Maksimum Akış Problemi

Bağlantı ağırlıkları (yani, genelde uzunlukları) yerine (karayolu taşımacılığı veya boru hatlarındaki gibi) taşıma kapasitelerinin dikkate alındığı ağ yapılarında çözülmesi gerekebilecek problem türlerinden biri de bir kaynaktan hedefe aktarılabilecek maksimum miktarı bulmaktır. Bu aktarma işlemi bir akış gibi düşünülürse, problemin amacı da maksimum akışı sağlamak olur.

Şunun gibi bir ağ yapısındaki bağlantı kapasitelerine bakarsanız, 0 nolu kaynak noddan 3 nolu hedef noda aktarabileceğiniz maksimum miktarın ya kaynağa ya da hedefe doğrudan bağlı bağlantıların toplam kapasitesi (hangisi daha küçükse) olacağını düşünebilirsiniz:

Kaynağa da, hedefe de baksanız, yukarıdaki ağ yapısında maksimum akış miktarı 15 olabilirmiş gibidir. Ne var ki aralardaki bağlantıların kapasiteleri aktarımı daha da sınırlayabilir. Kesin çözüm için kolay -ama yavaş- bir yöntem Ford-Fulkerson algoritmasıdır. Bu yöntemin temel prensibi kaynaktan hedefe ulaşan yolları derinlik öncelikli bir ağaç oluşturur gibi bulmak ve her bir yol için taşınabilecek maksimum miktarı aktarmaktır. Tabi bu miktar da da seçtiğiniz yol üzerindeki en düşük kapasite olacaktır. kapasitesini sıfırladığınız bağlantıyı ağdan çıkartılmış varsayarak başka yol arar ve yine en düşük kapasiteli bağlantının zin verdiği kadar taşıma yaparsınız.

Buradaki ağ örneğimizde, üstteki 0-1-2-3 yolundan aktarabileceğiniz miktar 1-2 bağlantısının kapasitesi 2 olacaktır. Orta yol 0-4-3 üzerindeki 0-4 bağlantısı en fazla 4 birim taşımanıza izin verir. Alt yol 0-6-5-3 üzerinde de 0-6 bağlantısı 4 birim taşımadan sonra iptal olacaktır.

Kaynak nod 0 ile hedef nod 3 arasında kalan yollardan 0-1-4-3, 0-5-3 ve 0-5-2-3'den her biri ancak 1 birim taşımaya izin verir. Sonuç olarak kaynak-hedef arasında ancak 13 birim akış sağlayabilirsiniz. Kaynak nod 0 ve komşusu 1 arasında 2 birim kapasite kalmıştır, ama 1 nodunun artık kullanılabilir başka bağlantısı olmadığı için bu kapasite atıl kalacaktır.

Şu son iki yol 0-5-3 ve 0-5-2-3 üzerinden 1er birim taşımak yerine 0-5-4-2-3 üzerinden (eh, kulağı iyice tersten göstermiş oldunuz) 2 birim taşıtabilirdiniz, ama o kadarla kalırdınız. Sonuçta 2 tane 1 ile 1 tane 2 aynı değerdir. Yani daha fazla akışı sağlamanın br yolu yoktur.