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.

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.

Než se pustíte do dalšího čtení, prostudujte si myšlenku protlačování toku po hraně a platné označkování vrcholů.

Push-Relabel algoritmus


Inicializace: Začneme s počátečním pratokem $f$ takovým, že $f(e)=c(e)$ pro hrany $e\in E$ vedoucí ze zdroje $s$ a $f(e)=0$ pro ostatní hrany. Položme $d(s)=n$ a $d(v)=0$ pro všechny ostatní vrcholy $v$. Označkování $d$ je platným označkováním pro pratok $f$, protože všechny hrany $G_f$ mají oba konce ve výšce nula.

Hlavním úkolem ve zbytku algoritmu je likvidovat aktivní vrcholy, protože až v grafu nebude existovat aktivní vrchol, tak se pratok stane tokem. Při zpracování vrcholů nám pomohou následující operace.

Operace protlač: Operaci protlačení toku po hraně $vw\in E(G_f)$ nazveme protlač($vw$) (anglicky se nazývá push). Jak už jsme řekli, přebytek toku budeme protlačovat pouze po hranách vedoucích z kopce dolů. Tedy při protlačení toku po hraně $vw\in E(G_f)$ je $d(w)\lt d(v)$. Protože hrany sítě rezerv nemohou klesat nejvíce o jedna, musí být $d(v)=d(w)+1$. Abychom měli co protlačovat, tak musí být ve $v$ kladný přebytek toku. To znamená, že $v$ musí být aktivní vrchol. Protlačování proto může probíhat pouze po hranách, které vedou z aktivních vrcholů a klesají právě o jedna. Takové hrany nazveme přípustné.

Hrana $uv$ se při protlačení buď nasytí a zmizí z $G_f$, nebo se nenasytí a zůstane v $G_f$. Do sítě rezerv přibude zpětná hrana $wv$, která vede do kopce. Jiné změny v $G_f$ nejsou a proto po protlačení toky po $vw$ zůstane označkování $d$ platné.

Operace zvýšení: Předpokládejme, že $v$ je aktivní, ale z $v$ už v $G_f$ nevede žádná přípustná hrana. Potom můžeme zvýšit $d(v)$ na $\min\{d(w)+1 \,|\, vw\in E(G_f)\}$, aniž bychom porušili platnost označkování. Této operaci budeme říkat zvýšení vrcholu $v$ (anglicky se označuje relabel nebo lift). Jinými slovy, aktivní vrchol $v$ zvedáme o jedničku tak dlouho, dokud některá hrana z vrcholu vycházející nepovede z kopce.

Je spousta výsledků o tom, v jakém pořadí se mají operace provádět. My si předvedeme obecnější verzi algoritmu. Jakmile vybereme aktivní vrchol $v$, tak budeme provádět operaci protlač po přípustných hranách $G_f$ tak dlouho, dokud se vrchol $v$ nestane neaktivním a nebo dokud ho nezvýšíme. Tuto posloupnost operací označíme jako zpracování vrcholu.

Zpracuj(v):

	 while $v$ je aktivní a existuje přípustná hrana $vw\in E(G_f)$  do
	 	 Protlač co největší část přebytku ve $v$ po hraně $vw$
	 if $v$ je aktivní then
	 	 Zvyš vrchol $v$

Samotný algoritmus potom můžeme vyjádřit následovně.

Push-Relabel:

	 Inicializuj $f$ a $d$ 
	 while $f$ není tok do
	 	 Vyber aktivní vrchol $v$
	 	 Zpracuj $v$

Je několik různých pravidel pro výběr aktivního vrcholu.

  • Vybereme vrchol $v$ s maximálním označením $d(v)$. Algoritmus s tímto pravidlem se označuje jako maximum distance push-relabel.2 Toto pravidlo se používá nejčastěji, protože garantuje nejlepší časovou složitost algoritmu.
  • Aktivní vrcholy vkládáme do fronty. Aktivní vrcholy zpracováváme v pořadí, jak jsou ve frontě. (Pokud vrchol zůstal po zpracování aktivní, tak se ocitne na konci fronty). Algoritmus s tímto pravidlem se označuje jako FIFO push-relabel.

Algoritmus si v průběhu udržuje platný pratok a také platné označkování. Při popisu operací jsme ověřili, že se provedením operace platnost označkování nezmění. Proto z důsledku [ref]corollary_oznac_tok[/ref] dostáváme, že pokud nebude existovat aktivní vrchol, tak se algoritmus zastaví a skončí s maximálním tokem.


Příklad

Na následujícím obrázku je graf, ve kterém chceme najít maximální tok pomocí algoritmu push-relabel. Použijeme pravidlo, které si vždy vybere aktivní vrchol s největším $d(v)$. Pokud mají dva vrcholy stejnou hodnotu $d(v)$, tak vybereme ten abecedně menší. V každém vrcholu $v$ probíráme přípustné hrany $vw$ v abecedním pořadí podle $w$.

Nejprve provedeme inicializaci a dostaneme ohodnocený graf na následujícím obrázku vlevo. Pozor, hodnota u vrcholu $v$ není rezerva, ale výška $d(v)$. Po inicializaci jsou vrcholy $c$, $d$ aktivní. Vybereme si $c$ a zvýšíme $d(c)$ na $1$. V dalším kroku protlačíme po hraně $ca$ tok velikosti $1$. Po tomto kroku už jsou všechny kroky algoritmu jasně určeny. Doporučujeme čtenáři, aby si odkrokoval zbytek algoritmu. Aktivní vrcholy zvolené algoritmem jsou $c$, $a$, $d$, $d$, $a$, $a$, $d$, $a$, $d$, $a$, $d$, $a$, $d$, $c$, $b$ a postupně algoritmus protlačuje tok po hranách $ca$, $at$, $db$, $da$, $ac$, $ad$, $da$, $ad$, $da$, $ad$, $ds$, $cb$, $bt$ (aktivní vrchol většinou zvedáme o $1$, párkrát o $2$ a v předposledním případě vůbec). Pro lepší pochopení si v každém kroku načtněte graf $G_f$, ať vidíte, které hrany jsou nasycené a vypadly. Algoritmus skončí s tokem a označkováním na následujícím obrázku vpravo.3

Výsledné označkování neobsahuje žádný vrchol s $d(v)=5$ a proto množina $R=\{s,d,a\}$ určuje minimální řez (viz lemma 1).