Maksimum Akış–Minimum Kesim Teoremi: Soğuk Savaştan Doğan Modern Ağ Matematiği

1954: bir gizli askeri rapor

Soğuk Savaş'ın doruğunda — 1954 — RAND Corporation Amerikan Hava Kuvvetleri için bir sorunu çalışıyordu: "Eğer Sovyetler büyük bir savaş başlatırsa, demiryolu ağı üzerinden Doğu Avrupa'ya ne kadar mühimmat akıtabilirler? Ve bu akışı durdurmak için hangi hatları bombalamalıyız?"

Görev iki Amerikan matematikçiye verildi: Lester Ford Jr. ve Delbert Fulkerson.

Sorulan klasik bir akış problemi: $G$ = yönlü graf (köşeler şehirler, kenarlar demiryolları), her kenarın bir kapasitesi $c(e)$ var (saatte ne kadar yük taşıyabilir). Bir kaynak $s$ (Moskova) ve bir kuyu $t$ (Berlin). Kaynaktan kuyuya maksimum akış ne kadar?

Ford ve Fulkerson 1954'te raporu (gizli) yazdı, 1956'da açık literatürde yayımladı. İçinde modern graf teorisinin temel teoremi vardı:

Maksimum akış = Minimum kesim.

Bu eşitlik, kombinatoryal optimizasyonun simgesi oldu. Soğuk Savaş motivasyonu altında doğan, bugün internetten vizeye kadar uzanan bir matematik.

Akış nedir?

Yönlü graf $G = (V, E)$, kapasiteler $c: E \to \mathbb{R}_{\geq 0}$, kaynak $s$, kuyu $t$.

Bir akış $f: E \to \mathbb{R}_{\geq 0}$ şu iki koşulu sağlar:

1. Kapasite kısıtı: $f(e) \leq c(e)$ her kenar için.
2. Korunum: $s$ ve $t$ dışındaki her köşede giren akış = çıkan akış.

Akışın değeri: $|f| = \sum_{e \text{ out of } s} f(e) - \sum_{e \text{ into } s} f(e)$ — yani $s$'den net olarak çıkan miktar.

Maksimum akış problemi: $|f|$'i maksimize et.

Kesim nedir?

Bir $s$-$t$ kesimi, köşeleri iki gruba böler: $S$ (kaynağı içeren) ve $T$ (kuyuyu içeren). Kesimin kapasitesi: $S$'den $T$'ye giden tüm kenarların kapasiteleri toplamı.

Minimum kesim: en küçük kapasiteli kesim.

Maks-Akış Min-Kesim teoremi

Bir ağda, maksimum akış değeri = minimum kesim kapasitesi.

Sezgi: Eğer $f$ bir akış ve $(S, T)$ bir kesim ise, akışın hepsi $S$'den $T$'ye geçmek zorundadır → $|f| \leq c(S, T)$ (kapasite kesimden büyük olamaz). Her kesim için bir üst sınır. Eşitlik garantili olduğu Ford-Fulkerson'ın katkısı.

İspat: bir maksimum akış varsa, "arttırma yolu" (augmenting path) yoktur. Bu olmayan yol, $S$ kümesini tanımlar. $(S, T)$ minimum kesim olur, kapasiteleri akışa eşittir.

Ford-Fulkerson algoritması

1. Başla: $f = 0$.
2. Arttırma yolu ara: $s$'den $t$'ye, artakalan kapasiteli kenarlardan oluşan yol.
3. Bulduğunda akışı bu yol boyunca artakalan kapasite kadar artır.
4. Yol kalmayınca dur.

Bu algoritma doğru sonucu verir (yukarıdaki teorem). Karmaşıklık: $O(|f^*| \cdot E)$. Tamsayı kapasitelerde sonludur; irrasyonel kapasitelerde sonsuza kadar sürebilir (bir patolojik örnek).

Edmonds-Karp (1972): arttırma yolunu BFS ile seç → $O(V E^2)$ deterministik karmaşıklık.

Dinic (1970, Soviet): $O(V^2 E)$ daha hızlı.

Goldberg-Tarjan (1988): preflow-push, $O(V^2 \sqrt{E})$.

Modern (2022, James Orlin): $O(VE)$ — en iyi bilinen bağ.

Niçin bu teorem güzel?

Maks-akış min-kesim dual sonucudur: max problem ile min problem aynı değeri verir. Bu, lineer programlama dualitesinin kombinatoryal görünümüdür.

Genel LP duality (1947, Dantzig): max problem = min dual. Maks akış-min kesim bunun özel hali, ama görsel ve kombinatoryal. Modern optimizasyon teorisinin giriş kapısıdır.

Klasik uygulamalar

1. İkili eşleştirme (Bipartite Matching)

Erkekler ve kadınlar var; bazı çiftler "uyumlu". Kaç çift kurulabilir? König teoremi (1931): maks eşleştirme = min vertex cover. Ford-Fulkerson uygulamasıyla maks akış problemi olarak modelleyince Hall ve König teoremleri trivial olur.

2. Atama problemleri

İşçileri işlere atama, görevleri kaynaklara atama. Hava trafiği kontrolü.

3. Görüntü segmentasyonu

Bilgisayar görüsünde graph cut yöntemi: bir görüntüyü ön plan-arka plan olarak segmente etmek için min-kesim hesaplanır.

4. Project selection

Hangi projeleri seçeyim ki kar maksimum olsun? Yan koşullar (X projesi Y'yi gerektirir) min-kesim ile modellenir.

5. Network reliability

Bir ağda iki noktayı kopuk yapmak için kaç kenar koparmak gerekir? Min-kesim cevap verir.

6. Vize kotaları

Devletler arası vize kotalarının dağılımı (her ülke için kota, her başvuru süreci). Klasik akış problemi.

7. İnternet trafiği

Modern load balancing ve routing protokolleri (BGP, OSPF) akış sezgilerinden yararlanır.

Soğuk Savaş ironisi

Ford-Fulkerson algoritmasının ilk uygulamalarından biri:

Sovyet demiryolu ağı analizi (1955, gizli rapor). Hangi hatlar bombalanırsa Doğu Avrupa'ya mühimmat akışı minimum olur? Cevap: min-kesim.

İlginç ironi: aynı matematik bugün:

• Vize kotalarını yönetmek için kullanılır.
• İnternet altyapısı dengelemek için kullanılır.
• Tıbbi görüntülemede tümör segmentasyonu için kullanılır.

Soğuk Savaş'tan barış zamanına: algoritma savaş aletinden hayat kurtaran araça dönüştü. Matematik araçlarının uygulama tarihinin zarif bir örneği.

Modern alanlar

Multi-commodity flow

Aynı ağda birden fazla farklı malın aynı anda akışı. NP-zor durumlar var, ama yaklaşımlar mevcut.

Submodular minimization

Min-kesim, submodular fonksiyon minimizasyonunun özel hali. Modern makine öğrenmesi optimizasyonunda yaygın.

LP relaxation

NP-zor problemler için LP gevşemesi + max-flow yaklaşımları.

Quantum graph algorithms

Kuantum bilgisayarlar için maks-akış varyantları aktif araştırma alanı.

Sonuç

Maks-Akış Min-Kesim teoremi:

• 1954 Sovyet demiryolu sorunundan doğdu.
• Lineer programlama dualitesinin kombinatoryal hali.
• Modern graf teorisi, ağ analizi, kombinatoryal optimizasyon'un merkezi.
• Bilgisayar görüsünden vize kotalarına her yerde uygulanır.

Bir tek formül — max $=$ min — modern matematiğin "aslında her şey aynı" estetiğinin örneği.

Ford ve Fulkerson 1954'te Sovyet hatlarını analiz ettiler. 70 yıl sonra, aynı teorem Google Maps'in rotanızı planlarken, hastanenin organ uyumu hesaplarken, ve internetin paketleri yönlendirirken çalışıyor. Bir tek askeri rapor, sonsuz katmanlı uygulama.