Kapsayan Ağaç ve Minimum Kapsama Ağacı

Bu eğitimde, örnekler ve şekiller yardımıyla yayılan ağaç ve minimum yayılan ağaç hakkında bilgi edineceksiniz.

Ağaçları kapsamayı öğrenmeden önce, iki grafiği anlamamız gerekir: yönlenmemiş grafikler ve bağlantılı grafikler.

Bir yönsüz grafik kenarları bir yöne işaret etmeyen bir grafiktir (yani. Kenarları çift yönlüdür).

Yönlendirilmemiş Grafik

Bir bağlı grafiği hep başka tepe bir tepe noktasından bir yol var olduğu bir grafiktir.

Bağlı Grafik

Kapsayan ağaç

Yayılan ağaç, mümkün olan minimum sayıda kenarla grafiğin tüm köşelerini içeren, yönlendirilmemiş bağlantılı bir grafiğin bir alt grafiğidir. Bir tepe noktası eksikse, bu bir kapsayan ağaç değildir.

Kenarlara ağırlık atanmış olabilir veya olmayabilir.

nTam bir grafikten oluşturulabilen köşeli ağaçların toplam sayısı şuna eşittir .n(n-2)

Varsa n = 4, mümkün olan maksimum yayılma ağaç sayısı eşittir . Böylece, 4 köşeli tam bir grafikten 16 adet uzanan ağaç oluşturulabilir.44-2 = 16

Yayılan Ağaç Örneği

Kapsayan ağacı aşağıdaki örneklerle anlayalım:

Orijinal grafik şöyle olsun:

Normal grafik

Yukarıdaki grafikten oluşturulabilecek olası yayılma ağaçlarından bazıları şunlardır:

Bir kapsayan ağaç A kapsayan ağaç A kapsayan ağaç A kapsayan ağaç A kapsayan ağaç A kapsayan ağaç

Az yer kaplayan ağaç

Minimum yayılan ağaç, kenarların ağırlıklarının toplamının mümkün olduğu kadar minimum olduğu bir kapsayan ağaçtır.

Yayılan Ağaç Örneği

Yukarıdaki tanımı aşağıdaki örnek yardımıyla anlayalım.

İlk grafik:

Ağırlıklı grafik

Yukarıdaki grafikte yer alan olası yayılma ağaçları şunlardır:

Minimum kapsayan ağaç - 1 Minimum kapsayan ağaç - 2 Minimum kapsayan ağaç - 3 Minimum kapsayan ağaç - 4

Yukarıdaki yayılan ağaçlardan minimum uzanan ağaç:

Az yer kaplayan ağaç

Bir grafikten minimum yayılma ağacı aşağıdaki algoritmalar kullanılarak bulunur:

1. Prim Algoritması
2. Kruskal Algoritması

Kapsayan Ağaç Uygulamaları

• Bilgisayar Ağı Yönlendirme Protokolü
• Küme analizi
• Sivil Ağ Planlaması

Minimum Kapsama Ağacı Uygulamaları

• Haritadaki yolları bulmak için
• Telekomünikasyon ağları, su temini ağları ve elektrik şebekeleri gibi ağlar tasarlamak.