Ford Fulkerson metodu

Ford Fulkerson methodu ile belirli bir source'dan sink'e(hedef) farklı yollardan giderken ulaştırılabiliecek maximum flow diyebiliriz.
Örneğin , Antalya'dan Ankara'ya max sayıda kamyon göndermek istiyoruz.
Antalya'dan Afyona max 15 kamyon gönderilebiliyor
Antalya'dan Burdur'a max 8 kamyon gönderilebiliyor.
Burdur'dan Afyon'a max 6 kamyon gönderilebiliyor.
Afyon'dan Ankara'ya max 8 kamyon gönderilebiliyor.
Antalya'dan Isparta'ya max 4 kamyon gönderilebiliyor.
Isparta'dan Ankara'ya max 7 kamyon gönderilebiliyor.
Ford Fulkerson Methodu sayesinde Antalya'dan Ankaraya gönderebileceğimiz max. kamyon sayısını bulacağız.

Öncelikle şunu bilmenizi istiyorum:

Şimdi de aşağıdaki flow network'lerine bakalım.
Source'dan Sink'e doğru bir yol çizeriz.Bunu aşağıda koyu renkle çizdiğimiz yol ile gösterdik. Buna "augmenting path" de denir.Augmentin path'deki min flow seçilir. Ve tüm augmenting path üzerindeki tüm flow sayılarından çıkartılır.

Bundan sonraki adımlar da aynı şekilde devam eder. Aşağıdan takip edebilirsiniz.

En son elimizde çizecek bir augmeting path kalmayıncaya kadar yukarıdaki gibi aynı adımları uygularız. En son , bulduğumuz tüm min. flow'ları toplarız , böylece source'dan sink'e gönderilebilecek max. flow'u buluruz.


Questions :
1 - 1st question here : http://www.cs.toronto.edu/~vassos/teaching/c73/handouts/4.pdf  Solutions






2 - 4th & 5th questions here : http://www.cs.toronto.edu/~vassos/teaching/c73/old-exams/final-10.pdf