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