ADS2 Jiří Kalvoda: Cvičení 6

Also available as: PDF Markdown

Informace k cv. jsou na https://kam.mff.cuni.cz/~jirikalvoda/vyuka/25z/ads2.

Toky v sítích

Dinicův algoritmus:

Začneme s prázdným tokem $f$ .
Iterativně vylepšujeme tok pomocí zlepšujících toků: (vnější cyklus)
1. Sestrojíme síť rezerv: vrcholy a hrany jsou tytéž, kapacity jsou určeny rezervami v původní síti. Dále budeme pracovat s ní.
2. Najdeme nejkratší $st$ -cestu. Když žádná neexistuje, skončíme.
3. Pročistíme síť, tj. ponecháme v ní pouze vrcholy a hrany na nejkratších $st$ -cestách.
4. Najdeme v pročištěné síti blokující tok $f_B$ $f_{B}$ :
  1. $f_B$ ← prázdný tok
  2. Postupně přidáváme $st$ $s t$ -cesty: (vnitřní c.) $\O(mn)$ $O (mn)$
    1. Najdeme st-cestu. Např. hladově – „rovnou za nosem“.
    2. Pošleme co nejvíce po nalezené cestě.
    3. Smažeme nasycené hrany.
    4. Dočistíme síť.
5. Zlepšíme $f$ podle $f_B$

Goldbergův algoritmus

Vlna je tok, až na to, že v libovolných vrcholech můžou být kladné přebytky.

Nastavíme počáteční výšky $h(v)$ : Zdroj ve výšce $n$ , ostatní $0$ .
Vytvoříme počáteční vlnu: Všechny hrany ze zdroje na maximum, jinde $0$ .
Dokud existuje vrchol $u \not= s, t$ $u \neq = s, t$ co má kladný přebytek ( $f^{\Delta} > 0$ $f^{Δ} > 0$ ):
1. Pokud existuje hrana $uv$ s neprázdou rezervou $r(uv) > 0$ a $h(u) > h(v)$ , převedeme co nejvíce z přebytku po hraně $uv$ .
2. V opačném případě zvedneme $u$ o jedna.

Převedení je syté, když použije celou rezervu hrany, jinak je nenasycené a tehdy převede veškerý přebytek.

Úloha 1 (Důkaz): Dokažte následující lemátka (důkaz už zazněl na přednášce, ale měl by jít snadno vymyslet).

Spád: Kdykoliv je hrana $uv$ nenasycená, tak $h(u)-h(v) \le 1$ , tedy hrana nevede dolů o více než jednu úroveň.
Korektnost: Pokud algoritmus zastaví, tak je korektní (vrátí tok a navíc ten je maximální).
Cesta do zdroje: Pokud je ve vrcholu $v$ nenulový přebytek, tak existuje v grafu nenasycených hran cesta $v \rightarrow s$ .
Výška: Pro každý vrchol $h(v) \leq 2n$ .
Počet zvednutí: Počet zvednutí je $\le 2n^2$ .
Sytá převedení: Sytých převedení je $\le nm$ .
Nenasycená převedení: Nenasycených převedení je $\O(n^2m)$ . [Potenciál $\sum_{v\neq s,t, \hbox{s nenulovým přebytkem}} h(v)$ .]
Časová složitost: Algoritmus doběhne v $\O(n^2m)$ .

Hinty:

Indukcí.
Ukažte, že neexistuje nenasycená cesta, budou se hodit výšky a předešlé lemma.
Sčítejte přebytky přes množinu vrcholů
Co by se stalo, kdybychom zvedali vrchol ve výšce $2n$ .
Bude se hodit 4.
Spočítejte to pro každou hranu zvlášť.
O kolik nejvýše zvedne potenciál syté převedení a zvednutí vrcholu? O kolik minimálně nenasycené převedení sníží potenciál.
Stačí použít předešlé lemátka.

Úloha 2 (Implementace): Navrhněte implementaci Goldbergova algoritmu se zvedáním nejvyššího vrcholu s přebytkem. Počet nenasycených převedení v takovém případě je $\O(n^2 \sqrt{m})$ (důkaz lze najít v Průvodci). Naším cílem je implementace o stejné složitosti.

Úloha 3 (Jednotkové kapacity): Rozeberte chování Goldbergova algoritmu na sítích s jednotkovými kapacitami. Bude rychlejší než ostatní algoritmy? Nebo alespoň stejně rychlý?

Úloha 4 (Výška zdroje): Co by se stalo, kdybychom v inicializaci Golbergova algoritmu umístili zdroj do výšky $n-1$ , $n-2$ , nebo dokonce $n-3$ ? Rozmyslete si, která vlastnost (skončí, vydá maximální tok, …) na výšce zdroje závisí a mohla by se tím pokazit.

Úloha 5 (Pokrytí): Množinu vrcholů takovou, že každá hrana sousedí alespoň s jedním vrcholem z množiny, nazvěme . Navrhněte algoritmus pro nalezení nejmenšího vrcholového pokrytí v bipartitním grafu. Z toho odvoďte vztah pro velikosti nejmenšího vrcholového pokrytí a největšího párování v bipartitních grafech