Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Toky v sítích

není požadaváno v IP a ISPS

Definice (Síť, tok)

Síť je čtveřice , kde je (orientovaný) graf, zdrojový a cílový vrchol (stok, spotřebič) a funkce kapacity hran. Tok sítí je taková funkce , že pro každou hranu je a navíc pro každý vrchol kromě a (uzel sítě) platí (tj. přebytek toku - rozdíl toho co do vrcholu vteče a co z něj odteče je pro uzly sítě nulový). Velikost toku se definuje jako .

Algoritmus (Ford-Fulkersonův algoritmus)

Algoritmus používá myšlenku zlepšitelné cesty - tj. pokud existuje v grafu neorientovaná cesta ze do taková, že pro hrany ve směru od zdroje je a pro hrany ve směru ke zdroji , pak mohu tok zlepšit (o minimum rezerv). Algoritmus opakuje takovýto krok, dokud je možné ho provést. Neřeší výběr cesty, proto je dost pomalý a pokud nejsou hodnoty racionální čísla, může se i zacyklit.

Ve chvíli zastavení algoritmu získám max. tok, neboť množina ze do vede zlepšitelná cesta je v tom okamžiku řez (množina taková, že , ) a jeho velikost ( ) je stejná jako velikost získaného toku.

Algoritmus (Dinitzův algoritmus)

Řeší výběr zlepšitelné cesty - vybírá vždy nejkratší cestu (což obecně popisuje Edmunds-Karpův algoritmus). Dinitzova varianta používá síť rezerv, což je graf , kde hrana , pokud má tok hranou kladnou rezervu, tj. . Zlepšující cesta odpovídá normální orientované cestě v síti rezerv. Převod na pův. graf ze sítě rezerv je jednoduchý, mohu předpokládat, že jedním ze směrů mezi dvěma vrcholy neteče nic.

Průběh algoritmu: na začátku nastaví všem hranám rezervu . Potom postupuje po fázích - v 1 fázi:

- Vyhodí ze sítě rezerv všechny hrany, které nejsou na nejkratší cestě (2x prohledávání do šířky).
- Vezme jednu z nejkr. cest v síti rezerv a zlepší podle ní tok.
- Vyhodí vzniklé slepé cesty v síti rezerv (testuji jen hrany, co vyhazuji, a jejich konc. vrcholy)
- Toto opakuje, dokud jsou v síti rezerv cesty dané nejkratší délky.

Další fází algoritmus pokračuje, dokud existuje vůbec nějaká cesta v síti rezerv. Fází je tím pádem max. (max. délka cesty ze do ), v 1 fázi se prochází max. cest (klesá počet použitelných hran), nalezení 1 cesty je (jdu přímo) a vyhazování slepých cest max celkem za fázi (každou hranu vyhodím jen jednou). Celková složitost je tedy .

Algoritmus (Goldbergův algoritmus (preflow-push, algoritmus vlny))

Nehledá v grafu zlepšující cesty, v průběhu výpočtu v grafu není tok, ale vlna (ze zdroje teče vždy více nebo rovno než max. tok). Preflow - vlna - je funkce taková, že , tedy přebytky toku ve vrcholech () jsou povolené. Ve chvíli, kdy žádný vrchol nemá přebytek toku (), dostávám (maximální) tok. Pro každý vrchol si algoritmus pamatuje výšku . Také pracuje se sítí rezerv.

- Inicializace: , , , .
- Úvodní preflow: převede ze zdroje maximum možného ( po směru) do sousedních vrcholů.
- Hlavní cyklus: opakuje se, dokud existuje vnitřní vrchol s kladným . pro vrchol :
  - pokud existuje hrana nebo , t.ž. (v daném směru) a , potom se převede z do .
  - jinak se zvýší o 1.

Po celou dobu běhu algoritmu platí invariant . To zaručuje, že nalezený tok po zastavení je maximální (zdroj je ve výšce , stok 0, tedy každá cesta překonává někde rozdíl ). Vrcholy nejde zvedat donekonečna, takže se algoritmus zastaví: pro každý vnitřní vrchol platí, že je-li , pak existuje v síti rezerv cesta . To zaručuje, že - pokud mám vrchol tak, že a , potom existuje cesta s kladnými rezervami a podle invariantu jde každá hrana na ní max. o 1 nahoru (tedy max. o celkem).

Složitost Goldbergova algoritmu je .