--- title: 'Ağ Akışı' source: 'https://academia.sh/tr/kurslar/algoritmalar/ag-akisi' course: Algoritmalar language: tr updated: '2026-08-17T18:07:39+00:00' license: 'CC BY-SA 4.0' --- # Ağ Akışı Akış ağı tanımı, kalan ağ ve artıran yol, Ford–Fulkerson yöntemi ile Edmonds–Karp değişkesi, en büyük akış–en küçük kesme teoremi ve eşleme uygulaması. 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. ```python 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. ```python 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. ```python 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. ```python 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.