Minimum Kapsayan Ağaç

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:

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.

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ı.

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.