Cesko.wiki Fordova–Fulkersonova věta
Author
Albert FloresFordova-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 G=(V,E) s vyznačenými dvěma různými vrcholy z a s (označujeme je jako zdroj a stok). Kapacita c \colon E \to R_0^+ je funkce ohodnocující hrany grafu nezápornými reálnými čísly.
Tok v síti je každá funkce f\colon E \to R_0^+ která splňuje následující podmínky # Pro každou hranu e\in E platí 0\leq f(e) \leq c(e). # Pro každý vrchol v \in V kromě zdroje a stoku je vstupní tok roven výstupnímu toku: \sum_{(x,u) \in E} f(x,u) = \sum_{(u,y) \in E} f(u,y)
Velikost toku lze definovat jako součet toků na hranách vedoucích od zdroje z: \textstyle |f| = \sum_{(z,v) \in E} f(z,v).
Problém maximálního toku v síti spočívá v nalezení toku f mezi zdrojem a stokem, který maximálně využívá kapacit hran.
Je-li dána síť G a tok f pak reziduální síť G_f k danému toku f je orientovaný graf definovaný na vrcholech V původního grafu. Jeho množina hran E_f vychází z množiny hran grafu G. +more Hrana e = (u,v) \in E se stane hranou reziduální sítě, pokud má vzhledem k f ještě volnou kapacitu, tj. f(e) \leq c(e). 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 f obsahuje cestu mezi zdrojem a stokem, pak lze podél této cesty velikost toku f zvětšit.
Řezem mezi zdrojem a stokem rozumíme množinu hran R \subseteq E. Tuto množinu získáme rozdělením množiny vrcholů na dvě disjunktní části Z a S, které od sebe 'oddělují' zdroj a stok, tj. +more \textstyle z \in Z a \textstyle s \in S. Řezem R pak rozumíme množinu hran mezi množinami Z a S. Kapacitu řezu pak definujeme jako c(R) = c (Z,S) = \sum_{(u,v) \in Z \times S} c_{uv}.
Problém minimálního řezu spočívá v nalezení rozdělení vrcholů na Z a S takové, že kapacita souvisejícího řezu c(R) 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 f je tok v síti G=(V,E), pak následující tvrzení jsou ekvivalentní # f je maximální tok v síti G # Reziduální síť G_f neobsahuje žádnou zlepšující cestu (tj. neexistuje cesta ze zdroje do cíle v reziduální síti) # V síti G existuje řez R \subseteq E pro který platí |f|=c(R).
Vysvětlení
Pro každý řez v síti G 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 f, pak musíme najít i jeden řez, pro který platí |f|=c(R). Pokud by se velikost toku f nerovnala kapacitě řezu R, bylo by možné tok f rozšířit o tento rozdíl na nový (větší) tok f' což je v rozporu z maximalitou toku f kterou jsme předpokládali.