Fordova–Fulkersonova věta

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 $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

1. Pro každou hranu $e\in E$ platí $0\leq f(e)\leq c(e)$.
2. 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$. 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. $\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í

1. $f$ je maximální tok v síti $G$
2. Reziduální síť $G_{f}$ neobsahuje žádnou zlepšující cestu (tj. neexistuje cesta ze zdroje do cíle v reziduální síti)
3. 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.

Související články

• Tok v síti