Az yer kaplayan ağaç - Minimum spanning tree - Wikipedia

Bir düzlemsel grafik ve minimum yayılma ağacı. Her kenar, burada kabaca uzunluğu ile orantılı olan ağırlığıyla etiketlenmiştir.

Bir az yer kaplayan ağaç (MST) veya asgari ağırlık kapsayan ağaç bir kenarlarının alt kümesidir bağlı, tüm verileri birbirine bağlayan kenar ağırlıklı yönsüz grafik köşeler birlikte, hiç olmadan döngüleri ve mümkün olan minimum toplam kenar ağırlığıyla. Yani bu bir yayılan ağaç kenar ağırlıklarının toplamı mümkün olduğu kadar küçük. Daha genel olarak, herhangi bir kenar ağırlıklı yönsüz grafiğin (bağlı olması gerekmez) bir minimum genişleyen ormanasgari yayılan ağaçların birliği olan bağlı bileşenler.

Minimum yayılan ağaçlar için epeyce kullanım durumu vardır. Yeni bir mahalleye kablo döşemeye çalışan bir telekomünikasyon şirketi buna bir örnek olabilir. Kabloyu yalnızca belirli yollar (örneğin yollar) boyunca gömmekle sınırlandırılmışsa, bu yollarla bağlanan noktaları (örneğin evler) içeren bir grafik olacaktır. Yollardan bazıları daha pahalı olabilir, çünkü daha uzundurlar veya kablonun daha derine gömülmesini gerektirirler; bu yollar, daha büyük ağırlıklara sahip kenarlarla temsil edilecektir. Para birimi, kenar ağırlığı için kabul edilebilir bir birimdir - kenar uzunluklarının aşağıdaki gibi normal geometri kurallarına uyması gerekmez. üçgen eşitsizliği. Bir yayılan ağaç çünkü bu grafik, döngüsü olmayan ancak yine de her evi birbirine bağlayan yolların bir alt kümesi olacaktır; birkaç olası ağaç olabilir. Bir az yer kaplayan ağaç kablonun döşenmesi için en ucuz yolu temsil eden, toplam maliyeti en düşük olanı olacaktır.

Özellikleri

Olası çeşitlilik

Eğer varsa n grafikte köşeler, ardından her yayılan ağaçta n − 1 kenarlar.

Bu şekil, bir grafikte birden fazla minimum kapsayan ağaç olabileceğini gösterir. Şekilde, grafiğin altındaki iki ağaç, verilen grafiğin minimum yayılma ağacının iki olasılığıdır.

Aynı ağırlıkta birkaç minimum uzanan ağaç olabilir; özellikle, belirli bir grafiğin tüm kenar ağırlıkları aynıysa, o grafiğin her kapsayan ağacı minimumdur.

Benzersizlik

Her kenarın farklı bir ağırlığı varsa, o zaman yalnızca bir, benzersiz minimum kapsayan ağaç olacaktır.. Bu, yukarıdaki telekomünikasyon şirketi örneği gibi pek çok gerçekçi durumda geçerlidir. kesinlikle aynı maliyet. Bu, ormanları da kapsayacak şekilde genelleşir.

Kanıt:

1. Aksini varsayın, iki farklı MST olduğunu Bir ve B.
2. Dan beri Bir ve B aynı düğümleri içermesine rağmen farklılık gösterir, birine ait olan ancak diğerine ait olmayan en az bir kenar vardır. Bu tür kenarlar arasında e₁ en az ağırlığa sahip olmak; bu seçim benzersizdir çünkü kenar ağırlıklarının tümü farklıdır. Genelliği kaybetmeden varsayalım e₁ içinde Bir.
3. Gibi B bir MST, {e₁} ${ displaystyle cup}$ B bir döngü içermelidir C ile e₁.
4. Bir ağaç olarak Bir döngü içermez, bu nedenle C bir kenarı olmalı e₂ bu içinde değil Bir.
5. Dan beri e₁ tam olarak birine ait olanlar arasında benzersiz en düşük ağırlıklı kenar olarak seçildi Bir ve B, ağırlığı e₂ ağırlığından büyük olmalı e₁.
6. Gibi e₁ ve e₂ C döngüsünün bir parçasıdır, yerine e₂ ile e₁ içinde B bu nedenle daha küçük ağırlığa sahip bir kapsayan ağaç verir.
7. Bu varsayımla çelişir B bir MST'dir.

Daha genel olarak, eğer kenar ağırlıklarının hepsi farklı değilse, o zaman minimum kapsayan ağaçlarda sadece (çoklu) ağırlık setinin benzersiz olacağı kesindir; tüm minimum yayılma ağaçları için aynıdır.^[1]

Minimum maliyetli alt grafik

Ağırlıklar ise pozitifasgari yayılma ağacı aslında minimum maliyettir alt grafik tüm köşeleri bağlayan alt grafikler döngüleri daha fazla toplam ağırlığa sahip olması gerekir.^{[kaynak belirtilmeli ]}

Döngü özelliği

Herhangi bir döngü için C grafikte bir kenarın ağırlığı e nın-nin C diğer tüm kenarların tek tek ağırlıklarından daha büyüktür. C, bu durumda bu kenar bir MST'ye ait olamaz.

Kanıt: Aksini varsayın yani e bir MST'ye ait T₁. Sonra siliniyor e kırılacak T₁ iki ucu olan iki alt ağaca e farklı alt ağaçlarda. Geri kalanı C alt ağaçları yeniden bağlar, dolayısıyla bir kenar vardır f nın-nin C farklı alt ağaçlarda uçlarla, yani alt ağaçları bir ağaca yeniden bağlar T₂ ağırlığından daha az T₁çünkü ağırlığı f ağırlığından daha az e.

Özelliği kes

Bu şekil MST'lerin kesme özelliğini gösterir. T, verilen grafiğin tek MST'sidir. S = {A, B, D, E}, dolayısıyla VS = {C, F} ise, bu durumda kesim boyunca 3 olasılık vardır (S, VS), bunlar orijinalin BC, EC, EF kenarlarıdır grafik. O halde, e, kesim için minimum ağırlık kenarlarından biridir, bu nedenle S ∪ {e}, MST T'nin bir parçasıdır.

Herhangi kesmek C bir kenarın ağırlığı e kesim setinde C kesim setinin diğer tüm kenarlarının ağırlıklarından kesinlikle daha küçüktür. C, bu durumda bu kenar grafiğin tüm MST'lerine aittir.

Kanıt: Varsaymak bir MST var T içermeyen e. Ekleme e -e T her seferinde kesimi geçen bir döngü üretecek e ve başka bir kenardan geri geçiyor e ' . Siliniyor e ' yayılan bir ağaç alıyoruz T ∖ {e '} ∪ {e} daha hafif T. Bu varsayımla çelişir T bir MST idi.

Benzer bir argümana göre, bir kesim boyunca birden fazla kenar minimum ağırlıkta ise, o zaman bu tür kenarların her biri minimum bir kapsama ağacında bulunur.

Minimum maliyet avantajı

Minimum maliyet kenarı e Bir grafiğin benzersiz olması durumunda bu kenar herhangi bir MST'ye dahil edilir.

Kanıt: eğer e MST'ye dahil edilmedi, ekledikten sonra oluşturulan döngüdeki (daha büyük maliyet) kenarlarından herhangi biri kaldırıldı e MST'ye göre, daha küçük ağırlıkta bir kapsayan ağaç verir.

Kasılma

T, MST kenarlarından oluşan bir ağaçsa, sözleşme Daraltılmış grafiğin MST'si artı T'nin daralmadan önce grafik için MST'yi verdiği değişmezi korurken T'yi tek bir tepe noktasına çevirin.^[2]

Algoritmalar

Aşağıdaki tüm algoritmalarda, m grafikteki kenarların sayısıdır ve n köşe sayısıdır.

Klasik algoritmalar

Minimum yayılan ağaç bulmak için ilk algoritma Çek bilim adamı tarafından geliştirilmiştir. Otakar Borůvka 1926'da (bkz. Borůvka algoritması ). Amacı, verimli bir elektrik kapsama alanıydı. Moravia. Algoritma bir dizi aşamada ilerler. Her aşamada denir Boruvka adımıbir ormanı tanımlar F grafikteki her bir tepe noktasına minimum ağırlıklı kenar olayından oluşur G, ardından grafiği oluşturur ${ displaystyle G_ {1} = G setminus F}$ sonraki adımın girdisi olarak. Buraya ${ displaystyle G setminus F}$ türetilen grafiği gösterir G kenarları daraltarak F (tarafından Özelliği kes, bu kenarlar MST'ye aittir). Her Boruvka adımı doğrusal zaman alır. Her adımda köşe sayısı en az yarı yarıya azaldığından Boruvka'nın algoritması O alır (m günlük n) zaman.^[2]

İkinci bir algoritma Prim'in algoritması tarafından icat edilen Vojtěch Jarník 1930'da ve yeniden keşfedildi Prim 1957'de ve Dijkstra 1959'da. Temel olarak, MST'yi büyütür (T) her seferinde bir kenar. Başlangıçta, T keyfi bir tepe noktası içerir. Her adımda T en az ağırlıklı kenarla (x,y) öyle ki x içinde T ve y henüz içinde değil T. Tarafından Özelliği kes, tüm kenarlar eklendi T MST'de. Çalışma zamanı O (m günlük n) veya O (m + n günlük n), kullanılan veri yapılarına bağlı olarak.

Yaygın olarak kullanılan üçüncü bir algoritma Kruskal'ın algoritması O da alır (m günlük n) zaman.

Yaygın olarak kullanılmayan dördüncü bir algoritma, tersine silme algoritması, Kruskal'ın algoritmasının tersi. Çalışma zamanı O (m günlük n (günlük günlüğü n)³).

Bunların dördü de açgözlü algoritmalar. Polinom zamanda çalıştıkları için, bu tür ağaçları bulma problemi FP, ve ilgili karar problemleri Örneğin, belirli bir kenarın MST'de olup olmadığını belirlemek veya minimum toplam ağırlığın belirli bir değeri aşıp aşmadığını belirlemek gibi P.

Daha hızlı algoritmalar

Birkaç araştırmacı, hesaplama açısından daha verimli algoritmalar bulmaya çalıştı.

Kenar ağırlıklarında izin verilen tek işlemlerin ikili karşılaştırmalar olduğu bir karşılaştırma modelinde, Karger, Klein ve Tarjan (1995) buldum doğrusal zaman rasgele algoritması Borůvka algoritması ve tersine silme algoritmasının bir kombinasyonunu temel alır.^[3][4]

Bilinen karmaşıklığa sahip en hızlı rastgele olmayan karşılaştırma tabanlı algoritma Bernard Chazelle, dayanmaktadır yumuşak yığın, yaklaşık bir öncelik sırası.^[5][6] Çalışma süresi Ö (m α (m,n)), burada α klasik işlevdir Ackermann işlevinin tersi. Α fonksiyonu son derece yavaş büyür, böylece tüm pratik amaçlar için 4'ten büyük olmayan bir sabit olarak kabul edilebilir; bu nedenle Chazelle'nin algoritması doğrusal zamana çok yakın bir zaman alır.

Özel durumlarda doğrusal zaman algoritmaları

Yoğun grafikler

Grafik yoğunsa (ör. m/n ≥ günlük günlüğü n), sonra Fredman ve Tarjan tarafından bir deterministik algoritma MST'yi O zamanında bulur (m).^[7] Algoritma bir dizi aşamayı yürütür. Her aşama yürütülür Prim'in algoritması birçok kez, her biri sınırlı sayıda adım için. Her fazın çalışma süresi O (m+n). Bir aşamadan önceki köşe sayısı ${ displaystyle n '}$, bir aşamadan sonra kalan köşe sayısı en fazla ${ displaystyle n '/ 2 ^ {m / n'}}$. Bu nedenle, en fazla ${ displaystyle log ^ {*} {n}}$ Yoğun grafikler için doğrusal bir çalışma süresi sağlayan aşamalara ihtiyaç vardır.^[2]

Yoğun grafiklerde doğrusal zamanda çalışan başka algoritmalar da vardır.^[5][8]

Tamsayı ağırlıkları

Kenar ağırlıkları ikili olarak temsil edilen tamsayılarsa, sorunu çözen deterministik algoritmalar bilinir. Ö(m + n) tamsayı işlemleri.^[9]Sorunun çözülüp çözülemeyeceği belirleyici olarak için genel grafik içinde doğrusal zaman karşılaştırmaya dayalı bir algoritma ile açık bir soru olarak kalır.

Karar ağaçları

Verilen grafik G düğümlerin ve kenarların sabit olduğu, ancak ağırlıkların bilinmediği yerlerde, bir ikili oluşturmak mümkündür karar ağacı (DT) ağırlıkların herhangi bir permütasyonu için MST'yi hesaplamak için. DT'nin her dahili düğümü, iki kenar arasında bir karşılaştırma içerir, örn. "Aradaki kenarın ağırlığı x ve y arasındaki kenarın ağırlığından daha büyük w ve z? ". Düğümün iki çocuğu," evet "veya" hayır "olmak üzere iki olası yanıta karşılık gelir. DT'nin her bir yaprağında, G bu bir MST'ye karşılık gelir. Bir DT'nin çalışma zamanı karmaşıklığı, yalnızca DT'nin derinliği olan MST'yi bulmak için gereken en büyük sorgu sayısıdır. Grafik için DT G denir en uygun için tüm doğru DT'lerin en küçük derinliğine sahipse G.

Her tam sayı için r, üzerindeki tüm grafikler için en uygun karar ağaçlarını bulmak mümkündür. r köşeler kaba kuvvet arama. Bu arama iki adımda ilerler.

A. Tüm potansiyel DT'lerin oluşturulması

• Var ${ displaystyle 2 ^ {r seçim 2}}$ farklı grafikler r köşeler.
• Her bir grafik için, bir MST her zaman kullanılarak bulunabilir r(r-1) karşılaştırmalar, ör. tarafından Prim'in algoritması.
• Bu nedenle, optimal bir DT'nin derinliği, ${ displaystyle r ^ {2}}$.
• Dolayısıyla, optimal bir DT'deki dahili düğümlerin sayısı şundan azdır: ${ displaystyle 2 ^ {r ^ {2}}}$.
• Her dahili düğüm iki kenarı karşılaştırır. En fazla kenar sayısı ${ displaystyle r ^ {2}}$ bu nedenle farklı sayıda karşılaştırma en fazla ${ displaystyle r ^ {4}}$.
• Dolayısıyla, potansiyel DT'lerin sayısı şunlardan daha azdır: ${ displaystyle {(r ^ {4})} ^ {(2 ^ {r ^ {2}})} = r ^ {2 ^ {(r ^ {2} +2)}}}$.

B. Doğru DT'lerin belirlenmesiBir DT'nin doğru olup olmadığını kontrol etmek için, kenar ağırlıklarının tüm olası permütasyonlarında kontrol edilmelidir.

• Bu tür permütasyonların sayısı en fazla ${ displaystyle (r ^ {2})!}$.
• Her permütasyon için, mevcut herhangi bir algoritmayı kullanarak verilen grafikteki MST problemini çözün ve sonucu DT tarafından verilen cevapla karşılaştırın.
• Herhangi bir MST algoritmasının çalışma süresi en fazla ${ displaystyle (r ^ {2})}$, bu nedenle tüm permütasyonları kontrol etmek için gereken toplam süre en fazla ${ displaystyle (r ^ {2} +1)!}$.

Bu nedenle, en uygun DT'yi bulmak için gereken toplam süre herşey ile grafikler r köşeler: ${ displaystyle 2 ^ {r seç 2} cdot r ^ {2 ^ {(r ^ {2} +2)}} cdot (r ^ {2} +1)!}$, şundan küçüktür: ${ displaystyle 2 ^ {2 ^ {r ^ {2} + o (r)}}}$.^[2]

Optimal algoritma

Seth Pettie ve Vijaya Ramachandran, kanıtlanabilir şekilde optimal deterministik karşılaştırmaya dayalı minimum yayılma ağacı algoritması buldular.^[2] Aşağıdaki, algoritmanın basitleştirilmiş bir açıklamasıdır.

1. İzin Vermek ${ displaystyle r = log log log n}$, nerede n köşe sayısıdır. Tüm optimal karar ağaçlarını bulun r köşeler. Bu, O zamanında yapılabilir (n) (görmek Karar ağaçları yukarıda).
2. Grafiği en fazla bileşenlere böl r her bileşendeki köşeler. Bu bölüm bir yumuşak yığın, bu da grafiğin az sayıda kenarını "bozar".
3. Her bileşende bozulmamış alt grafik için bir MST bulmak için en uygun karar ağaçlarını kullanın.
4. MST'ler tarafından yayılan her bir bağlı bileşeni tek bir tepe noktasına taşıyın ve üzerinde çalışan herhangi bir algoritmayı uygulayın yoğun grafikler O zamanında (m) bozulmamış alt grafiğin daralmasına
5. Minimum kapsayan ağacı içermesi garantili ve başlangıç ​​grafiğinden sabit bir faktörle daha küçük olan bir alt grafik oluşturmak için, ortaya çıkan ormana bozuk kenarları geri ekleyin. En uygun algoritmayı bu grafiğe yinelemeli olarak uygulayın.

Algoritmadaki tüm adımların çalışma zamanı O (m), karar ağaçlarını kullanma adımı dışında. Bu adımın çalışma zamanı bilinmemekle birlikte optimal olduğu kanıtlanmıştır - hiçbir algoritma optimal karar ağacından daha iyisini yapamaz. Bu nedenle, bu algoritmanın kendine özgü özelliği vardır. kanıtlanabilir optimal çalışma zamanı karmaşıklığı olmasına rağmen Bilinmeyen.

Paralel ve dağıtılmış algoritmalar

Araştırma da dikkate aldı paralel algoritmalar minimum yayılma ağacı problemi için.Doğrusal sayıda işlemci ile problemi şurada çözmek mümkündür: ${ displaystyle O ( log n)}$ zaman.^[10][11]Bader ve Cong (2006) MST'leri 8 işlemcide optimize edilmiş bir sıralı algoritmadan 5 kat daha hızlı hesaplayabilen bir algoritma gösterin.^[12]

Diğer özel algoritmalar, çoğu zaman diskte saklanacak kadar büyük bir grafiğin minimum yayılma ağaçlarını hesaplamak için tasarlanmıştır. Bunlar harici depolama algoritmalar, örneğin Roman, Dementiev ve diğerleri tarafından "Harici Bellek Minimum Yayılan Ağaç Algoritmasını Tasarlamak" bölümünde açıklandığı gibi,^[13] yazarların iddialarına göre, geleneksel bellek içi algoritmadan 2 ila 5 kat daha yavaş çalışabilir. Verimliliğe güveniyorlar harici depolama sıralama algoritmaları ve üzerinde grafik daralması grafiğin boyutunu verimli bir şekilde küçültme teknikleri.

Soruna ayrıca bir dağıtılmış şekilde. Her düğüm bir bilgisayar olarak kabul edilirse ve hiçbir düğüm kendi bağlı bağlantıları dışında hiçbir şey bilmiyorsa, kişi yine de dağıtılmış minimum yayılma ağacı.

Tam grafiklerde MST

Alan M. Frieze verildiğini gösterdi tam grafik açık n dağıtım işlevine sahip bağımsız, aynı şekilde dağıtılmış rastgele değişkenler olan kenar ağırlıklarına sahip köşeler ${ displaystyle F}$ doyurucu ${ displaystyle F '(0)> 0}$sonra n yaklaşımlar +∞ MST yaklaşımlarının beklenen ağırlığı ${ displaystyle zeta (3) / F '(0)}$, nerede ${ displaystyle zeta}$ ... Riemann zeta işlevi (daha spesifik olarak ${ displaystyle zeta (3)}$ Apéry sabiti ). Friz ve Steele ayrıca olasılıkta yakınsama olduğunu kanıtladı. Svante Janson kanıtladı Merkezi Limit Teoremi MST'nin ağırlığı için.

Düzgün rastgele ağırlıklar için ${ displaystyle [0,1]}$, küçük tam grafikler için minimum yayılma ağacının tam olarak beklenen boyutu hesaplanmıştır.^[14]

Başvurular

Minimum yayılan ağaçların ağ tasarımında doğrudan uygulamaları vardır. bilgisayar ağları, telekomünikasyon ağları, ulaşım ağları, su şebekeleri, ve elektrik ızgaraları (yukarıda bahsedildiği gibi ilk icat edildikleri).^[15] Algoritmalarda diğer sorunlar için alt yordamlar olarak çağrılırlar. Christofides algoritması yaklaşmak için seyyar satıcı sorunu,^[16] çoklu terminal minimum kesme problemini yaklaştırmak (bu, tek terminal durumunda eşdeğerdir. maksimum akış sorunu ),^[17]ve minimum maliyet ağırlıklı mükemmele yaklaşmak eşleştirme.^[18]

Minimum yayılma ağaçlarına dayalı diğer pratik uygulamalar şunları içerir:

• Taksonomi.^[19]
• Küme analizi: düzlemde kümeleme noktaları,^[20] tek bağlantılı kümeleme (bir yöntem hiyerarşik kümeleme ),^[21] grafik teorik kümeleme,^[22] ve kümeleme gen ifadesi veri.^[23]
• İçin ağaç inşa etmek yayın bilgisayar ağlarında.^[24]
• Görüntü kaydı^[25] ve segmentasyon^[26] - görmek minimum genişleyen ağaç tabanlı bölümleme.
• Eğrisel özellik çıkarma içinde Bilgisayar görüşü.^[27]
• Elyazısı tanıma matematiksel ifadeler.^[28]
• Devre tasarımı: etkin çoklu sabit çarpımları uygulama sonlu dürtü yanıtı filtreler.^[29]
• Bölgeselleştirme sosyo-coğrafi alanların, alanların homojen, bitişik bölgelere gruplandırılması.^[30]
• Karşılaştırma ekotoksikoloji veri.^[31]
• Topolojik gözlenebilirlik güç sistemlerinde.^[32]
• İki boyutlu malzemelerin homojenliğinin ölçülmesi.^[33]
• Minimax Süreç kontrolü.^[34]
• Finansal piyasaları tanımlamak için minimum yayılma ağaçları da kullanılabilir.^[35][36] Herhangi iki hisse senedi arasındaki bir korelasyon katsayısı hesaplanarak bir korelasyon matrisi oluşturulabilir. Bu matris, topolojik olarak karmaşık bir ağ olarak temsil edilebilir ve ilişkileri görselleştirmek için minimum bir kapsayan ağaç inşa edilebilir.

İlgili sorunlar

Normal çokgen köşelerinin minimum Steiner ağaçları N = 3 ila 8 taraf. En düşük ağ uzunluğu L için N > 5, çevrenin bir kenarı eksiktir. Kareler Steiner noktalarını temsil eder.

Bulma sorunu Steiner ağacı Köşelerin bir alt kümesinin, yani verilen alt kümeye yayılan minimum ağacın, NP-Tamamlandı.^[37]

İlgili bir sorun da k-az yer kaplayan ağaç (k-MST), bazı alt kümeleri kapsayan ağaçtır. k grafikte minimum ağırlıklı köşeler.

Bir dizi k-en küçük yayılan ağaçlar alt kümesidir k alt kümenin dışındaki hiçbir ağacın daha az ağırlığa sahip olmayacağı şekilde, ağaçları (olası tüm kapsayan ağaçların dışında) kapsayan.^[38][39][40] (Bu sorunun, k-az yer kaplayan ağaç.)

Öklid asgari kapsayan ağaç düzlemde (veya boşlukta) noktalar olan köşeler arasındaki Öklid mesafesine karşılık gelen kenar ağırlıklarına sahip bir grafiğin kapsayan bir ağacıdır.

doğrusal minimum kapsayan ağaç kenar ağırlıklarına karşılık gelen bir grafiğin kapsayan bir ağacıdır. doğrusal mesafe düzlemdeki (veya uzaydaki) noktalar olan köşeler arasında.

İçinde dağıtılmış model, her bir düğümün bir bilgisayar olduğu ve hiçbir düğümün kendi bağlı bağlantıları dışında hiçbir şey bilmediği durumlarda, dağıtılmış minimum yayılma ağacı. Problemin matematiksel tanımı aynıdır ancak çözüm için farklı yaklaşımlar vardır.

kapasitif minimum kapsayan ağaç işaretlenmiş bir düğüme (başlangıç ​​veya kök) sahip bir ağaçtır ve düğüme eklenen alt ağaçların her biri, en fazla bir c düğümler. c ağaç kapasitesi denir. CMST'yi en iyi şekilde çözmek NP-zor,^[41] ancak Esau-Williams ve Sharma gibi iyi buluşsal yöntemler, polinom zamanında optimuma yakın çözümler üretir.

derece kısıtlı minimum yayılma ağacı her bir tepe noktasının en fazla bağlı olmadığı minimum bir kapsayan ağaçtır. d belirli bir sayı için diğer köşeler d. Dava d = 2 özel bir durumdur seyyar satıcı sorunu, dolayısıyla minimum yayılma ağacının derece kısıtlaması NP-zor Genel olarak.

İçin yönlendirilmiş grafikler, minimum yayılma ağacı problemine Ağaçlanma problem ve ikinci dereceden zamanda çözülebilir. Chu – Liu / Edmonds algoritması.

Bir maksimum kapsayan ağaç Ağırlığı diğer her bir kapsayan ağacın ağırlığından büyük veya ona eşit olan bir yayılan ağaçtır.Böyle bir ağaç, kenar ağırlıklarını -1 ile çarparak ve MST problemini yeni grafikte çözdükten sonra Prim veya Kruskal gibi algoritmalarla bulunabilir. Maksimum kapsama ağacındaki bir yol, en geniş yol iki uç noktası arasındaki grafikte: olası tüm yollar arasında, minimum ağırlıklı kenarın ağırlığını en üst düzeye çıkarır.^[42]Maksimum yayılma ağaçları, uygulama bulur ayrıştırma için algoritmalar doğal diller^[43]ve eğitim algoritmalarında koşullu rastgele alanlar.

dinamik MST sorun, orijinal grafikte bir kenar ağırlığı değişikliğinden veya bir tepe noktasının eklenmesinden / silinmesinden sonra önceden hesaplanmış bir MST'nin güncellenmesiyle ilgilidir.^[44][45][46]

Asgari etiketleme kapsayan ağaç problemi, bir grafikteki her kenar bir ağırlık yerine sonlu bir etiket kümesinden bir etiketle ilişkilendirilmişse, en az türde etiket içeren bir kapsayan ağaç bulmaktır.^[47]

Darboğaz kenarı, kapsayan bir ağaçtaki en yüksek ağırlıklı kenardır. Genişleyen ağaç bir minimum darboğaz kapsayan ağaç (veya MBST) grafik, daha küçük darboğaz kenar ağırlığına sahip bir kapsayan ağaç içermiyorsa. Bir MST, zorunlu olarak bir MBST'dir ( kesim özelliği ), ancak bir MBST mutlaka bir MST değildir.^[48][49]

Referanslar

daha fazla okuma

• Otakar Boruvka Minimum Yayılma Ağacı Problemi (her iki 1926 makalesinin tercümesi, yorumları, tarihçesi) (2000) Jaroslav Nešetřil, Eva Milková, Helena Nesetrilová. (Bölüm 7, Prim ve Kruskal'ın arasında bir kesişme gibi görünen algoritmasını verir.)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, ve Clifford Stein. Algoritmalara Giriş, İkinci baskı. MIT Press ve McGraw-Hill, 2001. ISBN  0-262-03293-7. Bölüm 23: Minimum Genişleyen Ağaçlar, s. 561–579.
• Eisner, Jason (1997). Minimum genişleyen ağaçlar için son teknoloji algoritmalar: Bir öğretici tartışma. Elyazması, Pennsylvania Üniversitesi, Nisan. 78 s.
• Kromkowski, John David. Yıllık Baskılar, Irk ve Etnik İlişkiler, 17 / e (2009 McGraw Hill) (Amerika Birleşik Devletleri'ndeki etnik çeşitliliğin demografik analizi yöntemi olarak minimum yayılma ağacını kullanma) "Tüm Bu Yıllardan Sonra Hala Erimemiş".

Dış bağlantılar

• BGL'de uygulanan Boost Grafik Kitaplığı
• Stony Brook Algoritma Deposu - Minimum Kapsayan Ağaç kodları
• .Net için QuickGraph'ta uygulanmıştır