Hledat:

Invia.cz Pojeďte do Egypta Kanárské ostrovy Dovolená - Turecko Dominikánská republika Madeira Last minute
 

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

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

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

 
Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „https://cs.wikipedia.org/w/index.php?title=Fordova–Fulkersonova_věta&oldid=15633050
Stránka byla naposledy upravena 11. 12. 2017 v 04:43. Editovat celý článek Fordova–Fulkersonova věta.
Text je dostupný pod licencí Creative Commons Uveďte autora – Zachovejte licenci 3.0 Unported, případně za dalších podmínek. Podrobnosti naleznete na stránce Podmínky užití.
Další služby: Portál | Katalog | Hledej | Zprávy | Počasí | Kurzy | Práce | Slovník | TV | Online hry | Java hry | SMS | Loga a melodie | Chat | Fórum | Kontakt | Set-top-boxy