YAYILAN AĞAÇ - DS EĞITIMI

Bu yazıda yayılan ağaç ve minimum yayılan ağacı tartışacağız. Ancak doğrudan yayılan ağaca geçmeden önce grafiğin ve türlerinin kısa bir açıklamasına bakalım.

Grafik

Bir grafik, bu köşeleri birbirine bağlayan bir grup köşe ve kenar olarak tanımlanabilir. Grafik türleri aşağıdaki gibidir:

Yönsüz grafik:Yönsüz bir grafik, tüm kenarların belirli bir yöne işaret etmediği, yani tek yönlü olmadığı bir grafiktir; çift yönlüdürler. Aynı zamanda, her bir kenarın iki farklı köşeyi birbirine bağladığı bir dizi V köşesi ve bir dizi E kenarı olan bir grafik olarak da tanımlanabilir.Bağlı grafik:Bağlı bir grafik, bir tepe noktasından diğer herhangi bir tepe noktasına her zaman bir yolun mevcut olduğu bir grafiktir. Herhangi bir yöndeki kenarları takip ederek herhangi bir köşeden herhangi bir köşeye ulaşabiliyorsak, bir grafik bağlantılıdır.Yönlendirilmiş grafik:Yönlendirilmiş grafikler aynı zamanda digraflar olarak da bilinir. Grafiğin herhangi bir köşesi veya düğümü arasında bulunan tüm kenarlar yönlendirilmişse veya tanımlanmış bir yöne sahipse, bir grafik yönlü bir grafiktir (veya digraftır).

Şimdi konu kapsayan ağaca doğru ilerleyelim.

Yayılan ağaç nedir?

Yayılan ağaç, yönlendirilmemiş bağlantılı bir grafiğin alt grafiği olarak tanımlanabilir. Mümkün olan en az sayıda kenarla birlikte tüm köşeleri içerir. Herhangi bir köşe atlanırsa bu yayılan ağaç değildir. Yayılan ağaç, grafiğin döngüleri olmayan bir alt kümesidir ve bağlantısı kesilemez.

Yayılan bir ağaç (n-1) kenardan oluşur; burada 'n', köşelerin (veya düğümlerin) sayısıdır. Yayılan ağacın kenarlarına ağırlıklar atanabilir veya atanmayabilir. Verilen G grafiğinden oluşturulan tüm olası yayılan ağaçlar aynı sayıda köşe noktasına sahip olacaktır, ancak yayılan ağaçtaki kenarların sayısı, verilen grafikteki köşe sayısı eksi 1'e eşit olacaktır.

Tam bir yönlendirilmemiş grafik şunları içerebilir: N^n-2 yayılan ağaçların sayısı nerede N grafikteki köşelerin sayısıdır. varsayalım, eğer n = 5 mümkün olan maksimum yayılan ağaçların sayısı 5^5-2= 125.

Yayılan ağacın uygulamaları

Temel olarak, grafiğin tüm düğümlerini birbirine bağlayacak minimum yolu bulmak için yayılan ağaç kullanılır. Yayılma ağacının yaygın uygulamalarından bazıları aşağıda listelenmiştir:

Küme analizi
Sivil ağ planlaması
Bilgisayar ağı yönlendirme protokolü

Şimdi yayılan ağacı bir örnek yardımıyla anlayalım.

Yayılan ağaç örneği

Grafiğin şöyle olduğunu varsayalım -

Yukarıda tartışıldığı gibi, bir yayılan ağaç, grafikle aynı sayıda köşe içerir; yukarıdaki grafikteki köşe sayısı 5'tir; bu nedenle yayılan ağaç 5 köşe içerecektir. Yayılan ağaçtaki kenarlar, grafikteki köşe sayısı eksi 1'e eşit olacaktır. Yani yayılan ağaçta 4 kenar olacaktır.

Yukarıdaki grafikten oluşturulacak olası yayılan ağaçlardan bazıları aşağıda verilmiştir:

Yayılan ağacın özellikleri

Yayılan ağacın bazı özellikleri şu şekilde verilmiştir:

Bağlantılı bir G grafiğinin birden fazla kapsayan ağacı olabilir.
Yayılan bir ağacın herhangi bir döngüsü veya döngüsü yoktur.
Yayılan bir ağaç minimum düzeyde bağlantılı, yani ağaçtan bir kenarı kaldırmak grafiğin bağlantısını kesecektir.
Yayılan bir ağaç maksimum asiklik, yani ağaca bir kenar eklemek bir döngü yaratacaktır.
Maksimum olabilir N^n-2 Tam bir grafikten oluşturulabilecek yayılan ağaç sayısı.
Yayılan bir ağaç var n-1 kenarlar; burada 'n', düğüm sayısıdır.
Grafik tam bir grafikse, kapsayan ağaç maksimum (e-n+1) kenarların kaldırılmasıyla oluşturulabilir; burada 'e' kenar sayısı ve 'n' köşe sayısıdır.

Dolayısıyla, yayılan ağaç, bağlantılı G grafiğinin bir alt kümesidir ve bağlantısız bir grafiğin kapsayan ağacı yoktur.

Az yer kaplayan ağaç

Minimum yayılan ağaç, kenar ağırlıklarının toplamının minimum olduğu kapsayan ağaç olarak tanımlanabilir. Yayılan ağacın ağırlığı, yayılan ağacın kenarlarına verilen ağırlıkların toplamıdır. Gerçek dünyada bu ağırlık mesafe, trafik yükü, sıkışıklık veya herhangi bir rastgele değer olarak kabul edilebilir.

Minimum yayılan ağaç örneği

Bir örnek yardımıyla minimum yayılan ağacı anlayalım.

Yukarıdaki grafiğin kenarlarının toplamı 16'dır. Şimdi, yukarıdaki grafikten oluşturulan olası yayılan ağaçlardan bazıları şunlardır:

Dolayısıyla, verilen ağırlıklı grafik için yukarıdaki kapsayan ağaçlardan seçilen minimum kapsayan ağaç -

Minimum kapsayan ağacın uygulamaları

Minimum kapsayan ağacın uygulamaları aşağıdaki gibidir:

Minimum kapsayan ağaç, su temini ağlarını, telekomünikasyon ağlarını ve elektrik şebekelerini tasarlamak için kullanılabilir.
Haritadaki yolları bulmak için kullanılabilir.

Minimum yayılan ağaç için algoritmalar

Aşağıda verilen algoritmalar kullanılarak ağırlıklı bir grafikten minimum yayılan ağaç bulunabilir:

Prim'in Algoritması
Kruskal Algoritması

Yukarıda listelenen algoritmaların her ikisinin de kısa bir açıklamasına bakalım.

Prim'in algoritması - Boş bir yayılan ağaçla başlayan açgözlü bir algoritmadır. Grafikten minimum yayılan ağacı bulmak için kullanılır. Bu algoritma, kenarların ağırlıklarının toplamı en aza indirilebilecek şekilde grafiğin her köşesini içeren kenar alt kümesini bulur.

en az en çok

Prim'in algoritması hakkında daha fazla bilgi edinmek için aşağıdaki bağlantıya tıklayabilirsiniz - https://www.javatpoint.com/prim-algorithm

Kruskal'ın algoritması - Bu algoritma aynı zamanda bağlantılı ağırlıklı bir grafik için minimum kapsayan ağacı bulmak için de kullanılır. Kruskal'ın algoritması da global optimuma odaklanmak yerine her aşamada optimum çözümü bulan açgözlü yaklaşımı izlemektedir.

Prim'in algoritması hakkında daha fazla bilgi edinmek için aşağıdaki bağlantıya tıklayabilirsiniz - https://www.javatpoint.com/kruskal-algorithm

Yani bu makaleyle ilgili. Umarım makale sizin için yararlı ve bilgilendirici olacaktır. Burada yayılan ağaç ve minimum yayılan ağaç özelliklerini, örneklerini ve uygulamalarını ele aldık.