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 ${\displaystyle G=(V,E)}$ s vyznačenými dvěma různými vrcholy ${\displaystyle z}$ a ${\displaystyle s}$ (označujeme je jako zdroj a stok). Kapacita ${\displaystyle 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 ${\displaystyle f\colon E\to R_{0}^{+}}$ která splňuje následující podmínky

1. Pro každou hranu ${\displaystyle e\in E}$ platí ${\displaystyle 0\leq f(e)\leq c(e)}$.
2. Pro každý vrchol ${\displaystyle v\in V}$ kromě zdroje a stoku je vstupní tok roven výstupnímu toku: ${\displaystyle \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 ${\displaystyle z}$: ${\displaystyle \textstyle |f|=\sum _{(z,v)\in E}f(z,v)}$.

Problém maximálního toku v síti spočívá v nalezení toku ${\displaystyle f}$ mezi zdrojem a stokem, který maximálně využívá kapacit hran.

Je-li dána síť ${\displaystyle G}$ a tok ${\displaystyle f}$ pak reziduální síť ${\displaystyle G_{f}}$ k danému toku ${\displaystyle f}$ je orientovaný graf definovaný na vrcholech ${\displaystyle V}$ původního grafu. Jeho množina hran ${\displaystyle E_{f}}$ vychází z množiny hran grafu ${\displaystyle G}$. Hrana ${\displaystyle e=(u,v)\in E}$ se stane hranou reziduální sítě, pokud má vzhledem k ${\displaystyle f}$ ještě volnou kapacitu, tj. ${\displaystyle 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 ${\displaystyle f}$ obsahuje cestu mezi zdrojem a stokem, pak lze podél této cesty velikost toku ${\displaystyle f}$ zvětšit.

Řezem mezi zdrojem a stokem rozumíme množinu hran ${\displaystyle R\subseteq E}$. Tuto množinu získáme rozdělením množiny vrcholů na dvě disjunktní části ${\displaystyle Z}$ a ${\displaystyle S}$, které od sebe 'oddělují' zdroj a stok, tj. ${\displaystyle \textstyle z\in Z}$ a ${\displaystyle \textstyle s\in S}$. Řezem ${\displaystyle R}$ pak rozumíme množinu hran mezi množinami ${\displaystyle Z}$ a ${\displaystyle S}$. Kapacitu řezu pak definujeme jako ${\displaystyle 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 ${\displaystyle Z}$ a ${\displaystyle S}$ takové, že kapacita souvisejícího řezu ${\displaystyle 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 ${\displaystyle f}$ je tok v síti ${\displaystyle G=(V,E)}$, pak následující tvrzení jsou ekvivalentní

1. ${\displaystyle f}$ je maximální tok v síti ${\displaystyle G}$
2. Reziduální síť ${\displaystyle 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 ${\displaystyle G}$ existuje řez ${\displaystyle R\subseteq E}$ pro který platí ${\displaystyle |f|=c(R)}$.

Vysvětlení

Pro každý řez v síti ${\displaystyle 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 ${\displaystyle f}$, pak musíme najít i jeden řez, pro který platí ${\displaystyle |f|=c(R)}$. Pokud by se velikost toku ${\displaystyle f}$ nerovnala kapacitě řezu ${\displaystyle R}$, bylo by možné tok ${\displaystyle f}$ rozšířit o tento rozdíl na nový (větší) tok ${\displaystyle f'}$ což je v rozporu z maximalitou toku ${\displaystyle f}$ kterou jsme předpokládali.

Související články

• Tok v síti