Max-flow, residual graph ve matching

Akışta her kenarda 0≤f≤capacity, source/sink dışındaki düğümlerde conservation korunur. Residual graf ileri kenarda kalan kapasiteyi, geri kenarda önceki kararı geri alma imkanını tutar. Geri kenar gerçek boru eklemek değildir; seçilmiş akışı yeniden yönlendirme modelidir.

Ford–Fulkerson augmenting path bulup bottleneck kadar iter. Tamsayı kapasitede sonlanır; genel irrational kapasite ve kötü yol seçiminde sorun çıkabilir. Edmonds–Karp BFS ile en az kenarlı residual yolu seçer ve O(VE²) sınır verir. Dinic level graph ve blocking flow kullanır; daha ileri veri yapıları farklı sınırlar sağlar.

Max-flow=min-cut teoremi sonucu doğrular: source'tan residual erişilebilir küme bir kesit üretir. Bipartite matching source→sol→sağ→sink unit capacities ile modele çevrilir. Hopcroft–Karp doğrudan matching için O(E√V) sağlar. Min-cost flow başka problemdir; sadece en büyük akış en ucuz akışı garanti etmez.

Geri kenar neden zorunlu?

Bir flow seçimi daha sonra değiştirilebilir. u→v üzerinden f birim gönderildiğinde residual graph'ta ileri kapasite azalır, v→u ters kapasitesi artar. Bu ters edge fiziksel boru eklemek değil, önceki kararı geri alabilme hakkıdır. Augmenting path bottleneck'i yolun minimum residual kapasitesidir; her edge bu miktarla güncellenir.

Source ve sink dışında flow conservation sağlanır. Her edge için 0≤f≤c koşulu kontrol edilir. Undirected capacity veya parallel edges farklı representation ister; tek adjacency matrix hücresine tüm semantiği sıkıştırmak ters/gerçek edge'leri karıştırabilir.

Max-flow/min-cut theorem: daha fazla augmenting path kalmadığında residual'da source'tan reachable küme bir cut oluşturur ve flow değeri bu cut kapasitesine eşittir. Edmonds-Karp her augmenting path'i BFS ile seçer; O(VE²) bound yol uzunluklarının düzenine bağlıdır, yalnız integral capacity değerine değil. Ford-Fulkerson arbitrary path seçimi irrational capacity modelinde termination sorunu taşıyabilir.

Temel: Her augmentation sonrası conservation doğrula. Orta: Reverse edge kullanılmadan bulunamayan bir iyileştirme örneği kur. İleri: Bipartite matching'i unit-capacity flow'a dönüştür; matching witness ve min-cut certificate'ını ayrı döndür.

# A residual augmentation along s -> a -> t.
r = {("s","a"):3, ("a","t"):2, ("a","s"):0, ("t","a"):0}
path = [("s","a"),("a","t")]
bottleneck = min(r[e] for e in path)
for u,v in path:
    r[u,v] -= bottleneck
    r[v,u] += bottleneck
assert r["a","s"] == 2 and r["a","t"] == 0