Ağaç yönlendirilir mi yönlendirilmez mi?

2024 Yazar: Fiona Howard | [email protected]. Son düzenleme: 2024-01-10 06:44

Grafik teorisinde, bir ağaç, herhangi iki köşenin tam olarak bir yolla bağlı olduğu bir yönsüz grafiktir veya eşdeğer olarak bağlı bir döngüsel yönsüz grafiktir. … Bir çoklu orman (veya yönlendirilmiş orman veya yönlendirilmiş orman), altında yatan yönsüz grafiği bir orman olan yönlendirilmiş bir döngüsel olmayan grafiktir.

Yönlendirilmiş ve yönlendirilmemiş ağaçlar nelerdir?

Döngü içermeyen yönsüz bir graf ormandır ve eğer bağlıysa buna ağaç denir. Tüm kenarlar yönsüz kenarlara dönüştürüldüğünde yönsüz orman (veya ağaç) ise, yönlendirilmiş bir grafik bir ormandır (veya ağaçtır). Köklü bir ağaç, bir tepe noktası kök olarak belirlenmiş bir ağaçtır.

Ağaçlar neden yönsüz?

Teorem: Yönsüz bir grafik bir ağaçtır, eğer her bir köşe çifti arasında tam olarak bir tane basit yol varsaKanıt: Bir ağaç olan bir T grafiğimiz varsa, o zaman döngü olmadan bağlanmalıdır. T bağlı olduğundan, her bir köşe çifti arasında en az bir basit yol olmalıdır.

Yönlendirilmiş ağaç ne demek?

Yönlendirilmiş bir ağaç döngüsel olmayan bir yönlendirilmiş grafiktir Şekilde gösterildiği gibi derece 1 olan bir düğüme sahiptir, diğer tüm düğümler derece 1'e sahiptir: Derecesi 0 olan düğüm harici düğüm veya terminal düğüm veya yaprak olarak adlandırılır. Bire eşit veya daha büyük olan düğümlere dahili düğüm denir.

Yönsüz bir grafiğin ağaç olup olmadığını nasıl anlarsınız?

Yönlendirilmemiş grafikler durumunda, üç adım gerçekleştiririz:

1. Her düğümün tam olarak bir ebeveyni olduğundan emin olmak için herhangi bir düğümden bir DFS kontrolü yapın. Değilse, geri dönün.
2. Tüm düğümlerin ziyaret edildiğini kontrol edin. DFS denetimi tüm düğümleri ziyaret edemediyse,. döndürün
3. Aksi takdirde, grafik bir ağaçtır.