Folyam algoritmusok

A maximális folyam-minimális vágás tétel következménye, hogy a következõ eljárás természetes módon vetõdik fel, mint folyam algoritmus:

Egy kiinduló folyamot (legyen például az azonosan 0 folyam) addig javítunk javító utak mentén amíg lehetséges.

Hogy egy algoritmust kapjunk két dolgot kell megvizsgálnunk: I) Hogyan kereshetünk javító utat egy folyamra. II) Lehetséges-e ciklizálás a fenti eljárásban.

I) A javító út keresés egy implementációja (Ford-Fulkerson-algoritmus)

Javító út kezdemények keresése a már megtalált kezdemények lehetséges növeléseivel. A megtalált javító út kezdemények végpontjait megcímkézzük (és egy pointert vezetünk be annak jelölésére, hogy hova vezetõ javító út kezdeményt hosszabbítottunk meg egy éllel). A címkézésnél ügyelünk arra, hogy csak eddig címkézetlen csúcsoknak adjunk címkét (átcímkézés nincs).

Ha a nyelõt megcímkézzük, akkor a pointerek visszakeresésével egy javító utat találunk. Ha a nyelõt nem címkezzük meg, akkor a címkézett és címkézetlen pontok egy s-t vágást adnak, amley bizonyítja, hogy folyamunk optimális, azaz nincs javító út.

Megjegyzés: Ha a fenti eljárásban a címkéket fázisokban osztjuk ki és az egyes fázisokban az elõzõ fázisban megtalált javító út kezdemény összes egy éllel történõ meghosszabbítását megkeressük (és az ennek megfelelõ címkézést elvégezzük), akkor a fázisok sorszáma az éppen magtalált javító út kezdemény hosszát jelenti. Javító út megtalálása esetén az output a legrövidebb javító út lesz.

II) Ciklizálás kérdése

• Tetszõleges javító út mentén történõ javítás sorozat elvezet az optimumhoz, ha a kiinduló hálózat kapacitásai és a kiinduló folyam értékei egészek.
• Ez könnyen kiterjeszthetõ arra az esetre, ha a kiinduló hálózat kapacitásai és a kiinduló folyam értékei racionálisak.
• A legrövidebb javító út menti javítás esetén a Ford--Fulkerson-algoritmus nem ciklizálhat. Ezt nem bizonyítjuk, de az érdeklõdõ hallgatók megpróbálhatják a bizonyítás megértését.
• Tetszõleges javító út mentén történõ javítássorozat valós aritmetikában nem szükségszerûen ér véget. Sõt a végtelen folyamsorozat értéke (monoton növõ, korlátos sorozat) limesze lehet a maximális folamértéknél kisebb.