Fordova-Fulkersonova věta

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]