Fordova-Fulkersonova věta uvádí do vztahu maximální tok a minimální řez v síti oddělující zdroj od stoku. Vychází z ní i myšlenka základního způsobu hledání maximálního toku – Fordova-Fulkersonova algoritmu, která řeší úlohu toku v síti.
Definice Síť definujeme jako ohodnocený orientovaný graf s vyznačenými dvěma různými vrcholy a (označujeme je jako zdroj a stok). Kapacita je funkce ohodnocující hrany grafu nezápornými reálnými čísly.
Tok v síti je každá funkce která splňuje následující podmínky Pro každou hranu platí . Pro každý vrchol kromě zdroje a stoku je vstupní tok roven výstupnímu toku:
Velikost toku lze definovat jako součet toků na hranách vedoucích od zdroje : .
Problém maximálního toku v síti spočívá v nalezení toku mezi zdrojem a stokem, který maximálně využívá kapacit hran.
Je-li dána síť a tok pak reziduální síť k danému toku je orientovaný graf definovaný na vrcholech původního grafu. Jeho množina hran vychází z množiny hran grafu . Hrana se stane hranou reziduální sítě, pokud má vzhledem k ještě volnou kapacitu, tj. . Reziduální sítě hrají významnou roli při algoritmickém hledání maximálních toků. Základní myšlenkou je, že pokud reziduální síť k toku obsahuje cestu mezi zdrojem a stokem, pak lze podél této cesty velikost toku zvětšit.
Řezem mezi zdrojem a stokem rozumíme množinu hran . Tuto množinu získáme rozdělením množiny vrcholů na dvě disjunktní části a , které od sebe 'oddělují' zdroj a stok, tj. a . Řezem pak rozumíme množinu hran mezi množinami a . Kapacitu řezu pak definujeme jako
Problém minimálního řezu spočívá v nalezení rozdělení vrcholů na a takové, že kapacita souvisejícího řezu je minimální.
Znění Obecné lze větu zformulovat následovně Pro každou síť se velikost maximálního toku rovná kapacitě minimálního řezu.
Poněkud precizněji pak lze větu zformulovat takto:
Jestliže je tok v síti , pak následující tvrzení jsou ekvivalentní je maximální tok v síti Reziduální síť neobsahuje žádnou zlepšující cestu (tj. neexistuje cesta ze zdroje do cíle v reziduální síti) V síti existuje řez pro který platí .
Vysvětlení Pro každý řez v síti platí, že jeho kapacita je větší nebo rovno velikosti libovolného toku, který přes řez přetéká. Toto plyne přímo z bodu 1. definice toku v síti.
Uvažujeme-li nyní maximální tok v síti , pak musíme najít i jeden řez, pro který platí . Pokud by se velikost toku nerovnala kapacitě řezu , bylo by možné tok rozšířit o tento rozdíl na nový (větší) tok což je v rozporu z maximalitou toku kterou jsme předpokládali.
Související články Tok v síti
Kategorie:Grafové pojmy Kategorie:Matematické věty a důkazy