Minimum Kapsayan Ağaç: En Az Kablo ile Tüm Şehirleri Bağlamak

1926, Moravya: bir elektrik mühendisi sorusu

Çekoslovakya'nın Moravya bölgesinde Western Moravian Electricity Company'nin başında genç bir mühendis: Otakar Borůvka, 26 yaşında, gerçek mesleği matematikçi. Şirket, elde edilen veriden Moravya'daki 40 şehiri elektrikle bağlayacak yeni bir şebeke planlıyor.

Mühendis sorar: "Tüm şehirleri bağlamak için en az kabloyu nasıl kullanırım?" Her şehir çifti arasındaki maliyet farklı. Toplam masraf minimum olsun.

Borůvka problemi formalleştirir: bir graf ($G = (V, E)$, $V$ köşeler = şehirler, $E$ kenarlar = olası kablolar) ve her kenarın ağırlığı (maliyet) var. Sorulan: tüm köşeleri birbirine bağlayan bir ağaç (döngüsüz alt graf) bul, ki toplam ağırlık minimum olsun.

Bu, minimum kapsayan ağaç (Minimum Spanning Tree, MST) problemidir.

Tanım ve özellikler

Kapsayan ağaç = bağlı graf üzerinde:

• Tüm köşeleri içerir.
• Döngü içermez.
• Bağlıdır.

Eğer $|V| = n$ ise her kapsayan ağaç tam $n - 1$ kenar içerir.

MST = minimum toplam ağırlık ile kapsayan ağaç.

Borůvka 1926'da bu problemi çözen ilk algoritmayı yayımladı.

Açgözlü ispatın temel lemması

MST için tüm algoritmalar açgözlü (greedy) çalışır. Neden işe yarar?

Kesim (Cut) Özelliği: Bir graf düşünün, köşeleri iki gruba ayırın (kesim). Bu kesimi geçen tüm kenarlar arasında en küçük ağırlıklı kenar her MST'de bulunur.

Sezgi: aksi varsayalım — en küçük kenarı $e$ MST'de değil. MST kesimi geçen başka bir kenar $f$ kullanır ($w(f) > w(e)$). $e$ MST'ye eklendiğinde döngü oluşur; o döngüden $f$'yi atın. Yeni ağaç daha küçük ağırlıkta. Çelişki.

Bu lemmadan tüm MST algoritmaları sıralı olarak çıkar.

Algoritma 1: Borůvka (1926)

İlk MST algoritması.

Adım: Her köşe için, kendi bileşeninden çıkan en hafif kenarı işaretle. Tüm işaretli kenarları ağaca ekle. Bileşenleri birleştir. Bileşen sayısı 1 olana kadar tekrar.

Karmaşıklık: $O(E \log V)$.

Borůvka'nın algoritması bilinen ilk MST algoritmasıdır ama Çekoslovak literatüründe kaldı; İngilizce dünyada ancak 1985'te keşfedildi.

Algoritma 2: Kruskal (1956)

Joseph Kruskal'in algoritması — basit ve şık.

Adım:

1. Tüm kenarları ağırlığa göre artan sırada sırala.
2. En küçük kenardan başlayarak teker teker bakın:
   • Bu kenar döngü oluşturmuyorsa, ağaca ekleyin.
   • Döngü oluşturuyorsa atın.
3. $n - 1$ kenara ulaşınca dur.

Döngü kontrolü için Union-Find veri yapısı kullanılır.

Karmaşıklık: $O(E \log E) = O(E \log V)$.

Kruskal sade ve paralel hesaplamaya uygundur.

Algoritma 3: Prim (1957)

Robert Prim (ve bağımsız olarak Dijkstra 1959).

Adım:

1. Rastgele bir köşeyle başla.
2. Şu ana kadar oluşturulmuş ağaca bağlı en küçük kenarı bul (henüz ağaçta olmayan bir köşeye giden).
3. Ekle, tekrarla.

Karmaşıklık: Fibonacci heap ile $O(E + V \log V)$. Pratik uygulamalarda $O(E \log V)$.

Prim yoğun graflar (kenar sayısı yüksek) için daha hızlı.

Karşılaştırma

Algoritma	Yıl	Yaklaşım	Karmaşıklık
Borůvka	1926	Paralel bileşen birleştirme	$O(E \log V)$
Kruskal	1956	Kenar sıralama	$O(E \log V)$
Prim	1957	Tek kaynaklı genişleme	$O(E \log V)$

Modern paralel MST algoritmaları Borůvka tabanlı çünkü her adımda paralel işlem yapılabilir.

Uygulamalar

1. Telekomünikasyon altyapısı

Optik fiber ağ tasarımı. AT&T, Verizon gibi şirketler hangi şehirleri bağlayacaklarını seçerken MST kullanır.

2. Elektrik şebekeleri

Borůvka'nın orijinal motivasyonu. Bugün hâlâ standartır.

3. Boru hatları ve karayolu planlama

Petrol/su boru ağları, karayolu ana arter planlaması.

4. Küme analizi (clustering)

Tek bağlantılı (single linkage) küme analizi MST temelli. Veri noktalarını en yakın komşu ile birleştirip ağaç oluştur, sonra en uzun kenarları kes.

5. Yaklaşım algoritmaları — Gezgin Satıcı Problemi (TSP)

MST, TSP'nin %50'lik yaklaşımını verir: MST'yi "iki kere geçip" en kısa yol bul.

6. Bilgisayar görüsü

Segmentation: görüntü pikselleri arasındaki ağırlıklı graf üzerinde MST.

7. Sosyal ağ analizi

"En zayıf bağlantılı arkadaşlık ağı" — sosyolojik öneri sistemleri.

Eşsizlik

Eşsizlik teoremi: Eğer tüm kenar ağırlıkları farklıysa, MST biriciktir. Aynı ağırlıklı kenarlar varsa birkaç MST olabilir, ama tüm MST'lerin aynı toplam ağırlığı vardır.

Bu, MST probleminin iyi tanımlı bir optimal değer verdiğini garanti eder.

"Steiner ağacı" — daha güçlü problem

MST'de sadece verilen köşeleri birleştirebilirsiniz. Eğer yeni köşeler ekleme izniniz varsa (yani ara noktalar koyup yolları kısaltma), problem Steiner ağacına dönüşür.

Örnek: 3 köşe bir eşkenar üçgen, kenar uzunluğu 1. MST = 2 kenar, toplam = 2. Steiner ağacı = ortaya bir nokta ekleyip 3 kenar çekmek, toplam $\approx \sqrt{3} \approx 1.732$.

Steiner ağacı problemi NP-zordur (MST $O(E \log V)$, ama Steiner üstel zaman gerektirir). Optimizasyonun nadir bir örneği — küçük problem ekiyle gelmek bilgisayar bilimi karmaşıklık katmanını değiştiriyor.

Modern hızlı algoritmalar

2000'lerden sonra:

• Karger-Klein-Tarjan (1995): beklenen $O(E + V)$ rastgele algoritma.
• Chazelle (2000): deterministik $O(E \alpha(E, V))$ ($\alpha$ = ters Ackermann fonksiyonu, pratik olarak sabit).
• Pettie-Ramachandran (2002): optimum karmaşıklık çözen tek bir genel çerçeve.

Bunlar teorik inceliklerdir; pratikte Kruskal/Prim hâlâ en yaygın kullanılan.

Mirası

MST problemi, bilgisayar bilimi-graf teorisi sınırında zarif bir klasiktir:

• 1926'da bir elektrik mühendisinin sorusu.
• 3 ana algoritma, hepsi açgözlü.
• Modern altyapının (telekom, elektrik, taşımacılık) matematiğin temeli.
• Veri madenciliği, görüntü işleme, sosyal ağ analizinde rutin araç.

Bir tek sorudan — "En az kabloyla 40 şehri bağla" — modern bilgisayar bilimi dersi.

Borůvka'nın 1926 makalesi Slovakça yazıldı, 60 yıl çevrilmedi. Ama matematik dile tabi değil: doğru çözüm doğru çözümdür. 1926'da Çek mühendisin algoritması, 2026'da fiber optik şirketlerin yazılımının kalbinde çalışıyor.