Borůvka algoritması
Borůvka algoritması_Anim.gif)
Borůvka algoritmasını temsil eden animasyon, daraltmasız versiyonda.
| Kaşif veya mucit | Otakar Borůvka |
|---|---|
| Yayın tarihi | 1926 |
| İlgili konular | Grafik teorisi algoritması ( d ) , matematiksel kavram ( d ) |
Borůvka algoritması a, arama algoritması için en az ağırlığın kapsayan ağacın bir de ağırlıklı grafik . Aynı zamanda Sollin'in algoritması olarak da adlandırılır .
Minimal yayılma ağacı sorunu
Olarak grafik teorisi , belirli bir bağlı yönsüz grafik , kenarları ağırlıklandırılmış, bu grafiğin minimum ağırlık bir kapsayan ağaç a, bir kapsayan ağaç ( alt grup a, ağaç ve hep birlikte köşeleri birbirine bağlayan) miktarı toplamı kenar ağırlıklarının çok az.
Algoritma
Prensip
Prensip, kenarları daraltarak G'yi azaltmaktır : ağaçta olacak kenarları kademeli olarak seçeriz ve her birini seçtiğimizde, bu kenarın bağladığı düğümleri birleştiririz. Yani, sonunda sadece bir köşe kaldı.
Algoritmayı daralmadan bahsetmeden de tanımlayabiliriz: ağaçları azar azar birleşerek minimum ağırlığı kaplayan bir ağaç oluşturan bir orman inşa ediyoruz.
Sözde kod
G grafiğini ve F'yi seçilen kenarlar kümesini alıyoruz (azar azar dolduruyoruz).
1 F ← vide 2 Tant que G n'est pas réduit à un sommet faire 3 Détruire les boucles de G (*) 4 Remplacer les arêtes multiples entre deux sommets par une seule dont le poids est le minimum 5 Pour tout x, sommet de G, faire 6 Trouver l'arête e_x de poids minimum adjacente à x 7 F ← F union e_x 8 Contracter e_x (**) 9 fin pour 10 fin tant que 11 renvoyer F;;(*) yani başlayan ve aynı tepe noktasına varan kenarlar; bu tür kenarlar bir yinelemeden sonra ortaya çıkabilir.
(**) ör . köşeleri birleştirmek
Karmaşıklık
Borůvka algoritması bir sahiptir karmaşıklığı in , kenarların sayısını ve bir kabul Grafiğin köşeler sayısı.
Diğer algoritmalarla karşılaştırma
Minimal yayılma ağacı problemi için başka algoritmalar da vardır, örneğin Prim algoritması ve Kruskal algoritması .
Tarihi
Borůvka'nın algoritması, Otakar Borůvka tarafından 1926'da O jistém Problému minimálním ('Belli bir minimal problem üzerine') makalesinde yayımlanan, keşfedilen minimum ağırlıkta ilk kapsamlı ağaç arama algoritmasıdır . Başlangıçta bunu yapmak amaçlı olduğunu elektrik şebekesi arasında Moravia etkilidir. Daha sonra birçok kez yeniden keşfedildi.
Notlar ve referanslar
- Ivan Lavallée, " Bir grafikte minimum ağırlıkta bir ağaç oluşturmak için etkili bir paralel algoritma ", RAIRO-Operations Research , cilt. 19, n o 1, 1985, s. 57-69
- Graham-Hell, Minimum Yayılan Ağaç Sorununun Tarihi Üzerine s. 52.
- ( Borůvka 1926 )
- Graham-Hell, Minimum Yayılan Ağaç Sorununun Tarihi Üzerine s. 47.
Kaynakça
- (cs) Otakar Borůvka , " O jistém Problému minimálním (Belirli bir minimal sorun hakkında) " , Práce mor. přírodověd. spol. v Brně III , cilt. 3,1926, s. 37–58
- (tr) RL Graham ve Pavol Hell , " Minimum Yayılma Ağacı Probleminin Tarihi Üzerine " , Annals of the History of Computing , cilt. 7, n o 1,Ocak 1985, s. 43-57 ( çevrimiçi okuyun )
Dış bağlantı
- " Boruvka algoritması " üzerine, at coati INRIA