Bölüm 4.4: Ağ Akışı

4.4.1Akış ağları

Çizgelerde şimdiye kadar sorulan sorular çoğunlukla yollarla ilgiliydi: iki düğüm arasında yol var mı, en kısa yol hangisi, bütün düğümleri en ucuza bağlayan ağaç hangisi? Ağ akışı başka bir şey sorar. Bir yol bulmak yetmez; aynı anda pek çok yol kullanılır ve bu yollar ortak kenarları paylaşır. Her kenarın bir taşıma sınırı vardır. Soru, bütün yolların birlikte en fazla ne kadar taşıyabileceğidir.

Bu soru gündelik hayatta sık karşımıza çıkar. Boru hattında su, yol ağında trafik, bilgisayar ağında veri paketleri birer akıştır. Her boru en fazla kendi kapasitesi kadar su taşır. Kavşaklarda su birikmez: bir kavşağa ne kadar su girerse o kadarı çıkar. Bu iki gözlem, akış ağı modelinin iki temel kısıtına dönüşür.

4.4.1.1Maksimum akış problemi

Model yönlü bir çizgedir. Çizgede iki özel düğüm bulunur. Akışın çıktığı düğüme kaynak (source), vardığı düğüme hedef (sink) denir. Kaynak s, hedef t ile gösterilir. Her kenarın bir kapasitesi (capacity) vardır: o kenardan birim zamanda geçebilecek en fazla miktar.

Notun büyük bölümünde aynı küçük ağ kullanılacak. Şekil 4.4.1 bu ağı gösterir. Altı düğüm ve yedi kenar vardır; kenar etiketleri kapasitelerdir. Kaynak S, hedef T'dir.

Maksimum akışın 7 olduğunu iki yönden görmek gerekir. Birincisi, 7 birim gönderilebilir; bunu gösteren bir akış birazdan verilecek. İkincisi, 7'den fazlası gönderilemez. Bu ikinci iddia kaynağa bakarak hemen anlaşılır. S'den çıkan iki kenarın kapasiteleri toplamı 4 + 3 = 7'dir. Kaynaktan çıkan her birim bu iki kenardan birini kullanmak zorundadır. Öyleyse hedefe 7'den fazlası ulaşamaz. Bu basit gözlem, ilerideki kesim kavramının ilk örneğidir.

Aynı akıl yürütme hedef tarafında da yapılabilir. T'ye giren kenarların kapasiteleri 2 + 6 = 8'dir. Bu da bir üst sınırdır, ama 7'den gevşektir. İki sınırın küçüğü geçerlidir. Her zaman doğru bir üst sınır şudur: maksimum akış, kaynaktan çıkan kapasitelerin toplamını ve hedefe giren kapasitelerin toplamını aşamaz. Bu sınır her zaman sıkı değildir; darboğaz ağın ortasında da olabilir.

4.4.1.2Akış ve kısıtları

Akış, her kenara o kenardan geçen miktarı atar. Bu atamanın anlamlı olması için iki kural sağlanmalıdır.

Kapasite kısıtı borunun taşıma sınırını anlatır. Akış negatif olamaz; boru ters yönde çalışmaz. Kapasiteyi de aşamaz. Korunum kısıtı ise ara düğümlerin depo olmadığını söyler. Bir ara düğüme giren her birim bir yerden çıkmalıdır. Kaynak ve hedef bu kuraldan muaftır: kaynak akışı üretir, hedef tüketir.

Değer tanımındaki çıkarma terimi ilk bakışta gereksiz görünebilir. Örnek ağımızda kaynağa giren kenar yoktur, dolayısıyla bu terim sıfırdır. Ama genel bir ağda kaynağa geri dönen kenarlar olabilir. Kaynaktan 5 birim çıkıp 1 birimi geri dönüyorsa, ağa gerçekte 4 birim gönderilmiştir. Bu yüzden değer, kaynaktan çıkan net akıştır. Korunum sayesinde bu net akış, hedefe giren net akışa eşittir: ara düğümlerin hiçbiri akış biriktirmediği için kaynaktan çıkan her şey eninde sonunda hedefe varır.

Bu akışta bazı kenarlar sınırına kadar doludur. f(u, v) = c(u, v) olan bir kenara doymuş (saturated) kenar denir; üzerinden daha fazla akış gönderilemez. Şekildeki akışta S→A, S→C, A→B ve B→T doymuştur. Kaynaktan çıkan iki kenarın da doymuş olması, akışın neden artırılamayacağını açıklar. Doymuş kenarlar, maksimum akışın neden daha büyük olamayacağını anlatan kesimlerin parçasıdır.

4.4.1.3Birden çok kaynak ve hedef

Gerçek problemlerde tek bir kaynak ve tek bir hedef nadiren bulunur. Birkaç fabrika birkaç depoya mal gönderir; birkaç sunucu birkaç kullanıcı grubuna veri akıtır. Bu durumu ayrı bir algoritma gerektirmeden çözmenin yolu küçük bir çizge dönüşümüdür.

Ağa iki yeni düğüm eklenir: süper kaynak S ve süper hedef T. Her eski kaynak s_i için bir S → s_i kenarı, her eski hedef t_j için bir t_j → T kenarı konur. Bu kenarlara sınırsız (∞) kapasite verilir. Böylece yeni kenarlar hiçbir zaman darboğaz olmaz; akışı yalnızca eski ağın kenarları sınırlar. Yeni ağda S'den T'ye maksimum akış, eski ağda bütün kaynaklardan bütün hedeflere gönderilebilecek toplam akışa eşittir. Uygulamada ∞ yerine, eski ağın bütün kapasitelerinin toplamından büyük herhangi bir sayı yeterlidir.

Dönüşüm başka sınırlamalara da uyarlanabilir. Örneğin s₁ fabrikası en fazla 50 birim üretebiliyorsa S → s₁ kenarına ∞ yerine 50 kapasitesi verilir. Aynı düşünce, düğümlerin de kapasitesi olduğu problemlerde kullanılır: bir düğüm iki parçaya bölünür ve iki parça arasına düğümün kapasitesi kadar bir kenar konur. Bu yöntem uygulamalar arasında yeniden ele alınacak.

4.4.2Artık ağ ve artış yolu

Maksimum akışı bulmanın akla gelen ilk yolu açgözlü bir yöntemdir. Kaynaktan hedefe dolu olmayan kenarlardan geçen bir yol bulunur, yol boyunca gönderilebilecek kadar akış gönderilir ve bu iş yol kalmayana kadar sürdürülür. Bu yöntem bazen doğru sonucu verir, bazen vermez. Sorun, ilk kararların geri alınamamasıdır. Kötü seçilmiş bir yol, kenarları başka yolların daha iyi kullanabileceği bir biçimde doldurabilir. Çözüm, gönderilmiş akışı geri alma imkânını modele katmaktır. Bunu yapan yapı artık ağdır.

4.4.2.1Artık ağ

Artık ağ, mevcut akış altında hâlâ yapılabilecek değişiklikleri gösterir. İleri kenar “bu yönde daha fazla gönderebilirim” der. Ters kenar ise “bu yönde gönderdiğimin bir kısmını geri çekebilirim” der. Şekil 4.4.4 bunu tek bir kenarda gösterir. Kapasitesi 5 olan u → v kenarında 3 birim akış vardır. Artık ağda bu kenar iki kenara dönüşür: kalan 2 birim için u → v ileri kenarı ve geri alınabilecek 3 birim için v → u ters kenarı.

İki uç durum da öğreticidir. Akış sıfırsa ters kenarın kapasitesi sıfır olur ve ters kenar artık ağa girmez; artık ağ, özgün ağın aynısıdır. Kenar doymuşsa ileri kenarın kapasitesi sıfır olur ve artık ağda yalnızca ters kenar kalır. Her özgün kenar artık ağda en fazla iki kenar üretir. Bu yüzden artık ağın kenar sayısı en fazla 2E'dir.

4.4.2.2Ters kenarın anlamı

Ters kenar fiziksel bir boru değildir. v → u yönünde gerçek bir bağlantı olması gerekmez. Ters kenar bir muhasebe kaydıdır: daha önce u'dan v'ye gönderilmiş akışın iptal edilebileceğini gösterir. Ters kenar boyunca δ birim “göndermek”, f(u, v)'yi δ kadar azaltmak demektir.

Bu iptal neden işe yarar? Bir artış yolu v → u ters kenarını kullanıyorsa, yol v'ye gelen akışı u'dan gelen eski akışın yerine koyar. u'dan v'ye giden eski akış artık serbest kalır ve yolun devamında u'dan başka bir yöne gider. Sonuçta akış yeniden düzenlenir: bazı birimler eski yollarını bırakıp yenilerine geçer. Korunum her düğümde sağlanmaya devam eder. Ters kenarlar sayesinde algoritma ilk yanlış seçimlerini düzeltebilir. Bu düzeltmenin somut bir örneği Ford-Fulkerson'ın ikinci örneğinde görülecek.

4.4.2.3Artış yolu ve darboğaz

Artış yolundaki her kenarın artık kapasitesi pozitiftir. Yani yol ya kapasitesinden az akış taşıyan ileri kenarlardan ya da üzerinde akış bulunan kenarların ters yönlerinden geçer. Yol boyunca gönderilebilecek en fazla akış, yolun en dar kenarı kadardır. Zincirin gücü en zayıf halkası kadardır sözünün akıştaki karşılığı budur.

Akış başlangıçta her yerde sıfırsa artık ağ özgün ağın aynısıdır ve artış yolu sıradan bir yönlü yoldur. Artış yolları genellikle derinlik öncelikli arama (DFS, depth-first search) ya da genişlik öncelikli arama (BFS, breadth-first search) ile bulunur. Hangi aramanın kullanıldığı sonuçtaki akış değerini değiştirmez, ama algoritmanın kaç adım süreceğini çok değiştirir. Bu fark Edmonds-Karp algoritmasının çıkış noktasıdır.

4.4.2.4Akışı bir yol boyunca artırmak

Bir artış yolu p ve darboğazı δ = c_f(p) bulunduğunda akış şöyle güncellenir. Yoldaki her (u, v) kenarı için:

• (u, v) özgün ağın bir kenarıysa (ileri kenar) f(u, v), δ kadar artırılır.
• (u, v) bir ters kenarsa, yani özgün kenar (v, u) ise f(v, u), δ kadar azaltılır.

Bu teorem bütün artış yolu tabanlı algoritmaların temelidir. Her artışta akışın değeri kesin olarak büyür ve akış geçerliliğini korur. Geriye iki soru kalır. Artış yolu kalmadığında akış gerçekten maksimum mudur? Kaç artış gerekir? Birinci sorunun cevabı kesimlerle verilir. İkinci sorunun cevabı, yolun nasıl seçildiğine bağlıdır.

Güncellemenin iki önemli sonucu daha vardır. Darboğaz kenarının artık kapasitesi tam olarak δ'dır; güncellemeden sonra bu artık kapasite sıfıra iner. Yani her artışta yoldaki en az bir kenar artık ağdan çıkar. Ayrıca yoldaki her kenarın karşı yönünde δ birimlik artık kapasite doğar. Artık ağ böylece her artışta biraz değişir: bazı kenarlar kaybolur, bazı ters kenarlar ortaya çıkar.

4.4.3Kesimler

Bir akışın maksimum olduğunu kanıtlamak için daha büyük bir akışın olamayacağını göstermek gerekir. Bütün akışları tek tek denemek olanaksızdır. Kesim kavramı bunun yerine tek bir sayıyla üst sınır verir. Kaynağı içeren tarafla hedefi içeren taraf arasındaki kenarlar, akışın geçmek zorunda olduğu bir “sınır kapısı” gibidir. Kapının genişliği, geçebilecek akışı sınırlar.

4.4.3.1s–t kesimi ve kapasitesi

Tanımda kesim bir kenar kümesi değil, bir düğüm ayrımıdır. Kesilen kenarlar bu ayrımdan çıkar: bir ucu S'de, öbür ucu T'de olan kenarlar. Bu kenarlar ağdan silinirse kaynaktan hedefe yönlü yol kalmaz. Kapasite hesabında yalnızca S'den T'ye giden kenarlar sayılır. T'den S'ye giden kenarlar kapasiteye eklenmez, çünkü akışın hedefe ulaşmasını engelleyen onlar değildir.

Şekil 4.4.6'daki kesimde B→C kenarı da kesik çizgiyi geçer, ama T tarafından T tarafına gider; iki ucu da T'dedir. Bu yüzden hesaba girmez. Benzer biçimde S→A kenarının iki ucu da S tarafındadır.

4.4.3.2Kesimden geçen net akış

Bir kesimden geçen net akış, S'den T'ye giden kenarlardaki akışların toplamından T'den S'ye giden kenarlardaki akışların toplamının çıkarılmasıyla bulunur:

f(S, T) = Σ_{u ∈ S, v ∈ T} f(u, v) − Σ_{u ∈ S, v ∈ T} f(v, u)

Kapasitenin aksine net akışta geri yöndeki kenarlar da hesaba girer, çünkü geri dönen akış karşıya geçen akıştan düşülmelidir.

Teoremin söylediği şey sezgiye uygundur. Kaynaktan çıkan bütün akış hedefe varmak için kesimi bir yerde geçmelidir. Geri dönen akış olursa, o da en az bir kez daha ileri geçmek zorundadır. Sonunda kesimden geçen net miktar, ağa gönderilen miktara eşittir. Şekil 4.4.2'deki akışı {S, A} kesiminde sınayalım: ileri kenarlar A→B (4) ve S→C (3), geri kenar yok; net akış 7'dir. {S, C} kesiminde ileri kenarlar S→A (4) ve C→D (5), geri kenar B→C (2); net akış 4 + 5 − 2 = 7'dir. İki kesim farklı, net akış aynıdır.

Teoremin ikinci yarısı, her kesimin her akış için bir üst sınır olduğunu söyler. Herhangi bir akışın değeri, herhangi bir kesimin kapasitesini aşamaz. Öyleyse maksimum akış da minimum kesimin kapasitesini aşamaz. Bu bir eşitsizliktir. Asıl sürpriz, bu eşitsizliğin her zaman eşitlik olmasıdır.

4.4.3.3Maksimum akış minimum kesim teoremi

Teoremin üç ayrı yararı vardır. Birincisi, artış yolu tabanlı algoritmaların doğruluğunu kanıtlar: yol kalmadığında durmak güvenlidir. İkincisi, bir akışın maksimum olduğunu kolayca denetlenebilen bir sertifika verir. Değeri bir kesimin kapasitesine eşit olan akış, başka hiçbir hesap yapmadan maksimumdur. Üçüncüsü, minimum kesimi bulmanın yolunu gösterir: son artık ağda kaynaktan ulaşılabilen düğümler S tarafını oluşturur.

Örnek ağımızda bulunan akışın değeri 7'dir ve {S} kesiminin kapasitesi de 7'dir. Teoremin üçüncü maddesi sağlanır; akış maksimumdur. Örnek 4.4.2'de kurulan artık ağda kaynaktan hiçbir yere gidilemiyordu. Ulaşılabilen küme yalnızca {S}'dir ve ispattaki kesim tam olarak budur.

4.4.3.4Minimum kesimi bulmak

Teoremin ispatı aynı zamanda bir algoritmadır. Maksimum akış bulunduktan sonra son artık ağda kaynaktan bir arama yapılır. Ziyaret edilen düğümler S tarafıdır. Bir ucu ziyaret edilmiş, öbür ucu edilmemiş özgün kenarlar minimum kesimin kenarlarıdır. Aşağıdaki Java metodu bu işi yapar. Metot, artık kapasiteleri tutan artik matrisini ve özgün kapasitelerin bir kopyasını kullanır.

List<int[]> minKesim(int kaynak, int[][] kapasite) {
  boolean[] ziyaret = new boolean[V];
  Queue<Integer> kuyruk = new LinkedList<>();
  kuyruk.add(kaynak);
  ziyaret[kaynak] = true;
  while (!kuyruk.isEmpty()) {          // son artık ağda BFS
    int u = kuyruk.poll();
    for (int v = 0; v < V; v++)
      if (!ziyaret[v] && artik[u][v] > 0) {
        ziyaret[v] = true;
        kuyruk.add(v);
      }
  }
  List<int[]> kesim = new ArrayList<>();
  for (int u = 0; u < V; u++)          // S'den T'ye giden özgün kenarlar
    for (int v = 0; v < V; v++)
      if (ziyaret[u] && !ziyaret[v] && kapasite[u][v] > 0)
        kesim.add(new int[]{u, v});
  return kesim;
}

Metodun ilk yarısı sıradan bir BFS'dir. Tek fark, kenarın varlığının artik[u][v] > 0 ile sınanmasıdır: arama yalnızca artık ağda dolaşır. İkinci yarı bütün düğüm çiftlerini tarar ve ziyaret[u] doğru, ziyaret[v] yanlış olan çiftlerden özgün ağda kenar bulunanları listeye ekler. Kapasite koşulu önemlidir. Ters kenarlar artık matrisinde yer kaplar, ama özgün ağda yoktur; kesim kenarı olamazlar.

Komşu matrisiyle BFS O(V²), çift taraması da O(V²) sürer. Toplam süre O(V²)'dir; bu, maksimum akışı bulmanın maliyetinin yanında önemsizdir. Ek bellek ziyaret dizisi, kuyruk ve sonuç listesi için O(V + k)'dir; k kesimdeki kenar sayısıdır. Metot, ileride Ford-Fulkerson'ın ikinci örneğinin son artık ağında çalıştırıldığında S→1 (10) ve 3→4 (9) kenarlarını döndürür. Toplam 19, o ağdaki maksimum akışa eşittir.

4.4.3.5Ağ akış algoritmalarına genel bakış

Maksimum akışı bulan algoritmaların hepsi aynı amaca, aynı kavramlarla ulaşır. Farkları, akışı hangi sırayla ve hangi parçalar hâlinde büyüttükleridir. Tablo 4.4.2 notta ele alınan dört algoritmayı özetler.

İlk üç algoritma artış yolu düşüncesine dayanır ve her adımda geçerli bir akış tutar. Dördüncüsü farklıdır: ara adımlarda korunumu geçici olarak bozar ve en sonda düzeltir. Tablodaki yıllar da ilginç bir ayrıntı taşır. Dinic'in algoritması Edmonds-Karp'tan önce, 1970'te Sovyetler Birliği'nde yayımlanmıştır; iki çalışma birbirinden bağımsızdır.

4.4.4Ford-Fulkerson yöntemi

4.4.4.1Yöntemin fikri

Ford-Fulkerson yöntemi L. R. Ford Jr. ve D. R. Fulkerson'ın 1956'da yayımladığı çalışmaya dayanır. Kapasiteli yönlü bir çizgede iki düğüm arasındaki maksimum akışı bulur. Fikir şimdiye kadar kurulan kavramların doğal sonucudur: akış sıfırdan başlar, artık ağda bir artış yolu bulundukça akış o yol boyunca darboğaz kadar artırılır. Yol kalmadığında döngü durur; maksimum akış minimum kesim teoremi sonucun en iyi olduğunu garanti eder.

Ford-Fulkerson'a çoğu kaynakta “algoritma” yerine yöntem denir. Bunun nedeni, artış yolunun nasıl bulunacağını belirtmemesidir. Herhangi bir yol kabul edilir. Yolu DFS ile arayan sürüm genellikle Ford-Fulkerson adıyla anılır; BFS ile arayan sürümün ayrı bir adı vardır: Edmonds-Karp. Yol seçiminin sonuca değil, süreye etki ettiği bu iki sürümün karşılaştırmasında açıkça görülecek.

4.4.4.2Algoritma adımları

1. Başlangıç. Bütün kenarlarda f(u, v) = 0. Akış sıfır olduğu için her kenarın artık kapasitesi kendi kapasitesidir; artık ağ özgün ağın aynısıdır.
2. Yol arama. Artık ağda kaynaktan hedefe bir artış yolu p aranır. Yalnızca c_f > 0 olan kenarlar kullanılır.
3. Darboğaz. δ = min c_f(u, v), (u, v) ∈ p hesaplanır. Yol boyunca gönderilebilecek en fazla akış budur.
4. Artırma. Yol boyunca δ kadar akış gönderilir: ileri kenarlarda f(u, v) += δ, ters kenarlarda f(v, u) −= δ; |f| += δ. Yoldaki en az bir kenar doyar.
5. Tekrar. Artış yolu kalmayana kadar 2–4. adımlar tekrarlanır. Döngü bittiğinde |f| maksimumdur.

Uygulamada akış ve artık kapasite ayrı ayrı tutulmak zorunda değildir. Yalnızca artık kapasiteler saklanabilir. Akış eklenirken ileri kenarın artık kapasitesi δ azalır, ters kenarınki δ artar. Bir kenarın akışı gerektiğinde f(u, v) = c(u, v) − c_f(u, v) ile geri hesaplanır. Sunumdaki Java kodları bu yolu izler.

4.4.4.3Örnek 1: adım adım

Yöntemi Şekil 4.4.1'deki ağda çalıştıralım. Başlangıçta bütün akışlar sıfırdır ve artık ağ özgün ağla aynıdır. Yolların bu örnekteki sırası, her seferinde kenar sayısı en az olan yolu seçen bir aramanın vereceği sıradır. Ford-Fulkerson herhangi bir yolu kabul ettiği için bu sıra geçerlidir.

Birinci artış. p = S → A → B → T. Artık kapasiteler 4, 4 ve 2'dir; darboğaz 2 birimdir ve B→T'den gelir. Yol boyunca 2 birim gönderilir: |f| = 2. B→T doyar. Artık ağda S→A ve A→B'de 2'şer birim kalır ve karşı yönlerinde 2'şer birimlik ters kenarlar doğar.

İkinci artış. p = S → C → D → T. Artık kapasiteler 3, 6 ve 6'dır; darboğaz 3'tür. |f| = 2 + 3 = 5. S→C doyar. C→D ve D→T'de 3'er birim kalır.

Üçüncü artış. S'den çıkan tek artık kenar S→A'dır (2 birim). A'dan B'ye 2 birim gidilebilir. B→T doymuştur, ama B→C boştur (3 birim). C→D ve D→T'de 3'er birim vardır. Yol p = S → A → B → C → D → T, darboğaz min(2, 2, 3, 3, 3) = 2'dir. |f| = 7.

Üçüncü artıştan sonra S'den çıkan iki kenar da doymuştur. Artık ağda kaynaktan hiçbir yere gidilemez; döngü biter.

Son akış Şekil 4.4.2'deki akışın aynısıdır: B→C'de 2, C→D'de 5 birim. Bu bir rastlantıdır. Maksimum akışın değeri tektir, kenarlara dağılımı ise tek olmak zorunda değildir. Aynı ağda B→T'de 1, B→C'de 3, C→D ve D→T'de 6'şar birim taşıyan akış da geçerlidir ve değeri yine 7'dir. Değişmeyen tek şey, kaynaktan çıkan iki kenarın doymuş olmasıdır; minimum kesim {S} bunu zorunlu kılar.

4.4.4.4Örnek 2: ters kenarın kullanılması

İlk örnekte hiçbir artış yolu ters kenar kullanmadı. Ters kenarın neden gerekli olduğunu görmek için biraz daha büyük bir ağ gerekir. Şekil 4.4.10'daki ağda kaynak S, hedef T'dir; ara düğümler 1'den 4'e kadar numaralıdır.

Bu kez yolların sırası bilerek kötü seçilmiştir: ilk yol, sonradan düzeltilmesi gereken bir karar verir.

1. p = S → 1 → 4 → T: artık kapasiteler 10, 8, 10; darboğaz 1 → 4 (8). |f| = 8.
2. p = S → 3 → 4 → T: 4 → T'de yalnızca 10 − 8 = 2 birim kalmıştır. Darboğaz 2; |f| = 10. 4 → T doyar.
3. p = S → 3 → 4 → 1 → 2 → T: 3 → 4'te 9 − 2 = 7, 4 → 1 ters kenarında 8 (birinci adımda 1 → 4'e gönderilen akış), 1 → 2'de 4, 2 → T'de 10 birim vardır. Darboğaz 4; |f| = 14.
4. p = S → 1 → 4 → 2 → T: S → 1'de 2 birim kalmıştı. 1 → 4'te artık 8 − 4 = 4 birim boşluk vardır. Darboğaz 2; |f| = 16.
5. p = S → 3 → 4 → 2 → T: darboğaz 3 → 4'tür (9 − 6 = 3 kaldı). |f| = 19.

Üçüncü adım örneğin kalbidir. 4 → 1 ters kenarı kullanıldığında 1 → 4'teki akış 8'den 4'e düşer. Bunun anlamı şudur: daha önce 1'den 4'e giden 4 birim, artık 4'e 3'ten gelir. 1'de serbest kalan 4 birim ise 1 → 2 üzerinden hedefe yönlenir. Hiçbir düğümde korunum bozulmaz. 4'e giren toplam akış ve 1'den çıkan toplam akış değişmez; yalnızca yolları değişir.

Son artık ağda S → 1 doymuştur; S → 3'te 1 birim kalmıştır, ama 3'ten çıkan tek kenar olan 3 → 4 doymuştur. Kaynaktan ulaşılabilen küme {S, 3}'tür. Bu kümeden çıkan özgün kenarlar S → 1 ve 3 → 4'tür; ikisi de doludur. 1 → 3 kenarı T tarafından S tarafına gider ve üzerinde akış yoktur. Bu, ispattaki koşulların tam bir örneğidir: ileri kenarlar dolu, geri kenarlar boş.

4.4.4.5Ters kenarlar neden gerekli?

Aynı ağda ters kenarları hiç kullanmayan açgözlü bir yöntem düşünelim. Bu yöntem yalnızca dolu olmayan ileri kenarlardan geçen yollar arar.

Kayıp tek bir birimdir, ama ilke önemlidir. İlk yol 1 → 4 kenarına 8 birim yükledi. Bu akışın bir kısmı aslında 1 → 2 üzerinden gitmeliydi, böylece 3 → 4 kenarına yer açılırdı. İleri kenarlarla çalışan yöntem bu kararı geri alamaz. Ters kenarlı artık ağda ise 4 → 1 kenarı bu kararın bir kısmını geri almayı sağlar: 1'den gelen akış 2'ye, 3'ten gelen akış 4'e yönlenir. Sonuç 19'dur ve min kesime eşittir. Bunun genel bir kuralı vardır: ters kenarlı artık ağda yollar hangi sırayla seçilirse seçilsin, yöntem maksimuma ulaşır.

4.4.4.6Sözde kod

Yöntemin sözde kodu aşağıdadır. Burada akış değerleri ayrı bir akış tablosunda tutulur ve artık kapasite gerektiğinde kapasite − akış ile hesaplanır.

FORD_FULKERSON(G, kaynak, hedef):
  akış[u, v] = 0, her bir (u, v) için E içinde     // başlangıçta 0
  maksimumAkış = 0
  döngü artırıcı yol var iken:
    yol = DFS(G, kaynak, hedef, akış)            // c − akış > 0 kenarlarla
    delta = ∞                                    // yoldaki en küçük kalan kapasite
    v = hedef
    döngü v ≠ kaynak iken:
      u = yol.ata[v]
      delta = min(delta, kapasite[u, v] − akış[u, v])
      v = u
    v = hedef                                    // yoldaki akışları güncelle
    döngü v ≠ kaynak iken:
      u = yol.ata[v]
      akış[u, v] += delta
      akış[v, u] −= delta                        // ters kenar
      v = u
    maksimumAkış += delta
  döndür maksimumAkış, akış

Dış döngü bir artış yolu bulunduğu sürece döner. DFS çağrısı artık kapasitesi pozitif kenarlarla bir yol arar ve yolu, her düğümün bir önceki düğümünü tutan ata dizisiyle bildirir. Yolun kendisi bir liste olarak saklanmaz; hedeften kaynağa doğru ata izlenerek geri okunur.

İlk iç döngü darboğazı bulur. v hedeften başlar; her adımda u = yol.ata[v], yani v'ye gelinen düğümdür. delta, o ana kadar görülen en küçük artık kapasiteyle sınırlanır. Döngü kaynağa ulaşınca biter. İkinci iç döngü aynı yolu bir kez daha yürür ve akışı günceller: ileri yönde delta eklenir, ters yönde çıkarılır. Ters yöndeki çıkarma, akışı ters simetrik bir tabloda tutmanın sonucudur: akış[v, u] = −akış[u, v]. Bu gösterimde ters kenarın artık kapasitesi kapasite[v, u] − akış[v, u] = 0 − (−akış[u, v]) = akış[u, v] olur; tanımdaki değerin aynısı.

Bu ters simetrik gösterim kodu sadeleştirir. Ayrı bir “ters kenar mı?” sorusu sormaya gerek kalmaz; ileri ve ters kenarlar aynı formülle işlenir. Bir ayrıntı vardır: iki düğüm arasında iki yönde de özgün kenar varsa (örneğin hem 1 → 2 hem 2 → 1), iki kenarın akışları aynı hücrede birbirini götürebilir. Matris gösteriminde bu durum sorun çıkarmaz, çünkü yalnızca net akış önemlidir.

4.4.4.7Java: DFS ile artış yolu

Sunumdaki Java uygulaması artık kapasiteleri artik[u][v] matrisinde tutar. Başlangıçta bu matris kapasitelerle doldurulur; ters kenarların artık kapasitesi sıfırdır. Artış yolunu bulan DFS şöyledir:

boolean dfs(int u, int hedef,
            boolean[] ziyaret, int[] ata) {
  ziyaret[u] = true;
  if (u == hedef) return true;
  for (int v = 0; v < V; v++) {
    if (!ziyaret[v] && artik[u][v] > 0) {
      ata[v] = u;
      if (dfs(v, hedef, ziyaret, ata))
        return true;
    }
  }
  return false;   // bu daldan hedefe yol yok
}

Metot dört parametre alır: şu anki düğüm u, hedef, ziyaret işaretleri ve yolu kaydeden ata dizisi. İlk satır u'yu ziyaret edilmiş olarak işaretler. Böylece aynı düğüme bir daha girilmez ve arama döngüye düşmez. u hedefse yol bulunmuştur ve true döner.

Döngü bütün düğümleri sırayla dener; komşu matrisinde “komşu” demek, artik[u][v] > 0 olan v demektir. Ziyaret edilmemiş ve artık kapasitesi pozitif bir komşu bulununca ata[v] = u yazılır ve arama v'den sürer. Özyinelemeli çağrı true dönerse bu true hemen yukarı iletilir; döngünün geri kalanı denenmez. Bütün komşular denenip hedefe varılamazsa metot false döner: bu daldan hedefe yol yoktur.

Ziyaret işaretleri geri dönüşte silinmez. Bu önemlidir. Bir düğümden hedefe yol yoksa, o düğüme başka bir yoldan gelmek de sonucu değiştirmez; düğümü bir daha denemek boşa iştir. Bu sayede her düğüm en fazla bir kez ziyaret edilir. Komşu matrisinde her ziyaret V hücreyi tarar; bir DFS O(V²) sürer. Komşu listesiyle aynı arama O(V + E) sürer.

Akış eklenirken artik[u][v] −= d ve artik[v][u] += d yapılır. Ters kenar ayrıca oluşturulmaz; ikinci satır onu kendiliğinden doğurur. DFS bir sonraki çağrıda bu hücreyi pozitif görür ve ters kenarı sıradan bir kenar gibi kullanır. Kodun ters kenarları “bildiği” tek yer bu atamadır.

4.4.4.8Kod izleme: ölü uç ve ters kenar

Kodu Şekil 4.4.1'deki ağda çalıştıralım. Düğüm sırası S, A, B, C, D, T (indisler 0'dan 5'e) olsun; DFS komşuları bu sırayla dener. Bu sıra Örnek 1'deki yollardan farklı yollar üretir. İlk DFS S → A → B → C → D → T yolunu bulur (darboğaz 3). İkinci DFS'de B → C doymuştur ve S → A → B → T yolu 1 birim taşır. İki artıştan sonra |f| = 4'tür. Üçüncü aramayı ayrıntılı izleyelim.

Dördüncü adımdaki ölü uç DFS'nin karakteristik davranışıdır. A'ya bir ters kenarla gelinmiştir, ama A'dan hedefe giden bir artık yol yoktur. A'nın tek pozitif artık kenarı kaynağa geri döner, kaynak da zaten ziyaret edilmiştir. Arama A'yı terk eder ve B'de kaldığı yerden devam eder. ata[A] = B kaydı silinmez, ama zararsızdır: yol hedeften geriye okunurken A'ya hiç uğranmaz.

Yol hedeften geriye okunur: ata[T] = B, ata[B] = C, ata[C] = S. Yol S → C → B → T'dir. Darboğaz min(3, 3, 1) = 1'dir. Bu artış C → B ters kenarını kullanır: B → C'deki akış 3'ten 2'ye iner. Anlamı şudur: B'den C'ye giden akışın bir birimi artık B → T üzerinden doğrudan hedefe gider; C'nin eksilen girişini kaynaktan gelen yeni birim karşılar.

Dördüncü DFS S → C → D → T yolunu bulur ve 2 birim ekler. |f| = 7 olur. Beşinci DFS kaynaktan hiçbir yere gidemez ve false döner. Bu sürüm 4 artış yapar, Örnek 1'deki sıra ise 3 artış yapmıştı. İki sürümün son akışı aynıdır: Şekil 4.4.2'deki akış.

4.4.4.9Karmaşıklık ve tam sayılılık

Ford-Fulkerson'ın çalışma süresi ağın yapısına ve kapasitelere bağlıdır. Her tur iki parçadan oluşur. Bir artış yolu bulmak (DFS ya da BFS) ve akışı güncellemek O(E) sürer; komşu listesi varsayılır. Asıl soru tur sayısıdır.

Tam sayılılık özelliğinin önemli bir uygulaması vardır. Eşleştirme gibi problemlerde her kenar ya kullanılır ya kullanılmaz; yarım kenar anlamsızdır. Kapasiteler 1 olarak kurulursa teorem, maksimum akışın her kenarda 0 ya da 1 olduğunu garanti eder. Böylece akış doğrudan bir seçim olarak okunabilir.

Sınırın bir kusuru vardır: O(E · |f*|) polinom değildir. Bir algoritmanın süresi girdinin uzunluğuyla, yani girdiyi yazmak için gereken bit sayısıyla ölçülür. Kapasite 10⁹ yaklaşık 30 bitle yazılır, ama |f*| bu sayının kendisi kadar büyüyebilir. Bu tür sınırlara sözde polinom sınır denir. Kapasiteler küçük tam sayılarsa sorun yoktur. Büyük kapasitelerde ise yöntem, yolu kötü seçerse çok yavaşlayabilir.

Kapasiteler irrasyonel sayılar olabilirse durum daha da kötüdür. Bilinen örneklerde kötü seçilmiş yollarla artışlar giderek küçülür ve yöntem hiç sonlanmaz; hatta akış değeri maksimum akışa da yakınsamaz. Bilgisayarlarda kapasiteler sonlu duyarlıkla saklandığı için bu durum pratikte görülmez. Ama yöntemin “herhangi bir yol” özgürlüğünün bedeli olarak akılda tutulmalıdır.

4.4.4.10Kötü yol seçimi

Şekil 4.4.15'teki ağda maksimum akış 2000'dir: s → a → t ve s → b → t yollarının her biri 1000 birim taşır. İki artış yeterlidir. Şimdi kötü bir yol seçimini düşünelim. İlk yol s → a → b → t olsun. Ortadaki kenar yüzünden darboğaz 1'dir. Bu artış b → a ters kenarını doğurur. İkinci yol s → b → a → t olsun; ters kenar yüzünden darboğaz yine 1'dir ve a → b yeniden boşalır. Bu iki yol sırayla seçilmeye devam edilirse her artış yalnızca 1 birim ekler. Maksimuma ulaşmak için 2000 artış gerekir.

Kapasiteler 10⁹ olsaydı aynı seçim 2 · 10⁹ artış gerektirirdi. Oysa ağ yalnızca dört düğüm ve beş kenarlıdır. DFS bu kötü seçimi her zaman yapmaz. Örneğin komşuları indis sırasıyla deneyen DFS bu ağda 4 artışla biter: önce s → a → b → t (1), sonra s → a → t (999), s → b → a → t (1) ve s → b → t (999). Ama DFS'nin kötü seçimi yapmasını engelleyen hiçbir kural yoktur. Bu yüzden süre sınırı O(E · |f*|) olarak kalır.

Edmonds-Karp, yani BFS ile çalışan sürüm, en kısa yolları seçer. Bu ağda en kısa yollar iki kenarlıdır: s → a → t ve s → b → t. Her biri 1000 birim taşır; 2 artış yeter. Üç kenarlı ortadaki yol hiç seçilmez. BFS'nin kapasitelerin büyüklüğüne bağımlılığı nasıl kaldırdığı bir sonraki kesimin konusudur.

4.4.5Edmonds-Karp algoritması

4.4.5.1Fikir: en kısa artış yolu

Edmonds-Karp algoritması, Ford-Fulkerson yönteminin bir türevidir. Jack Edmonds ve Richard Karp 1972'de yayımlamıştır; Dinic aynı düşünceye 1970'te bağımsız olarak ulaşmıştır. Algoritma yöntemin tek serbest kararını sabitler: artış yolu genişlik öncelikli aramayla bulunur. BFS kaynaktan katman katman ilerlediği için hedefe ilk ulaştığı yol, kenar sayısı en az olan yoldur. Edmonds-Karp her turda bu en kısa artış yolunu seçer.

Burada “kısa” kenar sayısı anlamındadır, kapasite ya da ağırlık anlamında değil. Kenarların kapasitesi yol uzunluğunu etkilemez. Bu seçim ilk bakışta keyfî görünebilir. Ama kötü yol seçimi örneğindeki sorunun kökü, uzun ve dar bir yolun tekrar tekrar seçilmesiydi. En kısa yolları seçmek bu tür kısır döngüleri engeller. Algoritmanın adımları şöyledir:

1. BFS ile artık ağda kaynaktan hedefe en kısa artış yolu bulunur.
2. Yol boyunca darboğaz kadar akış gönderilir, ters kenarlar güncellenir.
3. BFS hedefe ulaşamayana kadar bu iki adım tekrarlanır.

BFS'nin ağ akışında iki farklı kullanımı olduğunu baştan belirtmek yararlıdır. Edmonds-Karp BFS'yi doğrudan artış yolu bulmak için kullanır ve her BFS'den sonra tek bir yol işler. Dinic ise BFS'yi hedefin hâlâ ulaşılabilir olup olmadığını anlamak ve bir seviye çizgesi kurmak için kullanır; o çizgede birçok yolu birden işler.

4.4.5.2Karmaşıklık: O(V · E²)

Her tur bir BFS ve bir yol güncellemesinden oluşur: O(E). Edmonds-Karp'ın asıl katkısı, artış sayısının kapasitelerden bağımsız bir sınırı olmasıdır. Bu sınırın gerekçesi iki gözleme dayanır.

Artık ağda kaynaktan bir v düğümüne olan en kısa yolun kenar sayısına d(v) diyelim. Birinci gözlem: Edmonds-Karp çalıştıkça hiçbir düğümün d(v) değeri azalmaz. Bir artış, yoldaki bazı kenarları artık ağdan çıkarır ve bazı ters kenarları ekler. Eklenen her ters kenar, en kısa yol üzerindeki bir (u, v) kenarının tersidir; yani d(v) = d(u) + 1 olan bir çiftte v'den u'ya gider. Böyle bir kenar uzaklığı bir düğüm geriye götürür ve hiçbir yolu kısaltamaz.

İkinci gözlem: Bir artışta darboğazı belirleyen kenara kritik kenar denir; artıştan sonra artık ağdan çıkar. Her artışta en az bir kenar kritiktir. (u, v) kenarı kritik olduğunda d(v) = d(u) + 1'dir. Aynı kenarın yeniden artık ağa girmesi için bir artış yolunun (v, u) ters kenarını kullanması gerekir. O anda d'(u) = d'(v) + 1'dir. Uzaklıklar azalmadığı için d'(u) = d'(v) + 1 ≥ d(v) + 1 = d(u) + 2 olur. Demek ki u'nun uzaklığı, kenar iki kez kritik olana kadar en az 2 artar.

Sınırın anlamı kötü durum ağında açıkça görülür. Kapasiteler 1000 de olsa 10⁹ da olsa Edmonds-Karp 2 artışla biter. Süre artık |f*|'ye bağlı değildir; algoritma polinom zamanlıdır. Bedeli, her artışta tam bir BFS yapılmasıdır. Sınır kötümserdir: pratikte artış sayısı V · E'nin çok altında kalır. V = 6, E = 9 olan ağlarda sınır yaklaşık 27 artışa izin verir; bu notun örneklerinde artış sayısı 3 ile 4 arasındadır.

4.4.5.3Java: BFS ile artış yolu

Edmonds-Karp'ın Ford-Fulkerson'dan tek farkı yol arayan fonksiyondur; ana döngü aynıdır. BFS sürümü şöyledir:

boolean bfs(int kaynak, int hedef, int[] ata) {
  boolean[] ziyaret = new boolean[V];
  Queue<Integer> kuyruk = new LinkedList<>();
  kuyruk.add(kaynak);
  ziyaret[kaynak] = true;
  ata[kaynak] = -1;
  while (!kuyruk.isEmpty()) {
    int u = kuyruk.poll();
    for (int v = 0; v < V; v++)
      if (!ziyaret[v] && artik[u][v] > 0) {
        kuyruk.add(v);
        ata[v] = u;
        ziyaret[v] = true;
      }
  }
  return ziyaret[hedef];
}

Metot her çağrıda yeni bir ziyaret dizisi oluşturur. Kuyruk kaynakla başlar; kaynak ziyaret edilmiş sayılır ve ata[kaynak] = -1 yazılır. Bu −1 değeri, yolu geri okurken kaynağa varıldığını belirten bir işarettir. Döngüde kuyruğun başındaki düğüm u çıkarılır. Ardından bütün v'ler sırayla denenir. Ziyaret edilmemiş ve artik[u][v] > 0 olan her v kuyruğa eklenir, ebeveyni u olarak kaydedilir ve hemen ziyaret edilmiş işaretlenir.

İşaretin kuyruğa eklerken konması önemlidir. Düğüm kuyruktan çıkarken işaretlenseydi, aynı düğüm birkaç farklı ebeveynden kuyruğa girebilirdi. ata değeri de son ekleyen ebeveyne göre değişirdi ve BFS ağacı bozulurdu. Erken işaretleme, her düğümün tam bir kez ve kaynağa en yakın ebeveyninden kuyruğa girmesini sağlar.

Metot ziyaret[hedef] değerini döndürür: hedefe ulaşıldıysa bir artış yolu vardır. ata dizisi BFS ağacını tutar; hedeften kaynağa doğru izlenince en az kenarlı yol elde edilir. Bu kod hedefe ulaştığında durmaz, kuyruk boşalana kadar sürer. Sonuç değişmez, çünkü hedefin ebeveyni ilk ulaşıldığında yazılmıştır; erken durmak yalnızca biraz zaman kazandırır. Komşu matrisiyle bir BFS O(V²), komşu listesiyle O(V + E) sürer.

Ana döngü şöyledir:

int edmondsKarp(int s, int t) {
  int maksAkis = 0;
  int[] ata = new int[V];
  while (bfs(s, t, ata)) {
    int akis = Integer.MAX_VALUE;
    for (int v = t; v != s; v = ata[v])
      akis = Math.min(akis, artik[ata[v]][v]);
    for (int v = t; v != s; v = ata[v]) {
      int u = ata[v];
      artik[u][v] -= akis;  // ileri
      artik[v][u] += akis;  // ters
    }
    maksAkis += akis;
  }
  return maksAkis;
}

while (bfs(s, t, ata)) koşulu her turda yeni bir BFS çalıştırır. İlk for döngüsü hedeften kaynağa doğru yürür. ata[v] yolun bir önceki düğümüdür; artik[ata[v]][v] o kenarın artık kapasitesidir. akis bu değerlerin en küçüğüne iner. Başlangıç değeri Integer.MAX_VALUE'dir, böylece ilk karşılaştırma her zaman gerçek bir kenarın değerini alır. İkinci döngü aynı yolu bir kez daha yürür: ileri artık kapasiteden akis çıkarılır, ters artık kapasiteye akis eklenir. Tur sonunda maksAkis büyür. BFS hedefe ulaşamadığında döngü biter ve sonuç döndürülür.

Bellek kullanımı artik matrisi için O(V²), ata, ziyaret ve kuyruk için O(V)'dir. Matris seyrek ağlarda savurgandır. Büyük seyrek ağlarda komşu listesi ve her kenarın ters kenarına bir bağlantı tutulur; Dinic'in Java kodu bu gösterimi kullanır.

4.4.5.4Kod izleme: bfs(s, t, ata)

BFS'yi Şekil 4.4.17'deki ağda izleyelim. Bu ağ Cormen ve arkadaşlarının kitabındaki klasik örnektir. Düğümler s, 1, 2, 3, 4, t sırasıyla 0'dan 5'e numaralıdır; döngü komşuları bu sırayla dener. Başlangıçta bütün akışlar sıfırdır, artık kapasite kapasiteye eşittir.

Hedef, 3 kuyruktan çıktığında ziyaret edilir. Kod yine de kuyruk boşalana kadar sürer. Döngü bittiğinde ata dizisi [−1, s, s, 1, 2, 3]'tür. Hedeften geriye okununca yol s → 1 → 3 → t çıkar: yalnızca 3 kenar. Bu ağda 3'ten kısa bir s–t yolu yoktur; BFS en az kenarlı artış yolunu bulmuştur. Darboğaz min(16, 12, 20) = 12'dir.

4.4.5.5Kod izleme: edmondsKarp(s, t)

Ana döngünün tamamı Tablo 4.4.6'da görülür. Her tur için bulunan yol, darboğaz ve güncellenen artık kapasiteler verilmiştir.

Yol uzunlukları 3, 3 ve 4'tür; azalmaz. Bu, Edmonds-Karp'ın karmaşıklık ispatındaki birinci gözlemin küçük bir örneğidir. İkinci turdan sonra 4 → t doymuştur. Üçüncü turda 4'ten hedefe doğrudan gidilemez; BFS 4'ten 3'e geçen ve bir kenar daha uzun olan yolu bulur. Darboğaz 4 → 3'ün kapasitesi olan 7'dir.

Dördüncü BFS'de kaynaktan 1'e (artık 4) ve 2'ye (artık 2) gidilir. 1'den 3'e giden kenar doymuştur. 2'den 4'e 3 birim gidilebilir, ama 4'ün iki çıkışı (4 → 3 ve 4 → t) doludur. 3'e ve hedefe ulaşılamaz; ulaşılabilen küme {s, 1, 2, 4}'tür. Metot 23 döndürür. Algoritma 3 artış ve 4 BFS yapmıştır.

4.4.5.6Örnek: son akış ve minimum kesim

Aynı ağda akışın neden 23'te durduğunu kesimlerle doğrulayalım. Algoritma başlamadan önce bile basit bir üst sınır vardır. Kaynaktan çıkan kapasite 16 + 13 = 29, hedefe giren kapasite 20 + 4 = 24'tür. Küçüğü alınırsa |f*| ≤ 24. Bulunan değer 23'tür; bu sınırın bir altında. Darboğaz ne kaynakta ne hedeftedir; ağın ortasındadır.

Son akışın kenarlara dağılımına bakmak da öğreticidir. 1 → 2 ve 2 → 1 kenarlarında akış yoktur; bu iki kenar bu çözümde hiç kullanılmamıştır. s → 1'de 12, s → 2'de 11 birim vardır. Kaynak kenarlarında boş kapasite kalmasına rağmen akış artırılamaz, çünkü kesim kenarları doludur.

4.4.5.7Örnek 2: A–G ağı

İkinci örnek, BFS'nin uzun yollar bulmak zorunda kaldığı ve ters kenar kullandığı bir ağdır. Kaynak A, hedef G'dir. BFS komşuları alfabetik sırayla dener.

İlk turda BFS A'dan B ve D'yi, B'den C'yi, D'den E ve F'yi kuyruğa koyar. E, F'den önce kuyruktan çıkar ve G'yi ilk o bulur. Yol A → D → E → G'dir; E → G'nin kapasitesi 1 olduğu için yalnızca 1 birim taşır. İkinci turda E → G doludur. BFS A → D → F → G'yi bulur; A → D'de 2 birim kalmıştır. Akış 3 olur ve A → D doyar.

Üçüncü turda kaynaktan yalnızca B'ye çıkılabilir. Yol beş kenara uzar: A → B → C → D → F → G. Darboğaz C → D'dir (1). Dördüncü tur en ilginç olanıdır. C → D doymuştur; C'den E'ye gidilir. E'den hedefe doğrudan yol yoktur, ama ilk turda D → E'ye 1 birim gönderilmişti. Artık ağda E → D ters kenarı vardır ve yol onu kullanır: A → B → C → E → D → F → G.

Ters kenarın etkisi şudur: ilk turda D'den E'ye geçip E → G ile hedefe giden birim artık C'den gelir. D'de serbest kalan birim D → F → G üzerinden hedefe gider. Son akışta D → E kenarı boştur. Yol uzunlukları 3, 3, 5 ve 6'dır; yine azalmaz.

Beşinci BFS hedefe ulaşamaz. Kaynaktan A, B, C, E düğümlerine ulaşılır. Bu kümeden çıkan özgün kenarlar A → D (3), C → D (1) ve E → G (1)'dir. Kesim kapasitesi 3 + 1 + 1 = 5 = |f*|'dır. D → E kenarı kesimi ters yönde geçer ve son akışta boştur; ispattaki koşul yine sağlanır.

4.4.5.8Örnek 3: artık ağ üzerinde

Üçüncü örnekte algoritma doğrudan artık ağ üzerinde izlenir. Her artışın artık ağı nasıl değiştirdiği adım adım görülür.

Başlangıçta artık ağ kapasitelerle aynıdır. BFS önce iki kenarlı s → 4 → t yolunu bulur. Darboğaz s → 4'tür (2); 2 birim itilir. s → 4'ün artık kapasitesi 0'a iner, 4 → s ters kenarı 2 olur. 4 → t'de 1 birim kalır.

Artık iki kenarlı yol yoktur. BFS üç kenarlı s → 1 → 2 → t yolunu bulur; darboğaz 2 → t'dir (3). 3 birim itilir. s → 1'de 1, 1 → 2'de 1 birim kalır; 2 → t doyar. Sonraki BFS'de 2'den hedefe gidilemez. s → 1 → 3 → t yolu bulunur; s → 1'de 1 birim kaldığı için 1 birim itilir.

Kaynaktan çıkan kenarlar doymuştur; artış yolu kalmamıştır. Maksimum akış |f*| = 2 + 3 + 1 = 6'dır: 3 birim s → 1 → 2 → t, 1 birim s → 1 → 3 → t, 2 birim s → 4 → t üzerinden gider. Minimum kesim ({s}, diğerleri)'dir ve kapasitesi 4 + 2 = 6'dır. Bu ağda {s, 1, 2, 3} kümesi de 6 kapasiteli bir kesim verir; minimum kesim yine tek değildir.

Bu örnekte hiçbir yol ters kenar kullanmamıştır. Bazı kenarlar da hiç dolmamıştır: 3 → 2 ve 4 → 3 boş kalır, 4 → t'de 1 birim boşluk vardır. Maksimum akış her kenarı doldurmaz; yalnızca bir minimum kesimin kenarlarını doldurur.

4.4.6Dinic algoritması

Edmonds-Karp her BFS'den sonra tek bir yol işler. Oysa BFS'nin bulduğu bilgi tek bir yoldan çok daha zengindir: kaynaktan her düğüme olan uzaklığı verir. Bu uzaklıklar kullanılarak aynı uzunluktaki bütün en kısa yollar tek bir aşamada doyurulabilir. Yefim Dinitz 1970'te yayımladığı algoritmada bu fikri kullanmıştır; algoritma Batı literatüründe Dinic adıyla tanınır.

4.4.6.1Seviye çizgesi ve engelleyici akış

Seviye çizgesinde her kenar bir seviye ileri gider. Aynı seviyedeki düğümler arasındaki kenarlar ve geri giden kenarlar atılır. Bu yüzden seviye çizgesindeki her s–t yolu, artık ağdaki en kısa s–t yollarından biridir. Üstelik seviye çizgesi döngüsüzdür: seviye her adımda artar, aynı düğüme geri dönülemez.

Engelleyici akış maksimum akış değildir. Yalnızca seviye çizgesindeki yolların hepsini tıkar; seviye çizgesinde artık s–t yolu kalmaz. Ama artık ağın tamamında, seviye atlamayan kenarlar ve yeni doğan ters kenarlar üzerinden daha uzun artış yolları kalabilir. Dinic bu yüzden fazlar hâlinde çalışır: her fazda seviyeleri yeniden hesaplar ve yeni bir engelleyici akış bulur.

4.4.6.2Algoritma adımları

1. Başlangıç. Bütün kenarların akışı 0'dır; artık ağ özgün ağla aynıdır.
2. BFS. Kaynaktan BFS ile her düğümün seviyesi belirlenir. BFS yalnızca artık kapasitesi pozitif kenarları kullanır. Hedefin seviyesi yoksa, yani hedefe ulaşılamıyorsa, akış maksimumdur ve algoritma durur.
3. DFS. Her adımda bir seviye ileri giden artış yolları DFS ile aranır. Yalnızca seviye(v) = seviye(u) + 1 olan kenarlar izlenir. Çıkmaz olduğu anlaşılan kenarlar o faz boyunca bir daha denenmez.
4. Güncelleme. Bulunan her yoldaki en küçük artık kapasite toplam akışa eklenir; kenarların ve ters kenarlarının artık kapasiteleri güncellenir. Yol kalmayınca bu fazın engelleyici akışı bulunmuş olur.
5. Yeni faz. 2. adıma dönülür.

Her fazda kaynaktan hedefe olan uzaklık en az 1 artar. Uzaklık en fazla V − 1 olabileceğinden en fazla V − 1 faz vardır. Bu, algoritmanın süre sınırındaki ilk çarpandır.

4.4.6.3Örnek: fazlar

Algoritmayı Şekil 4.4.25'teki ağda çalıştıralım. Bu ağ, Ford-Fulkerson'ın ikinci örneğindeki ağın aynısıdır; yalnızca 2 ve 3 numaralı düğümlerin adları yer değiştirmiştir. Dolayısıyla maksimum akışın 19 olduğunu biliyoruz.

Faz 1, BFS. Seviyeler: s = 0; 1, 2 = 1; 3, 4 = 2; t = 3. 1 → 2 kenarı iki seviye-1 düğümünü, 4 → 3 kenarı iki seviye-2 düğümünü bağlar. İkisi de seviye atlamaz ve bu fazda kullanılmaz. Kaynaktan hedefe uzaklık 3'tür.

Faz 1, engelleyici akış. DFS seviye çizgesinde üç yol bulur: {s, 1, 3, t} 4 birim (1 → 3'ün kapasitesi), {s, 1, 4, t} 6 birim (s → 1'de kalan), {s, 2, 4, t} 4 birim (4 → t'de kalan). Toplam |f| = 14. Bu fazdan sonra seviye çizgesinde s–t yolu kalmaz: s → 1, 1 → 3 ve 4 → t doymuştur.

Faz 2, BFS. Artık ağda kaynaktan yalnızca 2'ye çıkılabilir (s → 2'de 6 birim kaldı). 2'den 4'e 5 birim gidilir. 4'ten iki yöne gidilebilir: 4 → 3 kenarı ve birinci fazda 1 → 4'e gönderilen akışın ters kenarı 4 → 1. 3'ten de hedefe gidilir. Seviyeler: s = 0; 2 = 1; 4 = 2; 1, 3 = 3; t = 4. Kaynaktan hedefe uzaklık 3'ten 4'e çıkmıştır.

Faz 2, engelleyici akış. DFS önce 4'ten 1'e iner. 1'in seviye 4'teki bir düğüme kenarı yoktur; 4 → 1 kenarı çıkmaz sokaktır. DFS bu kenarı bırakır ve 4 → 3 → t ile devam eder. Yol {s, 2, 4, 3, t}, darboğaz 2 → 4'tür (9 − 4 = 5). |f| = 14 + 5 = 19.

Faz 3, BFS. Artık ağda kaynaktan yalnızca 2'ye ulaşılır (s → 2'de 1 birim kaldı); 2 → 4 doymuştur. Hedefin seviyesi yoktur, algoritma biter. Minimum kesim ({s, 2}, diğerleri)'dir: s → 1 (10) + 2 → 4 (9) = 19.

Sonuç: maksimum akış 19'dur ve yalnızca 2 faz, yani 2 + 1 = 3 BFS yeterli olmuştur. Aynı ağda Ford-Fulkerson'ın ikinci örneği 5 artış yolu kullanmıştı. Edmonds-Karp bu ağda 4 artış ve 5 BFS yapar. Dinic'in kazancı, birinci fazda uzunluğu 3 olan üç yolu tek bir BFS'nin bilgisiyle işlemesinden gelir.

4.4.6.4Sözde kod

Dinic'in ana döngüsü ve BFS'si aşağıdadır.

DINIC(G, kaynak, hedef):
  akış = [ ]       // her kenar için 0
  maksimumAkış = 0
  döngü BFS(G, kaynak, hedef, akış) iken:
    // seviye çizgesi kuruldu
    döngü engelleyici akış var iken:
      delta = DFS(G, kaynak, hedef,
                  akış, seviye, ∞)
      maksimumAkış += delta
  döndür maksimumAkış

BFS(G, kaynak, hedef, akış):
  seviye[v] = −1, her v için
  seviye[kaynak] = 0
  kuyruk.ekle(kaynak)
  döngü kuyruk boş değil iken:
    u = kuyruk.çıkar()
    her bir (u, v) için G[u] içinde:
      eğer seviye[v] < 0 ve
           kapasite[u,v] − akış[u,v] > 0:
        seviye[v] = seviye[u] + 1
        kuyruk.ekle(v)
  döndür seviye[hedef] ≥ 0

Dış döngü BFS hedefe ulaştığı sürece döner; her tur bir fazdır. İç döngü, engelleyici akış tamamlanana kadar DFS'yi tekrar tekrar çağırır. Her DFS bir yol bulur ve o yolun akışını döndürür; 0 dönünce faz biter. BFS, Edmonds-Karp'taki BFS'ye çok benzer. Fark şudur: ebeveyn yerine seviye kaydedilir. Ulaşılmamış düğümlerin seviyesi −1'dir. BFS, hedefin seviyesi negatif değilse true döner.

DFS(G, u, hedef, akış, seviye, lim):
  eğer u == hedef: döndür lim
  her bir (u, v) için G[u] içinde:
    kalan = kapasite[u,v] − akış[u,v]
    eğer seviye[v] == seviye[u] + 1
         ve kalan > 0:
      delta = DFS(G, v, hedef, akış,
                  seviye, min(lim, kalan))
      eğer delta > 0:
        akış[u, v] += delta
        akış[v, u] −= delta   // ters
        döndür delta
  döndür 0

DFS'nin lim parametresi, kaynaktan u'ya kadar gelen yolun darboğazıdır. Kaynakta ∞ ile başlar ve her kenarda min(lim, kalan) ile küçülür. Hedefe ulaşınca bu değer döndürülür; bu yolun darboğazıdır. Dönüşte her kenar akışı delta kadar artırır, ters kenarınki azalır. Seviye koşulu (seviye[v] == seviye[u] + 1) aramanın yalnızca seviye çizgesinde ilerlemesini sağlar.

4.4.6.5Java: seviyeli DFS ve kaldığı yer dizisi

Sözde koddaki DFS her çağrıda bütün kenarları baştan dener. Bir kenarın çıkmaz olduğu anlaşılsa bile sonraki çağrıda yeniden denenir. Bu, fazın süresini gereksiz uzatır. Java uygulaması bunu küçük bir diziyle önler:

int dfs(int u, int t, int akis, int[] basla) {
  if (u == t) return akis;
  for (; basla[u] < komsu[u].size(); basla[u]++) {
    Kenar k = komsu[u].get(basla[u]);
    if (seviye[k.hedef] == seviye[u] + 1 && k.akis < k.kapasite) {
      int d = dfs(k.hedef, t, Math.min(akis, k.kapasite - k.akis), basla);
      if (d > 0) {
        k.akis += d;                                 // ileri kenar
        komsu[k.hedef].get(k.tersIndis).akis -= d;   // ters kenar
        return d;
      }
    }
  }
  return 0;   // u'dan t'ye seviyeli yol kalmadı
}

Kenarlar komşu listesinde tutulur. Her Kenar nesnesi hedef düğümü, kapasiteyi, akışı ve tersIndis alanını taşır. tersIndis, ters kenarın hedef düğümün listesindeki yeridir. Böylece komsu[k.hedef].get(k.tersIndis) ifadesi ters kenara O(1)'de ulaşır. Bir kenar eklenirken iki nesne birlikte oluşturulur: kapasiteli ileri kenar ve kapasitesi 0 olan ters kenar.

basla[u], u'da denenecek sıradaki kenarın indisidir; İngilizce kaynaklarda bu yapıya current arc denir. for döngüsü basla[u]'dan başlar ve sayaç doğrudan bu dizide artırılır. Bir kenardan hedefe akış ulaşmazsa (d == 0), döngü basla[u]++ ile sonraki kenara geçer ve bu kenar o faz boyunca bir daha denenmez. Akış ulaşırsa metot basla[u]'yu artırmadan döner. Kenarda hâlâ yer olabilir; bir sonraki çağrı aynı kenardan başlar.

Koşuldaki k.akis < k.kapasite, artık kapasitenin pozitif olduğunu söyler. Ters kenarlar için kapasite 0, akış ise negatiftir: −f. Koşul −f < 0, yani f > 0 olur ve artık kapasite 0 − (−f) = f çıkar. İleri ve ters kenarlar aynı satırla işlenir. Her fazın başında basla dizisi sıfırlanır ve seviyeler BFS ile yeniden hesaplanır.

4.4.6.6Kod izleme: birinci fazda engelleyici akış

Birinci fazdaki DFS çağrılarını izleyelim. Komşu listelerinde kenarlar eklenme sırasındadır: 1'in listesinde ters s kenarından sonra 1 → 2, 1 → 3, 1 → 4; 4'ün listesinde iki ters kenardan sonra 4 → 3 ve 4 → t gelir. Ters kenarlar bu fazda seviye koşulunu sağlamaz.

Dördüncü çağrı engelleyici akışın tamamlandığını gösterir. Bu çağrıda 4'ten seviyeli yol kalmamıştır: 4 → 3 aynı seviyededir, 4 → t doymuştur. 0 değeri yukarı doğru iletilirken her düğüm sayacını ilerletir. Sonunda basla[s] listenin sonuna ulaşır ve faz |f| = 14 ile biter.

Tabloda basla sayaçlarının toplam artış sayısı küçüktür: her kenar faz boyunca en fazla bir kez “çıkmaz” ilan edilir. Kaldığı yer dizisinin değeri buradadır. Çıkmaz bir kenara bir daha bakılmadığı için bir fazdaki bütün DFS çağrılarının toplam işi sınırlı kalır.

4.4.6.7Karmaşıklık: O(V² · E)

Dinic'in sınırı Edmonds-Karp'ınkiyle karşılaştırılınca kazanç açıktır. E ≥ V olan ağlarda V² · E ≤ V · E²'dir; ağ yoğunlaştıkça fark büyür. V = 1000, E = 10.000 için V · E² değeri 10¹¹, V² · E değeri 10¹⁰'dur.

Özel ağlarda sınır daha da iyidir. Bütün kapasiteler 1 ise faz sayısı O(√E) ile sınırlanır ve her faz O(E) sürer: toplam O(E · √E). İki parçalı eşleştirme gibi, her düğümden en fazla bir birim akışın geçtiği birim ağlarda süre O(E · √V)'ye iner. Bu, Hopcroft-Karp algoritmasının sınırıdır; Hopcroft-Karp aslında Dinic'in eşleştirmeye uyarlanmış bir biçimidir.

Pratikte Dinic, yarışma programlamada en çok kullanılan maksimum akış algoritmasıdır. Kodu kısadır ve genellikle sınırının çok altında çalışır. Faz sayısı çoğu ağda V'den çok küçüktür; bu notun örneğinde 2 faz yetmiştir.

4.4.7İtme–yeniden etiketleme

4.4.7.1Fikir: suyu yokuş aşağı akıtmak

Şimdiye kadarki algoritmaların hepsi bütünsel çalışır: her adımda kaynaktan hedefe tam bir yol arar. A. Goldberg ve R. Tarjan'ın 1988'de yayımladığı itme–yeniden etiketleme (push–relabel) algoritması bambaşka bir yol izler. Artış yolu aramaz. Her işlem tek bir düğüm ve onun komşularıyla ilgilidir; algoritma bu yerel işlemlerin tekrarıyla maksimum akışa ulaşır.

Algoritmayı bir su sistemi gibi düşünmek kolaylık sağlar. Başlangıçta kaynaktan çıkan bütün borular sonuna kadar doldurulur. Su, kaynağın komşularında birikir. Her düğümün bir yüksekliği (height) vardır ve su yalnızca yüksekten bir alçağa doğru akar. Birikmiş suyunu hiçbir komşusuna akıtamayan bir düğüm yükseltilir; buna yeniden etiketleme (relabel) denir. Suyun bir komşuya akıtılmasına ise itme (push) denir. Hedefe ulaşamayan fazla su, yükseklik kaynağın yüksekliğini geçince kaynağa geri döner. Hiçbir düğümde birikmiş su kalmayınca hedefe varmış su maksimum akıştır.

4.4.7.2Ön akış ve aşırı akış

Algoritmanın ara adımlarındaki yapı bir akış değildir; korunum kısıtı bozulur. Bir düğüme giren su çıkandan fazla olabilir. Bu gevşek yapıya ön akış denir.

Ön akışta korunum yalnızca bir yönde gevşetilmiştir: bir düğüm akış biriktirebilir, ama elinde olmayan akışı veremez. Aşırı akış hiçbir zaman negatif olmaz. Korunum, bütün ara düğümlerde e(v) = 0 olması demektir. Öyleyse aktif düğüm kalmadığında ön akış gerçek bir akışa dönüşür. Algoritma bu ana kadar çalışır.

4.4.7.3Yükseklik fonksiyonu ve başlangıç

Algoritma her düğüme bir h(v) tam sayısı atar. Başlangıç şöyledir:

• Bütün kenarların akışı 0'dır.
• h(s) = |V|, yani düğüm sayısı; diğer bütün düğümlerde h = 0'dır.
• Kaynaktan çıkan her kenar doldurulur: f(s, v) = c(s, v) ve e(v) = c(s, v).

Algoritma boyunca iki değişmez korunur. Birincisi, h(s) = |V| ve h(t) = 0 hiç değişmez; kaynak ve hedef etiketlenmez. İkincisi, artık ağdaki her (u, v) kenarı için h(u) ≤ h(v) + 1'dir. Bu ikinci değişmez, bir kenar boyunca yüksekliğin en fazla 1 düşebileceğini söyler. Yokuşlar dik olamaz.

İkinci değişmezin önemli bir sonucu vardır: h(u), u'dan hedefe artık ağ uzaklığının bir alt sınırıdır. u'dan hedefe k kenarlı bir artık yol varsa, her kenarda yükseklik en fazla 1 düşer; hedefin yüksekliği 0 olduğundan h(u) ≤ k olur.

Bu bakış açısı algoritmanın Ford-Fulkerson ailesine göre tersine işlediğini gösterir. Ford-Fulkerson her an geçerli bir akış tutar ve artış yolu kalmayana kadar çalışır. İtme–yeniden etiketleme ise her an “artış yolu yok” koşulunu tutar ve ön akış geçerli bir akış olana kadar çalışır. Başlangıç değeri h(s) = |V| bu koşulun kurulmasını sağlar. Kaynaktan çıkan kenarlar doldurulduğu için artık ağda kaynaktan çıkan kenar kalmaz; değişmez başlangıçta da doğrudur.

4.4.7.4İtme ve yeniden etiketleme işlemleri

İtme: push(u, v). Koşul üç parçalıdır: e(u) > 0; c_f(u, v) > 0, yani kenarda kapasite ile akış arasında fark vardır; ve h(u) = h(v) + 1. Bu koşullarda δ = min(e(u), c_f(u, v)) kadar akış itilir: f(u, v) artar (ya da ters kenarsa f(v, u) azalır), e(u) −= δ, e(v) += δ. Kenar bu itmeyle doyarsa doyuran itme, doymazsa doyurmayan itme denir. Doyurmayan itmede δ = e(u)'dur ve u'nun fazlası tamamen boşalır.

Yeniden etiketleme: relabel(u). Koşul: e(u) > 0, ama artık ağdaki her (u, v) kenarı için h(u) ≤ h(v); yani hiçbir komşuya itilemiyor. İşlem h(u) = 1 + min h(v)'dir; en küçük, artık ağdaki (u, v) kenarları üzerinden alınır. Bu yeni değerle en az bir itme mümkün olur: en alçak komşu tam bir basamak aşağıdadır.

Her iki işlem de değişmezleri korur. İtme yalnızca h(u) = h(v) + 1 olan bir kenarda yapılır. Yeni doğabilecek (v, u) ters kenarında h(v) = h(u) − 1 ≤ h(u) + 1 olur; değişmez sağlanır. Yeniden etiketlemede h(u), artık komşularının en küçüğünden tam bir fazla seçilir; u'dan çıkan kenarlarda değişmez korunur. u'ya giren kenarlarda ise h(u)'nun artması koşulu yalnızca gevşetir.

Akış yüksekten alçağa itilir ve yükseklikler yalnızca artar. Aşırı akışı olan bir düğümün artık ağda her zaman kaynağa giden bir yolu vardır: bu akış kaynaktan bir yoldan gelmiştir ve o yolun ters kenarları artık ağdadır. Bu yüzden yeniden etiketlemedeki min her zaman tanımlıdır. Hedefe ulaşamayan fazla, yüksekliği kaynağın yüksekliği olan |V|'yi aşınca kaynağa geri itilir.

4.4.7.5Örnek: adım adım

Şekil 4.4.31'deki ağda altı düğüm vardır: |V| = 6. Aktif düğümler istenen sırada seçilebilir; örnekteki sıra işlemleri açıkça göstermek için seçilmiştir.

İlk adımlar işlemlerin koşullarını gösterir. Birinci adımda B aktiftir, ama tek artık komşusu A aynı yüksekliktedir (0); kaynak ise çok yüksektedir. B itemez ve yeniden etiketlenir. Ardından A'ya bir basamak yukarıdan bakar ve B → A kenarının kapasitesi kadar, 3 birim iter. Üçüncü adımda A'nın komşuları C (0), t (0), B (1; B → A akışının ters kenarı) ve s (6; s → A akışının ters kenarı)'dir. En küçük 0'dır, h(A) = 1 olur.

Dördüncü adımda A fazlasını hedefe ve C'ye dağıtır. Hedefin kenarı 7'de, C'nin kenarı 6'da doyar. A'da 3 birim kalır. Bu 3 birimin hedefe ulaşma yolu yoktur: A'nın iki çıkışı da doludur. Sonraki adımların çoğu, bu fazlanın kaynağa geri dönmesidir.

Altıncı adımdan dokuzuncu adıma kadar olan bölüm algoritmanın en sık eleştirilen yönünü gösterir. A ile B fazlayı birbirine iter; her seferinde biri bir basamak yükselir. Bu “top oynama”, ikisinin yüksekliği kaynağın yüksekliği olan 6'yı geçene kadar sürer. h(B) = 7 olunca B kaynaktan yüksektir. B'nin 10 birimlik fazlasından 3'ü A'ya, 7'si kaynağa gider (s → B akışı 10'dan 3'e iner). Onuncu adımda A da 7'ye yükselir ve kendi 3 birimini kaynağa iter.

Sonraki adımlarda aynı şey C ile D arasında olur. C'nin 6 birimi D'ye gider; D bunun 5'ini hedefe iter, çünkü D → t'nin kapasitesi 5'tir. Kalan 1 birim C ile D arasında gidip gelir. Yükseklikler A'nın yüksekliği olan 7'yi geçince C, bu birimi A'ya iter (A → C akışı 6'dan 5'e iner); A da onu kaynağa iter.

Aktif düğüm kalmadığında maksimum akış hedefe giren akıştır: 7 + 5 = 12. Kaynaktan çıkan akış da 9 + 3 = 12'dir. Minimum kesim S = {s, A, B, C, D}, T = {t}'dir: A → t (7) + D → t (5) = 12.

Örnekteki seçim sırası tek seçenek değildir. Sunumdaki Java işlevleri, her turda indis sırasına göre ilk aktif düğümü seçen bir ana döngüyle de çalıştırılabilir. Bu döngü aynı ağda 38 işlem (yeniden etiketleme ve itme) yapar ve yine 12 bulur. Sıra işlem sayısını değiştirir, sonucu değiştirmez.

4.4.7.6Sözde kod

Algoritmanın başlangıç kısmı şöyledir:

PUSH_RELABEL(G, kaynak, hedef):
  yükseklik[kaynak] = |V|
  yükseklik[v] = 0, v ≠ kaynak
  aşırı[v] = 0, her v için
  akış[e] = 0, her kenar e için
  // ön akış: kaynak kenarlarını doldur
  her bir (kaynak, v) ∈ E için:
    c = kapasite[kaynak, v]
    akış[kaynak, v] = c
    akış[v, kaynak] = −c
    aşırı[v] = c
    aşırı[kaynak] −= c

Akış ters simetrik bir tabloda tutulur: kaynak kenarı doldurulurken akış[v, kaynak] = −c yazılır. Kaynağın aşırı akışı negatif olur; kaynak bu bakımdan özel bir düğümdür. Ana döngü şöyledir:

döngü aşırı[u] > 0 olan u varken:
  // u ≠ kaynak, u ≠ hedef
  eğer kalan(u,v) > 0 ve
       yükseklik[u] == yükseklik[v]+1:
    // İtme
    delta = min(aşırı[u], kalan(u,v))
    akış[u,v] += delta
    akış[v,u] −= delta
    aşırı[u] −= delta
    aşırı[v] += delta
  değilse:
    // Yeniden etiketleme
    m = ∞
    her bir (u, v) için G[u] içinde:
      eğer akış[u,v] < kapasite[u,v]:
        m = min(m, yükseklik[v])
    yükseklik[u] = m + 1
döndür aşırı[hedef]
// kalan = kapasite − akış

Döngü aktif bir u düğümü bulunduğu sürece döner. u'nun bir v komşusuna itme koşulu sağlanıyorsa itme yapılır; sağlanmıyorsa u yeniden etiketlenir. Yeniden etiketleme kısmı artık ağdaki komşuların, yani akış < kapasite olan kenarların yüksekliklerinin en küçüğünü bulur ve bir fazlasını yazar. Döngü bittiğinde hedefin aşırı akışı döndürülür; bu, hedefe varmış toplam akıştır.

4.4.7.7Java: it() ve etiketle()

Java uygulamasında her Dugum nesnesi kendi yukseklik ve asiri alanlarını ve çıkan kenarlarının listesini tutar. İtme işlemi şöyledir:

boolean it(Dugum d) {
  for (Kenar k : d.kenarlar) {
    if (d.yukseklik > k.hedef.yukseklik
        && k.akis != k.kapasite) {
      int akis = Math.min(
        k.kapasite - k.akis, d.asiri);
      d.asiri -= akis;
      k.hedef.asiri += akis;
      k.akis += akis;
      tersKenariGuncelle(k, akis);
      return true;   // itme yapıldı
    }
  }
  return false;
}

Metot düğümün kenarlarını sırayla dener. Koşuldaki d.yukseklik > k.hedef.yukseklik ifadesi, teorideki h(u) = h(v) + 1 koşulundan daha gevşek görünür. Ama değişmez nedeniyle ikisi aynıdır: artık ağdaki bir kenarda h(u) ≤ h(v) + 1 olduğundan h(u) > h(v) ancak h(u) = h(v) + 1 iken mümkündür. k.akis != k.kapasite kenarın artık ağda olduğunu söyler.

Koşul sağlanınca itilecek miktar kalan kapasite ile aşırı akışın küçüğüdür. Düğümün fazlası azalır, hedef düğümünki artar, kenarın akışı büyür ve tersKenariGuncelle ters kenarın akışını aynı miktarda azaltır. Ters kenarlar kapasitesi 0, akışı negatif olan kenarlar olarak saklanır. Metot ilk başarılı itmeden sonra true döner. Hiçbir kenar uygun değilse false döner ve düğüm yeniden etiketlenir:

void etiketle(Dugum d) {
  int minY = Integer.MAX_VALUE;
  for (Kenar k : d.kenarlar) {
    // yalnızca artık ağdaki kenarlar
    if (k.akis != k.kapasite
        && k.hedef.yukseklik < minY) {
      minY = k.hedef.yukseklik;
      d.yukseklik = minY + 1;
    }
  }
}

Döngü artık ağdaki komşular arasında en alçak olanı bulur ve yüksekliği onun bir fazlasına ayarlar. Atama döngünün içinde yapılır, ama son yapılan atama en küçük yüksekliğe karşılık geldiği için sonuç doğrudur. Ana döngü bu iki metodu birleştirir: aktif düğüm varken if (!it(d)) etiketle(d);. Sonuç hedefin aşırı akışıdır.

Bir itme O(1), bir yeniden etiketleme düğümün derecesi kadar zaman alır. Kod kenar listesini her çağrıda baştan tarar. Bu basitlik uğruna yapılmış bir tercihtir; verimli uygulamalar Dinic'teki basla dizisine benzer bir “sıradaki kenar” göstergesi tutar.

4.4.7.8Karmaşıklık

Algoritmanın süresi, her işlem türünün en fazla kaç kez yapılabileceği sayılarak bulunur. Tablo 4.4.10 sonuçları özetler.

Yeniden etiketleme. Aktif bir düğümün artık ağda kaynağa giden bir yolu vardır. Bu yol en fazla |V| − 1 kenarlıdır ve her kenarda yükseklik en fazla 1 düşer. Öyleyse h(u) ≤ h(s) + |V| − 1 = 2|V| − 1. Her yeniden etiketleme yüksekliği en az 1 artırdığı için bir düğüm en fazla 2|V| − 1 kez etiketlenir; toplam O(V²). Örneğimizde |V| = 6 için sınır 11'dir; en yüksek etiket 8 olmuştur.

Doyuran itme. (u, v) kenarı doyurulduğunda h(u) = h(v) + 1'dir. Aynı yönde yeniden doyurulabilmesi için önce v'den u'ya itme yapılmalıdır; bunun için h(v), h(u) + 1'e çıkmalıdır, yani en az 2 artmalıdır. Sonra u'nun da 2 artması gerekir. Yükseklikler 2|V|'yi aşamadığından her kenar O(V) kez doyurulur; toplam O(V · E).

Doyurmayan itme. Aktif düğümlerin yükseklikleri toplamı Φ bir potansiyel olarak kullanılır. Doyurmayan itme u'yu pasif yapar ve Φ'yi en az 1 azaltır (v aktifleşse bile h(v) = h(u) − 1'dir). Yeniden etiketlemeler Φ'yi toplamda O(V²), doyuran itmeler en fazla O(V · E) · 2V artırır. Bu yüzden doyurmayan itme sayısı O(V² · E)'dir.

Genel algoritma en kötü durumda O(V² · E) sürer. Bir yeniden etiketleme en fazla derece kadar kenarı tarar; toplam tarama O(V · E)'dir ve baskın terimi değiştirmez. Aktif düğümün seçim kuralı sınırı iyileştirir. Aktif düğümler bir FIFO (ilk giren ilk çıkar) kuyruğunda tutulursa süre O(V³)'e iner. Her seferinde en yüksek etiketli aktif düğüm seçilirse süre O(V² · √E) olur.

Pratikte iki sezgi algoritmayı çok hızlandırır. Boşluk (gap) sezgisi, bir yükseklik değerinde hiç düğüm kalmadığını fark eder. Bu durumda o değerin üstündeki düğümler hedefe ulaşamaz; sezgi onları doğrudan |V|'nin üstüne taşır. Örnekteki uzun “top oynama” bölümleri böylece tek adımda kısalır. Toplu yeniden etiketleme (global relabeling) ise zaman zaman hedeften geriye bir BFS yaparak bütün yükseklikleri gerçek uzaklıklara eşitler. Bu sezgilerle itme–yeniden etiketleme, en hızlı genel amaçlı maksimum akış yöntemlerinden biridir.

4.4.8Karşılaştırma ve uygulamalar

4.4.8.1Algoritmaların karşılaştırması

Dört algoritma aynı ağ üzerinde çalıştırıldığında farkları somutlaşır. Tablo 4.4.11, maksimum akışı 19 olan ikinci örnek ağdaki sonuçları özetler.

Edmonds-Karp bu ağda şu yolları bulur: S → 1 → 2 → T (4), S → 1 → 4 → T (6), S → 3 → 4 → T (4) ve S → 3 → 4 → 2 → T (5). İlk üç yol üç kenarlı, sonuncusu dört kenarlıdır. Beşinci BFS hedefe ulaşamaz. Dinic'in birinci fazı ilk üç yolu tek bir BFS'den sonra işler; ikinci fazı dördüncü yolu bulur.

Seçim için kaba bir kural verilebilir. Kapasiteler küçük tam sayılarsa Ford-Fulkerson yeterlidir ve en kısa koddur. Genel amaçlı bir uygulama için Dinic iyi bir varsayılandır: kodu kısa, sınırı iyi, pratikte hızlıdır. Çok büyük ve yoğun ağlarda itme–yeniden etiketleme, sezgileriyle birlikte, genellikle en hızlısıdır. Bütün algoritmalar aynı |f*| değerini bulur. Akışın kenarlara dağılımı farklı olabilir. Minimum kesim her durumda son artık ağdan okunur.

4.4.8.2Bir ağda bütün adımlar

Notta tanıtılan kavramların hepsi küçük bir ağda birlikte uygulanabilir.

4.4.8.3Uygulamalar

Maksimum akışın gücü, ilk bakışta akışla ilgisi olmayan pek çok problemin bir akış ağına dönüştürülebilmesinden gelir. Dönüşüm yapıldıktan sonra notta anlatılan algoritmalardan herhangi biri kullanılır.

İki parçalı eşleştirme. Çalışanlar ve işler, öğrenciler ve projeler gibi iki grup düşünelim. Her çalışan yapabildiği işlerle bir kenarla bağlıdır. Her çalışan en çok bir iş, her iş en çok bir çalışan alabilir. En fazla sayıda eşleşme istenir. Bu problem bir akış ağına şöyle dönüştürülür: bir kaynak bütün çalışanlara, bütün işler bir hedefe bağlanır; çalışan–iş kenarları olduğu gibi kalır. Bütün kapasiteler 1'dir.

Kaynaktan bir çalışana giden kenarın kapasitesi 1 olduğu için o çalışandan en fazla bir birim akış çıkar; çalışan en fazla bir işe atanır. İşten hedefe giden kenar da aynı sınırı işler için koyar. Tam sayılılık teoremi maksimum akışın her kenarda 0 ya da 1 olduğunu garanti eder. Akış taşıyan çalışan–iş kenarları bir eşleştirmedir ve akışın değeri eşleştirmenin büyüklüğüdür. Şekil 4.4.35'teki ağda a₁ çalışanı b₁ ve b₂'yi, a₂ yalnızca b₁'i, a₃ ise b₂ ve b₃'ü yapabilir. Maksimum akış 3'tür; herkes bir iş alır.

Kenar ayrık yollar. İki düğüm arasında ortak kenarı olmayan en fazla kaç yol bulunabilir? Bu soru ağların dayanıklılığıyla ilgilidir: kaç bağlantı koparsa iletişim kesilir? Her kenara kapasite 1 verilir; maksimum akış, kenar ayrık yolların sayısına eşittir. Menger teoremi aynı sayının, iki düğümü ayırmak için silinmesi gereken en az kenar sayısına eşit olduğunu söyler. Bu, maksimum akış minimum kesim teoreminin birim kapasiteli özel durumudur.

Düğüm kapasiteleri. Bazı problemlerde kısıt kenarlarda değil düğümlerdedir: bir kavşaktan saatte en fazla belli sayıda araç geçebilir. Her v düğümü iki düğüme bölünür: giriş v_g ve çıkış v_ç. Aralarına kapasitesi c(v) olan bir v_g → v_ç kenarı konur. v'ye gelen kenarlar v_g'ye, v'den çıkanlar v_ç'den bağlanır. Düğümden geçen bütün akış bu tek kenarı kullanmak zorunda kalır.

Görüntü bölütleme. Bir fotoğrafta ön plan ile arka planı ayırmak için her piksel bir düğüm olur. Kaynak “ön plan”, hedef “arka plan”ı temsil eder. Bir pikselin ön plan olma olasılığı kaynaktan gelen kenarın, arka plan olma olasılığı hedefe giden kenarın kapasitesine dönüşür. Komşu pikseller arasındaki kenarlar, benzer piksellerin aynı tarafta kalmasını ödüllendirir. Minimum kesim, toplam “yanlış etiketleme maliyetini” en küçük yapan ayrımı verir.

Ağ güvenilirliği, ulaşım ve lojistik. Bir iletişim ağını ikiye bölmek için kesilmesi gereken en küçük toplam kapasite, bir minimum kesimdir. Boru hatlarında, trafik planlamada, havayolu çizelgelemede ve proje seçimi problemlerinde de maksimum akış ya da minimum kesim temel araçtır. Bu problemlerin çoğunda asıl iş, doğru ağı kurmaktır; algoritma hazırdır.

4.4.9Sık yapılan hatalar

Ağ akışı problemlerinde yapılan hataların çoğu birkaç kavram karışıklığından doğar. Aşağıdaki liste bunları bir araya getirir.

• Ters kenarları unutmak. Yalnızca ileri kenarlarla aramak açgözlü bir algoritmadır ve maksimumu kaçırabilir; ikinci örnek ağda sonuç 19 yerine 18 çıkar.
• Darboğazı kapasiteyle hesaplamak. Darboğaz, kapasitelerin değil artık kapasitelerin en küçüğüdür: ileri kenarda c − f, ters kenarda f. İkinci artıştan sonra kenarların bir kısmı dolu olduğu için kapasiteye bakmak yanlış ve fazla bir darboğaz verir.
• Minimum kesimi kenar sayısı sanmak. Minimum kesim en az kenarı değil, en küçük kapasite toplamını keser.
• T'den S'ye giden kenarları saymak. Kesim kapasitesine yalnızca S'den T'ye giden kenarlar girer; geri yöndekiler eklenmez. Kesimden geçen net akış hesabında ise geri yöndeki akışlar çıkarılır. İki hesap birbirine karıştırılmamalıdır.
• Akışın değerini kenar akışlarının toplamı sanmak. Değer yalnızca kaynaktan çıkan net akıştır; aynı birim yol üzerindeki her kenarda yeniden sayılmaz.
• Ford-Fulkerson'ı polinom sanmak. O(E · |f*|) kapasitelerin değerine bağlıdır. BFS ile çalışan Edmonds-Karp bu bağımlılığı kaldırır.
• Edmonds-Karp'taki “en kısa”yı kapasiteyle ölçmek. En kısa yol, kenar sayısı en az olan yoldur. Kapasitesi büyük yolu seçmek ayrı bir sezgidir ve Edmonds-Karp'ın sınırı onun için geçerli değildir.
• Dinic'te seviye koşulunu gevşetmek. DFS yalnızca seviye(v) = seviye(u) + 1 olan kenarları izlemelidir. Aynı seviyedeki kenarlara izin verilirse DFS döngüye girebilir ve faz sayısı sınırı geçersiz kalır.
• İtme yönünü karıştırmak. Akış yüksekten alçağa, yalnızca h(u) = h(v) + 1 iken itilir; başlangıçta h(s) = |V| olmalıdır.
• Minimum kesimi yanlış artık ağdan okumak. Kesim, algoritma bittikten sonraki son artık ağda kaynaktan ulaşılabilen düğümlerden okunur. Ara bir adımın artık ağından okunan küme bir kesim verse de minimum olmayabilir.

4.4.10Özet

• Akış ağı: kaynak, hedef ve kapasiteli kenarlardan oluşan yönlü çizge. Akış kapasite kısıtına (0 ≤ f ≤ c) ve ara düğümlerde korunuma (giren = çıkan) uyar. Değer |f|, kaynaktan çıkan net akıştır. Birden çok kaynak ve hedef, sonsuz kapasiteli kenarlarla bağlanan süper kaynak ve süper hedefle tek kaynaklı probleme dönüştürülür.
• Artık ağ: ileri kenarın artık kapasitesi c − f, ters kenarınki f'dir. Ters kenar, gönderilmiş akışın geri alınabilmesini sağlar. Artış yolu artık ağda bir s–t yoludur; darboğaz yoldaki en küçük artık kapasitedir. Yol boyunca darboğaz kadar artırma geçerli bir akış verir ve değeri darboğaz kadar büyütür.
• Kesim: c(S, T), S'den T'ye giden kenarların kapasiteleri toplamıdır. Her kesimden geçen net akış |f|'ye eşittir; bu yüzden |f| ≤ c(S, T). Maksimum akış minimum kesime eşittir. Minimum kesimin S tarafı, son artık ağda kaynaktan ulaşılabilen düğümlerdir.
• Ford-Fulkerson: herhangi bir artış yolunu kullanır. Tam sayı kapasitelerde sonlanır, tam sayı değerli bir akış bulur ve O(E · |f*|) sürer. Kötü yol seçimi kapasite kadar artış gerektirebilir.
• Edmonds-Karp: BFS ile en kısa artış yolunu seçer. Uzaklıklar azalmaz, her kenar O(V) kez kritik olur; O(V · E) artış ve O(V · E²) süre.
• Dinic: her fazda BFS ile seviye çizgesi kurar, DFS ve kaldığı yer dizisiyle engelleyici akış bulur. En fazla V − 1 faz, faz başına O(V · E); toplam O(V² · E). Birim kapasitelerde çok daha hızlıdır.
• İtme–yeniden etiketleme: h(s) = |V| ile başlar, kaynak kenarlarını doldurarak bir ön akış kurar. Akış yüksekten alçağa itilir; itilemiyorsa düğüm yeniden etiketlenir. Aktif düğüm kalmayınca ön akış maksimum akıştır. Genel sürüm O(V² · E), FIFO sürümü O(V³).
• Uygulamalar: iki parçalı eşleştirme, kenar ayrık yollar, düğüm kapasiteli ağlar, görüntü bölütleme ve ağ güvenilirliği maksimum akış ya da minimum kesim olarak modellenir.

4.4.11Kavram listesi

• akış ağı flow network
• kaynak / hedef source / sink
• kapasite capacity
• akış korunumu flow conservation
• maksimum akış maximum flow
• artık ağ residual network
• artık kapasite residual capacity
• artış yolu augmenting path
• darboğaz bottleneck
• kesim cut (s-t cut)
• maksimum akış minimum kesim teoremi max-flow min-cut theorem
• Ford-Fulkerson yöntemi Ford-Fulkerson method
• Edmonds-Karp algoritması Edmonds-Karp algorithm
• Dinic algoritması Dinic's algorithm
• seviye çizgesi level graph
• engelleyici akış blocking flow
• itme–yeniden etiketleme push-relabel
• aşırı akış excess flow
• iki parçalı eşleştirme bipartite matching

4.4.12Kendini Dene

1. Şekil 4.4.2'deki akışta B→C (2/3) ve C→D (5/6) kenarları artık ağda hangi kenarları ve kapasiteleri üretir? Bu akış için artık ağda bir artış yolu var mıdır?

   Cevap

   B→C: ileri c_f(B, C) = 3 − 2 = 1, ters c_f(C, B) = 2. C→D: ileri c_f(C, D) = 1, ters c_f(D, C) = 5. Artış yolu yoktur: kaynaktan çıkan iki kenar doymuştur ve artık ağda S'den çıkan kenar kalmaz.

2. İkinci örnek ağda (Şekil 4.4.10) S = {S, 1, 3} kesiminin kapasitesi kaçtır? Bu kesim neden minimum değildir?

   Cevap

   S'den T'ye giden kenarlar 1 → 2 (4), 1 → 4 (8) ve 3 → 4 (9)'dur: 4 + 8 + 9 = 21. S → 1, S → 3 ve 1 → 3 kenarlarının iki ucu da S tarafındadır. Maksimum akış 19 olduğundan kapasitesi 21 olan kesim minimum olamaz; minimum kesim {S, 3}'tür (19).

3. Edmonds-Karp birinci örnek ağda (Şekil 4.4.1) hangi yolları bulur? Kaç artış ve kaç BFS yapar?

   Cevap

   S → A → B → T (2), S → C → D → T (3) ve S → A → B → C → D → T (2). İlk iki yol 3, üçüncüsü 5 kenarlıdır. 3 artış yapılır; dördüncü BFS hedefe ulaşamaz. Toplam 4 BFS, maksimum akış 7.

4. Şekil 4.4.17'deki ağda komşuları indis sırasıyla (s, 1, 2, 3, 4, t) deneyen DFS'li Ford-Fulkerson hangi yolları bulur? Edmonds-Karp aynı ağda kaç artış yapar?

   Cevap

   Altı artış yapılır: s→1→2→4→3→t (7), s→1→2→4→t (3), s→1→3→2→4→t (1), s→1→3→t (5), s→2→1→3→t (6), s→2→3→t (1). Akış 7, 10, 11, 16, 22, 23 diye büyür. Beşinci yoldaki 2 → 1 özgün bir kenardır; altıncı yoldaki 2 → 3 ise 3 → 2'nin ters kenarıdır. Edmonds-Karp aynı ağda 3 artışla 23'e ulaşır.

5. Dinic algoritması birinci örnek ağda kaç faz yapar? Her fazdaki seviyeler ve engelleyici akış nedir?

   Cevap

   Faz 1: seviyeler S = 0; A, C = 1; B, D = 2; T = 3. B → C seviye geri gittiği için kullanılmaz. Engelleyici akış S → A → B → T (2) ve S → C → D → T (3); |f| = 5. Faz 2: seviyeler S = 0, A = 1, B = 2, C = 3, D = 4, T = 5; yol S → A → B → C → D → T (2), |f| = 7. Üçüncü BFS hedefe ulaşamaz. 2 faz, 3 BFS.

6. Birinci örnek ağda B → T kenarının kapasitesi 2'den 5'e çıkarılırsa maksimum akış değişir mi? Dinic kaç fazda biter?

   Cevap

   Değişmez; 7 kalır. ({S}, diğerleri) kesiminin kapasitesi hâlâ 4 + 3 = 7'dir ve bu kenar o kesimde yer almaz. Dinic tek fazda biter: seviye çizgesinde S → A → B → T 4, S → C → D → T 3 birim taşır. İkinci BFS hedefe ulaşamaz.

7. Birinci örnek ağda B düğümünden en fazla 3 birim akış geçebiliyorsa problem nasıl modellenir ve maksimum akış kaç olur?

   Cevap

   B, B_g ve B_ç düğümlerine bölünür; aralarına kapasitesi 3 olan bir kenar konur. A → B_g (4), B_ç → C (3), B_ç → T (2) olur. Maksimum akış 6'dır: örneğin B üzerinden 3 birim (2'si doğrudan hedefe, 1'i C'ye), S → C üzerinden 3 birim. Minimum kesim S → C (3) ile B_g → B_ç (3) kenarlarından oluşur: 6.

8. İkinci örnek ağda S'den T'ye en fazla kaç kenar ayrık yol vardır? Bu sayıya maksimum akışla nasıl ulaşılır?

   Cevap

   Bütün kapasiteler 1 yapılıp maksimum akış hesaplanır. Sonuç 2'dir; örneğin S → 1 → 2 → T ve S → 3 → 4 → T. Kaynaktan yalnızca iki kenar çıktığı için ({S} kesiminin kapasitesi 2) üçüncü bir kenar ayrık yol olamaz.

9. İtme–yeniden etiketleme birinci örnek ağda başlatılıyor. Başlangıçtaki yükseklikler ve aşırı akışlar nedir? A aktif düğüm olarak seçilirse ilk iki işlem ne olur?

   Cevap

   h(S) = 6, diğer bütün düğümlerde h = 0. S → A ve S → C doldurulur: e(A) = 4, e(C) = 3. A'nın artık komşuları B (h = 0) ve S (ters kenar, h = 6)'dir; hiçbiri bir basamak aşağıda değildir. Önce yeniden etiketleme: h(A) = 1 + min(0, 6) = 1. Sonra itme: δ = min(e(A), c_f(A, B)) = min(4, 4) = 4; e(A) = 0, e(B) = 4.

4.4.13İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 24: akış ağlarını, maksimum akış minimum kesim teoreminin ispatını, Edmonds-Karp analizini ve iki parçalı eşleştirmeyi ayrıntılı ispatlarla verir; notun Edmonds-Karp izleme ağı bu kitaptandır.
• J. Kleinberg ve É. Tardos, Algorithm Design (2006), Bölüm 7: maksimum akışı modelleme aracı olarak ele alır; görüntü bölütleme, proje seçimi ve havayolu çizelgeleme gibi uygulamaları çözülmüş örneklerle anlatır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 6.4: Ford-Fulkerson'ın en kısa yol sürümünü kenar nesneleriyle Java'da kodlar ve artık ağı nesne yönelimli bir tasarımla gösterir.
• A. V. Goldberg ve R. E. Tarjan, “A New Approach to the Maximum-Flow Problem” (1988): itme–yeniden etiketleme algoritmasını, değişmezlerini ve FIFO sürümünün O(V³) analizini ilk kaynağından verir.

4.4.14Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 24: Maximum Flow).
2. E. A. Dinic, “Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation”, Soviet Math. Doklady 11, 1970.
3. J. Edmonds, R. M. Karp, “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems”, Journal of the ACM 19(2), 1972.
4. L. R. Ford, D. R. Fulkerson, “Maximal Flow Through a Network”, Canadian Journal of Mathematics 8, 1956.
5. A. V. Goldberg, R. E. Tarjan, “A New Approach to the Maximum-Flow Problem”, Journal of the ACM 35(4), 1988.
6. J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2006 (Bölüm 7: Network Flow).
7. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011 (Bölüm 6.4: Maximum Flow).

İlgili sayfalar: Bölüm 4.4 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.