--- title: 'Minimum Kapsayan Ağaç' source: 'https://academia.sh/tr/kurslar/algoritmalar/minimum-kapsayan-agac' course: Algoritmalar language: tr updated: '2026-08-17T18:07:38+00:00' license: 'CC BY-SA 4.0' --- # Minimum Kapsayan Ağaç Kesme özelliği, Prim ve Kruskal algoritmaları, birleşim-bulma yapısı, iki yaklaşımın karşılaştırması ve kümeleme uygulaması. Buraya kadarki sorular iki düğüm arasındaki yolla ilgiliydi. Bu ders soruyu değiştirir: **tüm düğümleri birbirine bağlayan en ucuz kenar kümesi hangisidir?** Soru, ağ tasarımının temel biçimidir: her noktayı bağlamak zorunludur, toplam kablo, boru veya hat maliyeti en aza indirilmelidir. ## Problem Ağırlıklı, yönsüz ve bağlı bir çizgede **kapsayan ağaç**, tüm düğümleri içeren ve çevrim barındırmayan bir alt çizgedir. Böyle bir alt çizgede tam olarak $V-1$ kenar bulunur. **Minimum kapsayan ağaç (MST)**, kenar ağırlıkları toplamı en küçük olan kapsayan ağaçtır. Ağırlıklar birbirinden farklıysa MST tektir; eşit ağırlıklar varsa birden çok MST olabilir ve hepsinin toplam ağırlığı aynıdır. Bu ders boyunca kullanılan çizge yönsüzdür: ```python kenarlar: list[tuple[int, str, str]] = [ (4, "A", "B"), (2, "A", "C"), (5, "B", "C"), (10, "B", "D"), (3, "C", "E"), (4, "E", "D"), (11, "D", "F"), ] dugumler = ["A", "B", "C", "D", "E", "F"] ``` ## Kesme Özelliği Her iki algoritma da açgözlüdür ve doğrulukları tek bir gözleme dayanır. **Kesme (cut)**, düğümlerin boş olmayan iki parçaya ayrılmasıdır. Bir kenar, uçları farklı parçalardaysa kesmeyi **geçer**. **Kesme özelliği:** Herhangi bir kesmeyi geçen en hafif kenar, bir minimum kapsayan ağaçta bulunur. Gerekçe bir **değiş tokuş** akıl yürütmesidir. En hafif geçen kenar $e$ olsun ve onu içermeyen bir MST düşünülsün. Bu ağaca $e$ eklenirse bir çevrim oluşur; çevrim, kesmeyi en az bir kez daha geçmek zorundadır. O geçen kenar $f$ olsun. $f$ çıkarılıp $e$ eklendiğinde yine bir kapsayan ağaç elde edilir ve ağırlığı artmamıştır, çünkü $e \leq f$'tir. Dolayısıyla $e$'yi içeren bir MST de vardır. Bu özellik, "şu an güvenli olan en ucuz kenarı al" biçimindeki her açgözlü stratejinin doğruluğunu verir. İki algoritma yalnızca **hangi kesmeye** baktıklarıyla ayrılır. ## Prim Algoritması Tek bir düğümden başlanır ve ağaç her adımda büyütülür. Bakılan kesme, ağaçtaki düğümler ile dışarıdakiler arasındaki kesmedir; seçilen kenar bu kesmeyi geçen en hafif kenardır. ```python import heapq from collections import defaultdict def komsuluk(kenarlar: list[tuple[int, str, str]]) -> dict[str, list[tuple[int, str]]]: k: dict[str, list[tuple[int, str]]] = defaultdict(list) for agirlik, v, w in kenarlar: k[v].append((agirlik, w)) k[w].append((agirlik, v)) return k def prim(kenarlar: list[tuple[int, str, str]], baslangic: str) -> tuple[list[tuple[int, str, str]], int]: komsu = komsuluk(kenarlar) icinde = {baslangic} kuyruk = [(a, baslangic, w) for a, w in komsu[baslangic]] heapq.heapify(kuyruk) agac: list[tuple[int, str, str]] = [] while kuyruk: agirlik, v, w = heapq.heappop(kuyruk) if w in icinde: # kenarın iki ucu da ağaçta: çevrim continue icinde.add(w) agac.append((agirlik, v, w)) for a, komsusu in komsu[w]: if komsusu not in icinde: heapq.heappush(kuyruk, (a, w, komsusu)) return agac, sum(a for a, _, _ in agac) print(prim(kenarlar, "A")) # ([(2, 'A', 'C'), (3, 'C', 'E'), (4, 'A', 'B'), (4, 'E', 'D'), (11, 'D', 'F')], 24) ``` Yapı, Dijkstra'ya çok benzer; tek fark önceliğin **kaynaktan uzaklık** değil **ağaca uzaklık** olmasıdır. Maliyet de aynıdır: ikili yığınla $O(E \log V)$. ## Kruskal Algoritması Kruskal ağaç büyütmez; kenarları ağırlığa göre sıralar ve sırayla ekler. Bir kenar, iki ucu **zaten aynı bileşendeyse** çevrim yaratacağı için atlanır. Bu denetim için **birleşim-bulma (union-find)** yapısı kullanılır: her düğümün hangi bileşende olduğunu neredeyse sabit maliyetle söyleyen bir yapı. ```python class BirlesimBulma: def __init__(self, dugumler: list[str]) -> None: self.ebeveyn = {d: d for d in dugumler} self.derece = {d: 0 for d in dugumler} def bul(self, d: str) -> str: while self.ebeveyn[d] != d: self.ebeveyn[d] = self.ebeveyn[self.ebeveyn[d]] # yol sıkıştırma d = self.ebeveyn[d] return d def birlestir(self, a: str, b: str) -> bool: ka, kb = self.bul(a), self.bul(b) if ka == kb: return False # zaten aynı bileşen if self.derece[ka] < self.derece[kb]: # dereceye göre birleştirme ka, kb = kb, ka self.ebeveyn[kb] = ka if self.derece[ka] == self.derece[kb]: self.derece[ka] += 1 return True def kruskal(kenarlar: list[tuple[int, str, str]], dugumler: list[str]) -> tuple[list[tuple[int, str, str]], int]: kume = BirlesimBulma(dugumler) agac: list[tuple[int, str, str]] = [] for agirlik, v, w in sorted(kenarlar): if kume.birlestir(v, w): agac.append((agirlik, v, w)) if len(agac) == len(dugumler) - 1: # ağaç tamamlandı break return agac, sum(a for a, _, _ in agac) print(kruskal(kenarlar, dugumler)) # ([(2, 'A', 'C'), (3, 'C', 'E'), (4, 'A', 'B'), (4, 'E', 'D'), (11, 'D', 'F')], 24) ``` İki algoritma bu çizgede aynı ağacı bulur. Genel olarak yalnızca **toplam ağırlığın** aynı olması güvencedir; eşit ağırlıklı kenarlar varsa farklı ama eşit ağırlıkta ağaçlar üretebilirler. Buradaki kesme, "eklenmeye çalışılan kenarın bir ucunun bileşeni" ile geri kalan düğümlerdir; kenar, o kesmeyi geçen en hafif kenardır çünkü daha hafif olanlar zaten denenmiştir. **Yol sıkıştırma** ve **dereceye göre birleştirme** birlikte kullanıldığında, birleşim-bulma işlemlerinin amortize maliyeti neredeyse sabittir — büyümesi ters Ackermann işleviyle sınırlıdır ve pratikte dörtten küçüktür. ## Karşılaştırma | Ölçüt | Prim | Kruskal | |---|---|---| | Yaklaşım | Ağacı büyüt | Kenarları sırayla ekle | | Yardımcı yapı | Öncelik kuyruğu | Birleşim-bulma | | Maliyet | $O(E \log V)$ | $O(E \log E)$ | | Yoğun çizge | Uygun (dizi değişkesiyle $O(V^2)$) | Sıralama baskın | | Bağlı olmayan çizge | Yalnızca bir bileşeni bulur | Kapsayan **orman** üretir | Kruskal'ın maliyetine sıralama egemendir; kenarlar zaten sıralıysa maliyet neredeyse doğrusala iner. Prim, kenar sayısı düğüm sayısının karesine yaklaştığında öne çıkar. Bir ayrım pratikte belirleyicidir: çizge bağlı değilse Kruskal her bileşen için bir ağaç üretir ve sonuç kapsayan ormandır; Prim ise yalnızca başlangıç düğümünün bileşenini kapsar. ## Kümeleme Uygulaması Kruskal'ın ara adımları tek başına anlamlıdır: algoritma $V-k$ kenar eklediğinde $k$ tane bileşen kalmıştır ve bu bileşenler, **birbirine en uzak duran** $k$ kümedir. Bu, tek bağlantılı kümeleme yöntemidir: noktalar arası uzaklıklar kenar ağırlığı sayılır, MST kurulur ve en ağır $k-1$ kenar atılır. Sonuç, kümeler arası en küçük uzaklığı en büyükleyen bölünmedir. Aynı yapı, ağ tasarımı ve yaklaşık çözümlerde de kullanılır: gezgin satıcı probleminin metrik durumunda MST, eniyi turun uzunluğu için bir alt sınır verir ve iki katını aşmayan bir tur üretmeye yarar. ## Özet - Kapsayan ağaç tüm düğümleri çevrimsiz bağlar ve $V-1$ kenar içerir; minimum kapsayan ağaç bunların en hafifidir. - Kesme özelliği, herhangi bir kesmeyi geçen en hafif kenarın bir MST'de bulunduğunu söyler ve açgözlü seçimleri gerekçelendirir. - Prim ağacı büyütür ve öncelik kuyruğu kullanır; maliyeti $O(E \log V)$'dir. - Kruskal kenarları sıralar ve birleşim-bulma ile çevrim denetler; maliyeti $O(E \log E)$'dir. - Yol sıkıştırma ve dereceye göre birleştirme, birleşim-bulma işlemlerini amortize olarak neredeyse sabit yapar. - Kruskal'ın ara durumları kümeleme üretir; MST ayrıca yaklaşık çözümlerde alt sınır sağlar. ## Sonraki Adım Şimdiye kadar kenarlar maliyet taşıyordu. Sonraki ders kenarlara farklı bir anlam yükler: **kapasite**. Bir ağdan kaynaktan hedefe en çok ne kadar akıtılabilir sorusu, artık çizge üzerinde tanımlı bir eniyileme problemidir ve yanıtı beklenmedik bir eşitlikle — en büyük akış ile en küçük kesme arasındaki eşitlikle — gelir.