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 s vyznačenými dvěma různými vrcholy a (označujeme je jako zdroj a stok). Kapacita je funkce ohodnocující hrany grafu nezápornými reálnými čísly.

Tok v síti je každá funkce která splňuje následující podmínky

  1. Pro každou hranu platí .
  2. Pro každý vrchol kromě zdroje a stoku je vstupní tok roven výstupnímu toku:

Velikost toku lze definovat jako součet toků na hranách vedoucích od zdroje : .

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

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


Řezem mezi zdrojem a stokem rozumíme množinu hran . Tuto množinu získáme rozdělením množiny vrcholů na dvě disjunktní části a , které od sebe 'oddělují' zdroj a stok, tj. a . Řezem pak rozumíme množinu hran mezi množinami a . Kapacitu řezu pak definujeme jako

Problém minimálního řezu spočívá v nalezení rozdělení vrcholů na a takové, že kapacita souvisejícího řezu 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 je tok v síti , pak následující tvrzení jsou ekvivalentní

  1. je maximální tok v síti
  2. Reziduální síť neobsahuje žádnou zlepšující cestu (tj. neexistuje cesta ze zdroje do cíle v reziduální síti)
  3. V síti existuje řez pro který platí .

Vysvětlení

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

Související články