V algoritmech vylepšující cesty se tok podél jedné hrany postupně nasčítává z toků podél vylepšujících cest. Těchto cest může být poměrně mnoho a nalezení zlepšující cesty může trvat až $\OO(n)$. Proto se naskýtá myšlenka, jestli nemůžeme tok podél hrany poslat naráz.

V další sekci si ukážeme Push-relabel algoritmus, který je založen na daleko jednodušší myšlence než jsou vylepšující cesty. Algoritmus používá dvě základní operace: protlačení toku po hraně (push)1 a zvýšení výšky vrcholu (relabel). Proto se algoritmus nazývá push-relabel. Algoritmus vymyslel Goldberg v roce 1985. Varianta, kterou si ukážeme je podle Goldberga a Tarjana z roku 1988.

Připomeňme, že $G$ je orientovaný graf, jehož hrany jsou ohodnoceny kapacitami $c:E \to\RR_+$. Graf $G$ rozšíříme tak, aby ke každé hraně $uv$ existovala opačná hrana $vu$. Přidávané hrany budou mít kapacitu nula, takže nijak neovlivní tok v síti (ve skutečnosti žádné hrany přidávat nemusíme, používáme je jen pro zjednodušení definice rezervy). Rozšířenému grafu budeme říkat původní síť.

Budeme pracovat s pomocným grafem $G_f$ (síť rezerv) podobně jako v algoritmech pracujících s vylepšující cestou. Pro dvojici $G$ a $f$ dáme do grafu $G_f$ každou hranu původního grafu s nenulovou rezervou. Připomeňme, že rezerva hrany $uv$ je $r(uv)=(c(uv)-f(uv))+ f(vu)$. Rezerva $r(uv)$ znamená, že můžeme skrz hranu $uv$, případně hranu $vu$, protlačit $r(uv)$ jednotek toku z vrcholu $u$ do vrcholu $v$. Aby v původním grafu po dvojici hran $uv$, $vu$ neproudil tok tam i zpět, tak nejprve protlačíme co největší část toku v protisměru po $vu$ a pak teprve zbytek toku po $uv$. Změnou toku se změní i pomocný graf $G_f$.

Dále připomeňme, že $f(v)$ značí bilanci vrcholu $v$, nebo také přebytek toku ve vrcholu $v$.

Myšlenka protlačování

Nejprve zavedeme jeden klíčový pojem. Funkce $f:E\to\RR_+$ je pratok2, pokud splňuje
$$\begin{eqnarray} i) & 0\leq f(e) \leq c(e) & \mbox{pro každou hranu $e\in E $}\\ ii) & f(v)\geq 0& \mbox{pro každý vrchol $v\in V\setminus\{s,t\}$} \end{eqnarray}$$

Řekneme, že vrchol $v\in V\setminus\{s,t\}$ je aktivní, pokud $f(v)>0$. Tedy pokud do vrcholu přitéká více, než z něj odtéká. Vrcholy $s$, $t$ nejsou nikdy aktivní.

Jak se liší pratok od toku? V definici toku platí druhá podmínka s rovností ($f(v)=0$ pro každý vrchol $v\in V\setminus\{s,t\}$).

Podívejme se na základní myšlenku push-relabel algoritmu. Nejprve protlačíme ze zdroje co největší tok do sousedních vrcholů. Dále budeme probírat aktivní vrcholy a snažit se protlačit přebytek toku v nich do sousedních vrcholů směrem ke spotřebiči. Při protlačování toku nesmíme překročit kapacitu hran. Protlačování bude probíhat pouze po hranách s nenulovou rezervou. Postupně budeme chtít protlačit všechny přebytky toku až do spotřebiče. Když to nepůjde, tak je protlačíme zpátky do zdroje.

Podívejme se na příklad sítě na obrázku, ve které najdeme maximální tok pomocí protlačování toku po hranách.

Průběh protlačování toku si můžeme představit jako vlnu, která se šíří ze zdroje do spotřebiče. Tam se odrazí a valí se zpátky do zdroje. Jednotlivé kroky protlačování jsou na následujících obrázcích. U každé hrany na obrázku je hodnota “$f(e)/c(e)$”. Ve vrcholech je uvedeno jméno vrcholu a aktuální přebytek toku. V první fázi postupně protlačujeme co nejvíce toku ze zdroje směrem ke spotřebiči. Ve zdroji $s$ je nekonečně mnoho vody a tak po hraně $sa$ protlačíme $5$ jednotek toku do $a$. V dalším kroku protlačíme po hraně $ab$ co největší část přebytku $f(a)$. Dále postupujeme podobně a to tak dlouho, dokud nedorazíme do spotřebiče.




Do spotřebiče jsme dotlačili největší možný tok, ale vrcholy $a$, $b$ jsou stále aktivní. V grafu $G_f$ nevede orientovaná cesta z aktivních vrcholů do spotřebiče $t$ a proto nastane druhá fáze, ve které dotlačíme přebytek toku z aktivních vrcholů zpátky do zdroje.


Skončili jsme s maximálním tokem.

Na cestě je hledání toku jednoduché, ale v jakém pořadí provádět jednotlivá protlačení v obecném grafu?

Musíme si dát pozor, abychom se nezacyklili. Například by se mohlo stát, že budeme neustále protlačovat tok po jedné hraně tam a zpátky, tam a zpátky,…

Rozhodování, podél kterých hran budeme tok protlačovat, provedeme na základě odhadu vzdáleností v $G_f$. Přebytky toku budeme protlačovat po nejkratších cestách do spotřebiče. Za chvíli si vysvětlíme, co je to výška každého vrcholu. Dolním odhadem vzdálenosti dvou vrcholů potom bude jejich výškový rozdíl. Samotný algoritmus nebude přemýšlet nad nejkratšími cestami do spotřebiče, ale bude tok posílat po libovolné hraně vedoucí z kopce dolů.

Platné označkování a výšky vrcholů


Vektor $d\in (\NN_0\cup\{\infty\})^n$ nazveme platné označkování3 vrcholů vzhledem k toku $f$, pokud $$\begin{eqnarray} i) & d(s)=n,\quad d(t)=0, &\\ ii) & d(v)\leq d(w)+1 & \mbox{pro každou hranu $vw \in E(G_f)$.} \end{eqnarray}$$

Pod hodnotou $d(v)$ si budeme představovat výšku, ve které se vrchol $v$ nachází. Protlačování toku budeme provádět podél hran vedoucích z kopce dolů. To je tak, jak voda přirozeně teče. Platné označkování říká, že zdroj bude vždy ve výšce $n$, spotřebič ve výšce $0$. Neklade žádná omezení na stoupání, ale říká, že žádná hrana $G_f$ nevede příliš strmě dolů.4 Hrana může klesat nejvýše o jedna.

Z existence platného označkování vrcholů vyplývá důležitá vlastnost pratoku, která říká, že pratok “nasycuje” jistý řez. Řez $\delta(R)$ je nasycený, pokud pro každou hranu $e\in \delta(R)$ je $f(e)=c(e)$ a pro každou hranu $\delta(\overline{R})$ je $f(e)=0$. Připomeňme, že tok je vždy menší roven velikosti řezu. Pokud pro tok $f$ najdeme řez $\delta(R)$ nasycený tokem $f$, tak víme, že je tok maximální (platí $c(\delta(R))=|f|$).

Lemma 1: Nechť $f$ je pratok a $d$ je platné označkování pro $f$. Potom existuje nasycený $(s,t)$-řez $\delta(R)$.
Důkaz: Protože má graf $G_f$ jen $n$ vrcholů, tak existuje hodnota $k$, $0\lt k\lt n$, taková, že $d(v)\not=k$ pro všechny vrcholy $v\in V$. Položme $R=\{ v\in V\,:\, d(v)\gt k \}$. Potom $s\in R$ a $t\not\in R$, protože $d(s)=n$ a $d(t)=0$. Z bodu ii) definice platného označkování plyne, že žádná hrana $G_f$ nevede z $R$ ven, protože nemůže klesnout o více než jedna.
Důsledek 1: Pokud existuje platné označkování pro tok $f$, tak je tok $f$ maximální.

Důsledek nám dává podmínku pro zastavení algoritmu. Push-relabel algoritmus si neustále udržuje platný pratok a platné označkování (tedy i nasycený řez). Skončí v momentě, kdy se z pratoku stane tok. V jistém smyslu je duální k algoritmům vylepšující cesty, protože ty si udržují platný tok a skončí, až se některý řez nasytí.

Připomeňme, že $d_f(v,w)$ je orientovaná vzdálenost v grafu $G_f$, tj. počet hran na nejkratší orientované cestě z $v$ do $w$.

Ukážeme si, že rozdíl výšek dvou vrcholů je dolním odhadem jejich vzdálenosti v $G_f$.

Lemma 2 (dolní odhad vzdálenosti 2 vrcholů): Nechť $f$ je pratok a $d$ platné označkování. Potom pro každé dva vrcholy $v,w\in V$ platí $ d_f(v,w)\geq d(v) – d(w)$.
Důkaz: Pokud je $d_f(v,w)=\infty$, tak lemma platí. Předpokládejme tedy, že je $d_f(v,w)$ konečné. Uvažme nejkratší orientovanou $(v,w)$-cestu v $G_f$. Pro každou hranu $pq$ orientované cesty z definice platného označkování platí $d(p)-d(q)\leq 1$. Sečtením těchto nerovností podél hran orientované cesty dostaneme výsledek.5

Ve speciálním případě lemma říká, že

  • $d(v)$ je dolním odhadem na $d_f(v,t)$ a že
  • $d(v)-n$ je dolním odhadem na $d_f(v,s)$.

Poznamenejme, že $d(v)\geq n$ znamená, že $d_f(v,t)=\infty$. Tedy že v $G_f$ nevede orientovaná cesta z $v$ do spotřebiče $t$ a proto by se měl v tomto případě posílat přebytek toku ve $v$ zpátky do zdroje. Bez ohledu na velikost $d(v)$ budeme protlačovat tok z kopce dolů. Tedy z vrcholu $v$ do vrcholů $w$ s $d(w)\lt d(v)$, protože se tím podle odhadů dostane tok z $v$ blíže k místu určení.

Poznámka (o výpočtu platného označkování): Důkaz lemmatu nám naznačuje, jak si spočítat platné označkování, pokud bychom ho neznali. Nejprve se podívejme na speciální případ, kdy ze všech vrcholů kromě $s$ existuje v síti rezerv $G_f$ orientovaná cesta do $t$. Za výšky $d(v)$ zvolíme délku nejkratší cesty z $v$ do $t$, jinými slovy $d(v):=d_f(v,t)$. Potom označkování vrcholů $d(v)$ splňuje vlastnosti platného označkování až na podmínku $d(s)=n$. Hodnotu $d(s)$ si můžeme zvolit jak chceme, protože v síti $G_f$ nevede z $s$ žádná hrana do ostatních vrcholů. Jinak by v $G_f$ existovala i cesta z $s$ do $t$. (Všechny hrany vedoucí z $s$ jsou nasycené a tudíž nejsou v síti $G_f$).

V obecném případě zvolíme $d(v):=\min\{ d_f(v,t),\; n+d_f(v,s) \}$. Důkaz, že takto dostaneme platné označkování, necháme jako cvičení. Poznamenejme jenom, že množina vrcholů, ze kterých v $G_f$ vede orientovaná cesta do $t$, určuje nasycený řez.

Výpočtu platného označkování využijeme později v heuristice na straně \pageref{push_relabel_heuristic}.