Ford-Fulkersonova věta
Z Wikipedie, otevřené encyklopedie
Ford-Fulkersonova věta uvádí do vztahu maximální tok a minimální řez oddělující zdroj od stoku. Vychází z ní i myšlenka základního způsobu hledání maximálního toku - Ford-Fulkersonova algoritmu.
[editovat] Znění
Jestliže f je tok v síti G, pak následující tvrzení jsou ekvivalentní:
1. f je maximální tok v síti G,
2. Reziduální síť Gf neobsahuje žádnou zlepšující cestu(tj. neexistuje cesta ze zdroje do cíle v reziduální síti),
3. | f | = c(S,T) pro nějaký řez (S,T) sítě G, kde | f | je délka toku a c(S,T) je kapacita řezu (S,T).