\input lecnotes.tex

\prednaska{3}{Dinicùv algoritmus}{(zapsali Jakub Melka, Petr Musil)\foot{\rm s~díky Bernardovi Lidickému za obrázky}}

Na~minulé pøedná¹ce jsme si ukázali \s{Fordùv} algoritmus. Víme o~nìm, ¾e kdy¾ se zastaví, tak vydá maximální tok. Jen¾e zastavit se nemusí (napøíklad pro~sítì s~reálnými kapacitami), nebo trvá pøíli¹ dlouho.
Uká¾eme si lep¹í algoritmus, {\I Dinicùv}, který má výraznì men¹í slo¾itost a zastaví se v¾dy. 


Idea je následující: v~algoritmu budeme pou¾ívat {\I sí» rezerv}, která bude obsahovat rezervy -- kolik je¹tì po~dané hranì mù¾eme pustit, aby to nepøekroèilo její kapacitu.
Sí» rezerv pak budeme vyu¾ívat k~vylep¹ování toku.

\s{Definice:} {\I Sí» rezerv }$R$ k síti $S=(V,E,z,s,c)$ a toku $f$ v $S$ je  sí» $R=(V,E\cup\overleftarrow{E}, z,s, r)$, pro $\forall e\in E : $ 
\itemize\ibull
\:$r(e)=c(e)-f(e)$
\:$r(\overleftarrow{e})=f(e)$
\endlist
\>kde hrana $\overleftarrow{e}$ vznikne z~hrany $e$ tak, ¾e se zorientuje opaèným smìrem. V pøípadì, ¾e v~síti rezerv u¾ opaènì orientovaná hrana\foot{vznikne tak, ¾e v pùvodní síti jsou dvì opaènì orientované hrany mezi stejnými vrcholy.} je, pak vznikne multigraf\foot{graf, který mù¾e mít mezi dvìma vrcholy více stejnì orientovaných hran.} s~multiplicitou maximálnì 2.


\>Sí» rezerv budeme pou¾ívat v~algoritmu k~hledání vylep¹ujících tokù. K~tomu nám bude slou¾it následující vìta:

\s{Vìta:} Je-li $f$ tok v~síti $S$ a $g$ tok v~pøíslu¹né síti rezerv, pak $\exists$ tok $f'$ v $S$ takový, ¾e $\vert f'\vert = \vert f\vert + \vert g\vert$, co¾ znamená $\forall e \in E : f'(e) = f(e) + g(e) - g(\overleftarrow{e})$.

\proof
Rozebereme si jednotlivé pøípady pro~$\forall e\in E$. 
\numlist\nalpha
\:$g(e)=g(\overleftarrow{e})=0 \Rightarrow f'(e)=f(e) $.
\:$g(e)>0$ a zároveò $g(\overleftarrow{e})=0\Rightarrow f'(e) = f(e) + g(e)$.
\:$g(e)=0$ a zároveò $g(\overleftarrow{e})>0\Rightarrow f'(e) = f(e) - g(\overleftarrow{e})$.
\:nastává cirkulace, tu snadno odstraníme: odeèteme $\varepsilon$ od obou hran $e$ a $\overleftarrow{e}$,
kde $\varepsilon=\min( g(e), g(\overleftarrow{e})  )$. Pøevedeme tím tento pøípad na jeden ze tøí uvedených vý¹e.
\endlist

Je v¹ak $f'$ tok? Víme, ¾e $f'$ urèitì nemù¾e klesnout pod $0$, proto¾e se odeèítá jen v pøípadì c), a tam je z~definice vidìt, ¾e $f'$ pod $0$ klesnout nemù¾e. Kapacita také nemù¾e
být pøekroèena, pøièítá se jen v~pøípadì b) a z~definice se nepokazí, proto¾e $g(e)=c(e)-f(e)$, tedy v~nejhor¹ím pøípadì $f'(e) = c(e)$.

Dále doká¾eme, ¾e $f'$ dodr¾uje Kirchhoffùv zákon. V~následujících sumách pøedpokládejme, ¾e v¹echny vrcholy jsou rozdílné od~zdroje a stoku. Musí platit, ¾e:
$$\sum\limits_{ab \in E} f'(ab) = \sum\limits_{ba \in E} f'(ba).$$
Rozepí¹eme si tuto rovnici dle definice:
$$\sum\limits_{ab \in E} f'(ab) - \sum\limits_{ba \in E} f'(ba) = 0,$$
$$\sum\limits_{uv\in E}(f(uv)+g(uv)-g(\overleftarrow{uv})) - \sum\limits_{vu\in E}(f(vu)+g(vu)-g(\overleftarrow{vu})) = 0.$$
Roztrhneme si to na ètyøi sumy a dostaneme:
$$\underbrace{\sum\limits_{uv\in E}f(uv)-\sum\limits_{vu\in E}f(vu)}\limits_0+$$
$$+\underbrace{\sum\limits_{uv\in E}g(uv)-g(\overleftarrow{uv})-\sum\limits_{vu\in E}g(vu)-g(\overleftarrow{vu})}\limits_0 = 0,$$
nebo» $f$ i $g$ jsou toky a musí splòovat Kirchhoffùv zákon.
\qed

\>Tato vìta nám øíká, ¾e pokud existuje nenulový tok v~síti rezerv, pak lze tok v~pùvodní síti je¹tì zvìt¹it. Naopak pokud takový tok neexistuje, je tok v~pùvodní síti maximální.


\s{Definice:} $f$ je {\I blokující tok}, pokud na~ka¾dé orientované cestì $P$ ze~zdroje do~spotøebièe $\exists e\in P : f(e)=c(e)$.

\s{Definice:} $C$ je {\I proèi¹tìná sí»}, pokus obsahuje pouze vrcholy a hrany na~nejkrat¹ích $z\rightarrow s$ cestách. Proèi¹tìná sí» nemá slepé ulièky, ani hrany vedoucí ze~stoku nìkam do~dal¹ího vrcholu.

\figure{dinic-cistasit.eps}{Pøíklad proèi¹tìné sítì}{0.5\hsize}

\s{Dinicùv algoritmus}

\algo
\:$f\leftarrow$ nulový tok 
\:Sestrojíme sí» rezerv $R$, vynecháme hrany s nulovou rezervou.
\:$l\leftarrow$ délka nejkrat¹í cesty $z\rightarrow s$ cesty v $R$.
\:Kdy¾ $l=\infty$, tak skonèíme.
\:Sestrojíme proèi¹tìnou sí» $C$, a to následujícím zpùsobem:%\foot{Ponecháme vrcholy a hrany z $R$, které le¾í na nejkrat¹ích $z\rightarrow s$ cestách} 
\::spustíme BFS\foot{Breadth-First Search, standardní prohledávání do ¹íøky.} algoritmus ze zdroje
\::BFS nám rozdìlí uzly do vrstev, vyhodíme hrany za spotøebièem a slepé ulièky.
\:$g\leftarrow$ blokující tok v $C$.
\:Zlep¹íme tok $f$ podle $g$ a jdeme na bod 2.
\endalgo

\s{Postup tvorby proèi¹tìné sítì podrobnìji:} prohledáním do~¹íøky vytvoøíme vrstvy $C_i$, zahodíme ty za~spotøebièem, ponecháme
pouze hrany mezi $C_i$ a $C_{i+1}$. Je¹tì musíme odstranit slepé ulièky -- cesty, které konèí v~$C_m : m < l$, proto¾e ty urèitì nejsou souèástí nejkrat¹í $z\rightarrow s$ cesty.

Proèi¹tìní zvládneme v~lineárním èase $\O(N+M)$, v~pøípadì souvislého grafu pouze $\O(M)$. 


\figure{dinic-neprocistenasit.eps}{Pøíklad neproèi¹tìné sítì}{0.5\hsize}

Na obrázku neproèi¹tìné sítì vidíme, co se má smazat. Èerné hrany ponecháme, ty tam jsou správnì. Èervené hrany jsou zpìtné, ty sma¾eme. Modré hrany jsou hrany ve~stejné vrstvì, ty rovnì¾ sma¾eme. Èervené teèkované hrany nevedou vùbec do stoku, tak¾e ty rovnì¾ sma¾eme.

\s{Definice:} {\I Fází} algoritmu oznaèíme jeden bìh cyklu -- kroky 3 a¾ 9.

\>Provedeme podrobnou analýzu algoritmu z~hlediska slo¾itosti a uvidíme, ¾e má slo¾itost $\O(N^2M)$. Nejprve analyzujeme hledání
blokujícího toku, pak se podíváme, kolik fází maximálnì mù¾e Dinicùv algoritmus mít.


\s{Algoritmus hledání blokujícího toku}
\algo
\:$g\leftarrow$ nulový tok
\:Dokud $\exists z\rightarrow s$ cesta $P$ v proèi¹tìné síti $C$:
\::$\varepsilon \leftarrow \min\limits_{e\in P} (c(e)-f(e)) $
\::$\forall e \in P :g(e)\leftarrow g(e)+\varepsilon$, pokud $g(e)$ vzroste na $r(e)$, tak sma¾eme hranu $e$,
\::Doèistíme sí» tím, ¾e odstraníme slepé ulièky, které mohly vzniknout smazáním hrany $e$.
\endalgo

Pøi ka¾dém prùchodu se sma¾e v¾dy alespoò 1 hrana, tedy maximálnì $M$-krát provádíme $\O(N)$ -- právì tolik trvá nalezení cesty $P$, proto¾e délka cesty bude krat¹í nebo rovna $N$. Èi¹tìní pak maximálnì sma¾e celý graf, jedno mazání nás stojí konstantní èas, tedy celková slo¾itost tohoto algoritmu bude $\O(MN)$.

Doká¾eme si, ¾e poèet fází je men¹í nebo roven $N$. Algoritmus se ukonèí, pokud $l>N$, proto¾e pak u¾ neexistuje nejkrat¹í $z\rightarrow s$ cesta, pro¹li jsme v¹echny vrcholy.

\s{Lemma:} Pøi ka¾dé fázi $l$ vzroste alespoò o~jedna.

\proof
Uva¾me sí» $R$, rozdìlenou na~vrstvy, je¹tì pøed~proèi¹tìním. Po~proèi¹tìní nìkteré hrany zmizí. Pøibýt\foot{Pøibudou tak, ¾e po~hranì s~nulovým tokem po¹leme nìjaký tok, v~opaèném smìru v~síti rezerv vytvoøíme z~nulové hrany nenulovou.} mohou jen zrcadlové 
protìj¹ky ji¾ existujících hran.

Uva¾me cestu $P$ délky $< l$ ze $z\rightarrow s$ a $e$ novou hranu vzniklou pøi~poslání toku po~hranì s~nulovým tokem:
\numlist\nalpha
\:hrana $e \not\in P\Rightarrow$ -- zablokování, taková cesta neexistuje.
\:hrana $e \in P\Rightarrow$ délka $ > l$, proto¾e hrana $e$ vede z nìjakého vrcholu ve vrstvì $C_i$ do vrcholu ve vrstvì $C_{i-1}$.
\qeditem
\endlist

\s{Vìta:} Dinicùv algoritmus najde maximální tok v~èase $\O(MN^2)$.

\proof
Slo¾itost plyne pøímo z~pøedchozího lemmatu a slo¾itosti algoritmu hledání blokujícího toku.

Korektnost (najde v¾dy maximální tok) doká¾eme takto: Nech» algoritmus probìhne. Skonèit mù¾e jedinì tehdy, kdy¾ nenajde ¾ádnou cestu ze~zdroje do~spotøebièe v~síti rezerv, kterou by
mohl být tok vylep¹en. Tedy tok musí být nutnì maximální.
\qed


Takto napsaný algoritmus je je¹tì pøíli¹ pomalý, ale jde výraznì zrychlit. Napøíklad namísto pøepoèítávání tokù na~rezervy a naopak mù¾eme
minimálnì vnitøní cyklus poèítat jenom v~rezervách. Proèi¹tìní se dá dìlat jednou namísto dvakrát, mù¾eme prohledávat do~hloubky a mazat pøi vracení se z~vrcholù. Dokonce i~hledání blokujícího toku lze øe¹it v~rámci prohledávání do~hloubky. 
Cesta si pamatuje minimum rezerv a pøi vracení se rezerva sni¾uje.


\>Problematika tokù v~sítích má velké uplatnìní v~kombinatorice a teorii grafù. Zde uvedeme jeden pøíklad :


\>\s{Hledání maximálního párování v bipartitních grafech:} Zorientujeme v¹echny hrany zleva doprava a pøidáme zdroj, z~nìj
vedou hrany do~1.~partity, a stok, do~nìj vedou hrany z~2.~partity, hrany mezi partitami mají kapacitu 1.

\bye
