Minimum kapsayan ağaçlar

1926'da Otakar Borůvka'dan Moravya'nın güneyindeki elektrik şebekesini olabildiğince ucuza planlaması istendi. Onun sorusu, her yeri en az toplam hat uzunluğuyla nasıl bağlarız, minimum kapsayan ağaç problemidir ve bu problemin bilgisayar biliminin en basit ve en zarif cevaplarından bazıları vardır.

Kenarlarının uzunlukları olan bir graf: büyüyen bir ağacın kısa kenarları vurgulanmış, döngü kapatacağı için atlanan bir kenar kırmızı kesik çizgiyle gösterilmiş, altında da denenecek kenarların listesi var
Kenarlarının uzunlukları olan bir graf: büyüyen bir ağacın kısa kenarları vurgulanmış, döngü kapatacağı için atlanan bir kenar kırmızı kesik çizgiyle gösterilmiş, altında da denenecek kenarların listesi var

Problem

Kenarlarının uzunlukları, yani maliyetleri olan bağlantılı bir graf alın. Kapsayan ağaç, tüm düğümleri bağlayan ve hiç döngü içermeyen bir kenar kümesidir; n düğümde her zaman tam olarak n − 1 kenarı vardır, çünkü her kenar bir düğüm daha bağlar. Tüm kapsayan ağaçlar arasında minimum kapsayan ağacın toplam uzunluğu en küçüktür. Bir grafın çok büyük sayıda kapsayan ağacı olabilir, ama hepsini denemeye gerek yoktur.

Açgözlü yaklaşım neden işe yarar

Düğümleri herhangi bir şekilde iki gruba ayırın. Gruplar arasında geçen en kısa kenar her zaman bir minimum kapsayan ağaca aittir: bir ağaç onun yerine gruplar arasında daha uzun bir kenar kullansaydı, onu daha kısa olanla değiştirmek aynı düğümleri daha ucuza bağlardı. Buna kesme özelliği denir. Madalyonun öbür yüzü döngü özelliğidir: herhangi bir döngüdeki en uzun kenara hiçbir zaman gerek yoktur. Aşağıdaki iki algoritma da bu kuralları tekrar tekrar uygular.

Bir örnek

Uzunluğu 1 olan A–B, 2 olan B–C, 3 olan A–C, 4 olan C–D ve 5 olan B–D kenarlarını alın. Kruskal algoritması A–B'yi, sonra B–C'yi alır, sonra A–C'yi atlar, çünkü A ile C zaten bağlıdır ve bu kenar bir döngü kapatırdı; sonra C–D'yi alır. Ağaçta dört düğüm için üç kenar vardır, yani iş biter; toplam uzunluk 7'dir ve B–D'ye hiç bakılmaz bile. A'dan başlayan Prim algoritması önce A–B ile B'yi ekler; B'nin B–C (2) kenarı, C'ye giden yol olarak A–C'yi (3) geçer, bu yüzden C, B–C ile katılır; C'nin C–D (4) kenarı B–D'yi (5) geçer, bu yüzden D, C–D ile katılır. Aynı ağaç, aynı 7.

Kruskal, Prim ve Borůvka

Joseph Kruskal'ın 1956'da yayımladığı Kruskal algoritması kenarları sıralar ve tek bir parçanın içindeki kenarları atlamak için bir union-find yapısı kullanır; bu yüzden işi E log E ile büyür. Prim algoritmasını ilk olarak 1930'da Vojtěch Jarník tanımladı; 1957'de Robert Prim ve 1959'da Edsger Dijkstra onu yeniden keşfetti. İkili yığınla işi E log V ile, basit bir diziyle de V² ile büyür; bu da yoğun graflar için iyidir. Borůvka'nın 1926 algoritması her parçanın aynı anda kendi en kısa dış kenarını almasını sağlar; bu da paralel bilgisayarlara uygundur.

Otakar Borůvka, 1981’de. 1926’da güney Moravya’nın elektrik şebekesini mümkün olduğunca ucuza planlaması istenince, ilk asgari yayılan ağaç algoritmasını verdi.
Otakar Borůvka, 1981’de. 1926’da güney Moravya’nın elektrik şebekesini mümkün olduğunca ucuza planlaması istenince, ilk asgari yayılan ağaç algoritmasını verdi.

Kullanım alanları

Minimum kapsayan ağaçlarla ucuz kablo, boru ve yol ağları tasarlanır. Verileri kümelere ayırırlar: ağacın en uzun kenarlarını çıkarın, geriye kalan parçalar kümelerdir. Uzaklıklar üçgen eşitsizliğine uyduğunda gezgin satıcı problemi için en iyisinin en fazla iki katı uzunlukta hızlı bir tur verirler. Ayrıca rastgele kenar uzunlukları olan bir ızgarada Kruskal ya da Prim algoritması, labirent üretmenin klasik bir yoludur.

Keşfedin

Uygulamayı açın, Kruskal ya da Prim'i seçin ve Adım'a basın. Kruskal'da denenecek kenarlar grafın altında en kısadan en uzuna listelenir; döngü kapatacak kenarlar kırmızı kesik çizgiyle çizilir. Prim'de orada katılmayı bekleyen düğümler, kesik çizgiyle çizilen en iyi kenarlarının uzunluğuyla birlikte listelenir. İkisini aynı grafta çalıştırıp karşılaştırın: sıra farklıdır, ama toplam uzunluk her zaman aynıdır.

Sık sorulan sorular

Kapsayan ağacın kaç kenarı vardır?

Tam olarak düğüm sayısından bir eksik. Daha az kenar her düğümü bağlayamaz, bir fazlası da her zaman bir döngü oluşturur.

Hangisi daha hızlı, Kruskal mı Prim mi?

Kenarları sıralayan Kruskal algoritması genellikle daha basittir ve az kenarlı seyrek graflarda hızlıdır. Yığın kullanan Prim algoritması yoğun graflarda iyi iş çıkarır; basit bir diziyle ise kaç kenar olursa olsun yaklaşık V² adım gerekir.

Union-find nedir?

Hangi düğümlerin aynı parçada olduğunu takip eden bir veri yapısı. "Bu ikisi bağlı mı?" sorusunu yanıtlar ve iki parçayı neredeyse anında birleştirir; Kruskal algoritmasının her kenar için tam olarak ihtiyaç duyduğu şey budur.

Minimum kapsayan ağaç yönlü graflarda işe yarar mı?

Olduğu gibi değil. Tek yönlü kenarları olan graflarda buna karşılık gelen problem minimum kapsayan arboresanstır ve Chu–Liu/Edmonds algoritmasıyla çözülür.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Minimum kapsayan ağaç kurun