Ağ Akışı

Kenarlar şimdiye kadar maliyet taşıdı: uzunluk, süre, ücret. Bu ders kenarlara farklı bir anlam yükler — kapasite. Soru artık “en ucuz yol hangisi” değil, “kaynaktan hedefe en çok ne kadar akıtılabilir” olur.

Problem, boru hatlarından iletişim ağlarına ve görev atamasına kadar geniş bir aileyi tek bir çatı altında toplar.

Akış Ağı

Akış ağı, her kenarında negatif olmayan bir kapasite bulunan yönlü bir çizgedir. İki özel düğüm vardır: kaynak ve havuz.

Bir akış, her kenara bir değer atar ve iki kısıtı sağlar:

Kapasite kısıtı. Hiçbir kenardaki akış, kapasitesini aşamaz.

Korunum kısıtı. Kaynak ve havuz dışındaki her düğümde, giren akış çıkan akışa eşittir.

Akışın değeri, kaynaktan çıkan net akıştır. Amaç bu değeri en büyüklemektir.

kapasite: dict[str, dict[str, int]] = {
    "S": {"A": 10, "C": 10},
    "A": {"B": 4, "C": 2, "D": 8},
    "B": {"T": 10},
    "C": {"D": 9},
    "D": {"B": 6, "T": 10},
    "T": {},
}

Kaynaktan çıkan toplam kapasite 20’dir, ama bu bir üst sınırdır; ağın iç yapısı daha düşük bir tavan koyabilir.

Kalan Ağ ve Artıran Yol

Açgözlü bir yaklaşım — “boş bir yol bul, doldur, tekrarla” — yanlış sonuç verir: erken yapılan bir seçim, daha sonra daha iyi bir dağılımı engelleyebilir ve geri alınamaz.

Çözüm, kalan ağ (residual network) kavramıdır. Kalan ağda her kenar için iki değer tutulur:

• İleri yönde kalan kapasite: kapasite eksi mevcut akış.
• Geri yönde, mevcut akış kadar kapasite.

Geri kenar, “bu kenardan gönderilen akışı iptal etme” olanağıdır. Böylece hiçbir seçim kalıcı olarak yanlış olmaz — algoritma kendi kararını sonradan düzeltebilir.

Kalan ağda kaynaktan havuza giden herhangi bir yola artıran yol denir. Yol boyunca gönderilebilecek miktar, üzerindeki en küçük kalan kapasitedir (darboğaz).

Ford–Fulkerson yöntemi: Artıran yol kaldığı sürece bul ve akışı artır.

Edmonds–Karp Değişkesi

Yöntem, artıran yolun nasıl seçileceğini söylemez. Yol her seferinde enine aramayla — yani en az kenarlı yol olarak — seçilirse, ortaya çıkan değişkenin maliyeti $O(V \cdot E^2)$’dir ve seçimden bağımsız olarak sonlanır.

from collections import deque, defaultdict


def kalan_ag(kapasite: dict[str, dict[str, int]]) -> dict[str, dict[str, int]]:
    kalan: dict[str, dict[str, int]] = defaultdict(dict)
    for v in kapasite:
        for w, c in kapasite[v].items():
            kalan[v][w] = c
            kalan[w].setdefault(v, 0)      # geri kenar: başlangıçta sıfır
    return kalan


def edmonds_karp(kapasite: dict[str, dict[str, int]],
                 kaynak: str, havuz: str) -> tuple[int, set[str]]:
    """(en büyük akış, kalan ağda kaynaktan ulaşılabilen düğümler)"""
    kalan = kalan_ag(kapasite)
    toplam = 0

    while True:
        onceki: dict[str, str | None] = {kaynak: None}
        kuyruk = deque([kaynak])
        while kuyruk and havuz not in onceki:
            v = kuyruk.popleft()
            for w, c in kalan[v].items():
                if c > 0 and w not in onceki:
                    onceki[w] = v
                    kuyruk.append(w)

        if havuz not in onceki:            # artıran yol kalmadı
            return toplam, set(onceki)

        d, darbogaz = havuz, float("inf")
        while onceki[d] is not None:       # darboğazı bul
            darbogaz = min(darbogaz, kalan[onceki[d]][d])
            d = onceki[d]

        d = havuz
        while onceki[d] is not None:       # akışı gönder, geri kenarı büyüt
            kalan[onceki[d]][d] -= darbogaz
            kalan[d][onceki[d]] += darbogaz
            d = onceki[d]
        toplam += darbogaz


akis, ulasilabilir = edmonds_karp(kapasite, "S", "T")
print(akis, sorted(ulasilabilir))       # 19 ['C', 'S']

Kaynaktan çıkan 20 birimlik kapasiteye karşın en büyük akış 19’dur. Sınırı koyan şeyin ne olduğu, dönen ikinci değerde saklıdır.

En Büyük Akış – En Küçük Kesme

Bir kesme, düğümleri kaynağın bulunduğu ve havuzun bulunduğu iki parçaya ayırır. Kesmenin kapasitesi, kaynak tarafından havuz tarafına giden kenarların kapasiteleri toplamıdır.

Her akışın değeri, her kesmenin kapasitesinden küçük veya ona eşittir — akış, kesmeyi geçmek zorundadır. Teorem bundan daha güçlüsünü söyler:

$$\text{en büyük akış} = \text{en küçük kesme kapasitesi}$$

Gerekçe algoritmadan çıkar. Algoritma durduğunda kalan ağda kaynaktan havuza yol yoktur; kaynaktan ulaşılabilen düğümler bir kesme tanımlar. Bu kesmeyi geçen ileri kenarların hepsi doludur (yoksa ulaşılabilirlik sürerdi) ve geri kenarların hepsi boştur. Dolayısıyla akışın değeri, tam olarak bu kesmenin kapasitesine eşittir.

kesme = [(v, w) for v in kapasite for w in kapasite[v]
         if v in ulasilabilir and w not in ulasilabilir]

print(kesme)                                              # [('S', 'A'), ('C', 'D')]
print(sum(kapasite[v][w] for v, w in kesme))              # 19

Sonuç yalnızca bir sayı değil, bir teşhistir: ağın darboğazı S→A ve C→D kenarlarıdır. Kapasite artırımı yapılacaksa başka bir kenarı genişletmek akışı artırmaz.

Teoremin bir yan sonucu tam sayı özelliğidir: kapasiteler tam sayıysa, en büyük akışı veren bir akış da tam sayılıdır. Bu, akışın ayrık nesnelerin atanması olarak yorumlanabildiği problemlerde belirleyicidir.

İndirgeme: İkili Eşleme

Ağ akışının gücü, başka problemlerin ona indirgenebilmesindedir.

İki kümeli (bipartite) bir çizgede en büyük eşleme problemi şudur: sol taraftaki her düğümü, aralarında kenar bulunan bir sağ düğüme, hiçbir düğüm iki kez kullanılmadan eşlemek.

İndirgeme basittir: yapay bir kaynaktan sol düğümlere 1 kapasiteli kenarlar, mevcut kenarlara 1 kapasite, sağ düğümlerden yapay bir havuza 1 kapasiteli kenarlar.

def en_buyuk_esleme(sol: list[str], sag: list[str],
                    baglar: dict[str, list[str]]) -> int:
    ag: dict[str, dict[str, int]] = defaultdict(dict)
    for s in sol:
        ag["S"][s] = 1
    for s, liste in baglar.items():
        for h in liste:
            ag[s][h] = 1
    for h in sag:
        ag[h]["T"] = 1
    ag["T"] = {}
    return edmonds_karp(ag, "S", "T")[0]


print(en_buyuk_esleme(["a1", "a2", "a3"], ["i1", "i2", "i3"],
                      {"a1": ["i1", "i2"], "a2": ["i1"], "a3": ["i2", "i3"]}))   # 3

print(en_buyuk_esleme(["a1", "a2", "a3"], ["i1", "i2", "i3"],
                      {"a1": ["i1"], "a2": ["i1"], "a3": ["i1"]}))               # 1

Birinci örnekte üç adayın üçü de farklı işlere yerleşir; ikincisinde hepsi tek bir işi istediği için yalnızca biri yerleşebilir. Tam sayı özelliği burada zorunludur: yarım bir eşleme anlamsız olurdu.

Aynı yöntem, görev atama, ayrık yolların sayısı ve proje seçimi gibi problemleri de akışa çevirir. İndirgeme, algoritma tasarımının merkezî tekniklerinden biridir ve Hesaplama Kuramı kursunda zorluk sınıflarını tanımlamak için de kullanılacaktır.

Sonlanma ve Seçim Duyarlılığı

Ford–Fulkerson yöntemi, artıran yolu keyfî seçtiğinde sorun çıkarabilir: her adımda çok küçük bir miktar artıran yollar seçilirse, tam sayı kapasitelerde bile adım sayısı akışın değeri kadar olabilir. Kapasiteler tam sayı değilse yöntem hiç sonlanmayabilir.

Enine aramayla seçim (Edmonds–Karp) bu sorunu ortadan kaldırır: artıran yolların uzunluğu azalmaz ve toplam adım sayısı $O(V \cdot E)$ ile sınırlıdır. Bu, “yöntem” ile “algoritma” ayrımının somut bir örneğidir — bir yöntemi algoritmaya çeviren şey, açık bırakılan seçimin belirlenmesidir.

Özet

• Akış ağı, kapasiteli kenarlardan oluşur; akış kapasite ve korunum kısıtlarını sağlar.
• Kalan ağdaki geri kenarlar, önceki kararların geri alınmasını sağlar ve açgözlü yaklaşımın hatasını giderir.
• Ford–Fulkerson artıran yol kaldıkça akışı büyütür; Edmonds–Karp yolu enine aramayla seçerek $O(V E^2)$ sınırını verir.
• En büyük akış, en küçük kesme kapasitesine eşittir; kalan ağda ulaşılabilen küme bu kesmeyi verir.
• Kapasiteler tam sayıysa en büyük akışı veren tam sayılı bir akış vardır.
• İkili eşleme gibi problemler akış ağına indirgenerek çözülür.

Sonraki Adım

Çizge algoritmaları, aralarında bağlantı bulunan veriler üzerinde çalıştı. Sonraki konu farklı bir yapıya geçer: sıralı simgeler. Metin içinde örüntü aramak, ilk bakışta doğrusal bir tarama gibi görünse de, örüntünün kendi yapısı kullanıldığında belirgin biçimde hızlanır. Konu, kaba kuvvet aramanın maliyetini ölçerek başlayacak.