[ads2.git] / old / 2-dinic / 2-dinic.tex

\input lecnotes.tex

\prednaska{2}{Dinicùv algoritmus}{(zapsala Markéta Popelová)}


Na~minulé pøedná¹ce jsme si~ukázali Fordùv-Fulkersonùv algoritmus. Tento algoritmus hledal maximální tok tak, ¾e zaèal s~tokem nulovým a~postupnì ho zvìt¹oval. Pro~ka¾dé zvìt¹ení potøeboval v~síti najít cestu, na~které mají v¹echny hrany kladnou rezervu (po takovéto cestì mù¾eme poslat více, ne¾ po~ní aktuálnì teèe). Ukázali jsme, ¾e pokud takováto cesta existuje, jde tok vylep¹it (zvìt¹it). Zároveò pokud tok jde vylep¹it, pak takováto cesta existuje. Dokázali jsme, ¾e pro~racionální kapacity je algoritmus koneèný a~najde maximální tok.

Fordùv-Fulkersonùv algoritmus má ov¹em znaèné nevýhody. Funguje pouze pro~racionální kapacity a~je pomìrnì pomalý. Nyní si~uká¾eme jiný algoritmus, který nevylep¹uje tok pomocí cest, ale pomocí tokù\dots Budeme k~tomu potøebovat sí» rezerv.

\s{Definice:} {\I Sí» rezerv} k~toku~$f$ v~síti $S=(V,E,z,s,c)$ je sí» $R=(S,f)=(V,E,z,s,r)$, kde~$r(e)$ je rezerva hrany~$e$ v~toku~$f$.

\s{Konvence:} Pro~hranu~$e$ znaèí~$\overleftarrow{e}$ hranu opaènou. Napø. pokud $e=uv$, tak $\overleftarrow{e}=vu$.

Je dùle¾ité si~uvìdomit, ¾e sí» rezerv je závislá jak na~pùvodní síti~$S$, tak na~nìjakém toku~$f$ v~síti~$S$. Sí» rezerv~$R$ se~pak od sítì~$S$ li¹í pouze kapacitami -- sí»~$R$ má jako kapacitu hrany rezervu hrany v pùvodní síti. Pro~pøipomenutí: rezervu hrany~$e$ v~síti $S=(V,E,z,s,c)$ s~tokem~$f$ jsme si~definovali jako $r(e)=c(e) - f(e) + f(\overleftarrow{e})$.

Ne¾ si~uká¾eme samotný algoritmus, doká¾eme si~následující lemma.

\s{Lemma:} Pro~ka¾dý tok~$f$ v~síti~$S$ a~pro~ka¾dý tok~$g$ v~síti $R=(S,f)$ lze v~èase $\O(m)$ nalézt tok~$f'$ v~síti~$S$ takový, ¾e $\vert f' \vert = \vert f \vert + \vert g \vert$.

\proof

Dùkaz rozdìlíme do~tøí krokù. V~prvním kroku si~uká¾eme, jak budeme tok~$f'$ v~síti~$S$ konstruovat. V~druhém kroku doká¾eme, ¾e takto zkonstruované~$f'$ je opravdu tok. A~nakonec uká¾eme, ¾e splòuje po¾adovanou vlastnost, tedy ¾e jeho velikost je souèet velikostí tokù~$f$ a~$g$.

\>{\it 1. konstrukce~$f'$}

\noindent
Pro ka¾dou dvojici hran~$e, \overleftarrow{e}$ urèíme~$f'(e)$ a~$f'(\overleftarrow{e})$ následovnì:

\itemize\ibull
\:Pokud~$g(e) = g(\overleftarrow{e}) = 0$, pak nastavme:
        \itemize\ibull
        \:$f'(e) := f(e)$,
        \:$f'(\overleftarrow{e}) := f(\overleftarrow{e})$.
        \endlist
        
\:Pokud~$g(e) > 0$ a~$g(\overleftarrow{e}) = 0$, pak polo¾me:
        \itemize\ibull
        \:$\varepsilon := \min (g(e), f(\overleftarrow{e}))$,
        \:$f'(e) := f(e) + g(e) - \varepsilon$,
        \:$f'(\overleftarrow{e}) := f(\overleftarrow{e}) - \varepsilon$.
        \endlist

\:Pøípad~$g(e) = 0$ a~$g(\overleftarrow{e}) > 0$ vyøe¹íme obdobnì.

\:Pokud~$g(e) > 0$ a~$g(\overleftarrow{e}) > 0$, pak odeèteme od toku~$g$ cirkulaci po cyklu tvoøeném hranami~$e$ a $\overleftarrow{e}$:
        \itemize\ibull
        \:$\delta := \min (g(e),g(\overleftarrow{e}))$,
        \:$g'(e) := g(e) - \delta$,
        \:$g'(\overleftarrow{e}) := g(\overleftarrow{e}) - \delta$.     
        \endlist

        Tok $g'$ nyní spadá pod nìkterý z~pøedchozích pøípadù, které u¾ umíme vyøe¹it.
        
\endlist

\>{\it 2. $f'$ je tok}

\numlist{\ndotted}

\:Nejdøíve ovìøme první podmínku: $\forall e \in E: 0 \leq f(e) \leq c(e)$. Vezmìme libovolnou hranu~$e \in E$. Podle toho, co teèe po~hranách~$e$ a~$\overleftarrow{e}$ v~toku~$g$, jsme rozdìlili konstrukci toku na~tøi pøípady:

        \numlist{\ndotted}      
        
        \:Pokud po~hranách~$e$ a~$\overleftarrow{e}$ netekl ¾ádný tok~$g$, pak jsme nastavili $f'(e) := f(e)$ a~$f'(\overleftarrow{e}) := f(\overleftarrow{e})$. Tedy pokud~$f$ dodr¾oval kapacity, tak pro~$f'$ musí platit to samé.


        \:Pokud po~hranì~$e$ tekl tok~$g$ nenulový a~po opaèné nulový, tak jsme zvolili: $f'(e) := f(e) + g(e) - \varepsilon$. Víme, ¾e jsme si~$\varepsilon$ vybrali tak, ¾e $\varepsilon \leq g(e)$. Proto $f'(e) \geq 0$.

        Teï ovìøme, ¾e $f'(e) \leq c(e)$. V~pøípadì, ¾e $\varepsilon = g(e)$, tak $f'(e) = f(e) \leq c(e)$. V~opaèném pøípadì platí, ¾e $\varepsilon = f(\overleftarrow{e})$. Pak ov¹em
        $$f'(e) = f(e) + g(e) - f(\overleftarrow{e}) \leq $$
        $$\leq f(e) + \left[ c(e) - f(e) + f(\overleftarrow{e}) \right] - f(\overleftarrow{e}) = c(e).$$
        Vyu¾ili jsme, ¾e~$g$ je tok v~síti rezerv, tedy $g(e) \leq  c(e) - f(e) + f(\overleftarrow{e})$.

        Pro tok $f'(\overleftarrow{e})$ platí, ¾e $\varepsilon \leq f(\overleftarrow{e})$. Proto $f'(\overleftarrow{e}) = f(\overleftarrow{e}) - \varepsilon \geq 0$. Zároveò $f'(\overleftarrow{e}) \leq f(\overleftarrow{e}) \leq c(\overleftarrow{e})$.

        Tím jsme dokázali, ¾e~$f'(e)$ i~$f'(\overleftarrow{e})$ dodr¾ují kapacity.

        \:V posledním pøípadì tekl po~obou hranách kladný tok~$g$. Men¹í tok z~$g(e)$ a~$g(\overleftarrow{e})$ jsme vynulovali a~od vìt¹ího odeèetli ten men¹í. Tok~$g'(e)$ a~$g'(\overleftarrow{e})$ tedy zùstal korektní a~tok~$f'$ u¾ konstruujeme podle pøedchozího pøípadu.

        \endlist

\:Teï musíme je¹tì dokázat, ¾e nový tok neporu¹uje Kirchhoffovy zákony: $$\forall v~\in V \setminus \{z,s\}: f'^\Delta(v)=0.$$
        % neboli $$\forall v~\in V \setminus \{z,s\}: \sum_{u: uv \in E}{f'(uv)}=\sum_{u: vu \in E}{f'(vu)}.$$

        Vezmìme si~libovolnou hranu~$e = uv \in E$. Uvìdomme si, ¾e pøi~pøechodu z~$f(e)$ na~$f'(e)$ a~z~$f(\overleftarrow{e})$ na~$f'(\overleftarrow{e})$ bylo:
        \itemize\idot
        \:$f^\Delta(u)$ sní¾eno o~$g(e)$
        \:$f^\Delta(v)$ zvý¹eno o~$g(e)$.
        \endlist
        Seèteme-li úpravy na v¹ech hranách, dostaneme: $$f'^\Delta(v) = f^\Delta(v) + \sum_{u:uv \in E} g(uv) - \sum_{u:vu \in E} g(vu) =$$ $$= f^\Delta(v) + g^+(v) - g^-(v) = f^\Delta(v) + g^\Delta(v).$$

        Jeliko¾~$f$ byl tok, tak $f^\Delta(v) = 0$ a jeliko¾~$g$ byl tok, tak $g^\Delta(v) = 0$. Proto $f'^\Delta(v) = f^\Delta(v) + g^\Delta(v) = 0$.
        
\endlist

Tím jsme dokázali, ¾e~$f'$ je tok v~síti~$S$.

\>{\it 3. $\vert f' \vert = \vert f \vert + \vert g \vert$}

Pou¾ijme vztah pro souèet pøebytkù z pøedchozího kroku:
$$\vert f' \vert = f'^\Delta(s) = f^\Delta(s) + g^\Delta(s) = \vert f \vert + \vert g \vert.$$
\qed


Pro algoritmus budeme potøebovat vybírat kvalitní toky~$g$ v~síti rezerv. Pokud se~nám to bude daøit, bude se~tok~$f'$ rychle zvìt¹ovat, a¾ bychom mohli dojít k~maximálnímu toku. Nejlépe by se~nám hodily co nejvìt¹í toky v~síti rezerv. Kdybychom si~dali za cíl najít v¾dy maximální tok v~síti rezerv, výsledek by byl sice krásný (dostali bychom tak rovnou i~maximální tok v~pùvodní síti), ale problém hledání maximálního toku bychom pouze pøenesli na~jinou sí». Na¹e po¾adavky na~tento tok budou tedy takové, aby byl dostateènì velký, ale abychom bìhem jeho hledání nestrávili moc èasu. Podívejme se, jak se~s~tímto problémem vyrovná {\I Dinicùv algoritmus}. Nejdøíve si~ale zadefinujme nìkolik pojmù.

\s{Definice:} Tok~$f$ je {\I blokující}, jestli¾e pro~ka¾dou orientovanou cestu~$P$ ze~$z$ do~$s$ existuje hrana~$e \in P$ taková, ¾e $f(e) = c(e)$.

\s{Definice:} Sí» je {\I vrstevnatá (proèi¹tìná)}, kdy¾ v¹echny vrcholy a~hrany le¾í na~nejkrat¹ích cestách ze~$z$ do~$s$.

Dinicùv algoritmus zaèíná s~nulovým tokem. Potom v¾dy podle toku~$f$ sestrojí sí» rezerv a~v~ní vyma¾e hrany s~nulovou rezervou. Pokud v~této promazané síti rezerv neexistuje cesta ze~zdroje do~stoku, tak skonèí a~prohlásí tok~$f$ za maximální. Jinak proèistí sí» rezerv tak, aby se~z ní stala vrstevnatá sí» (rozdìlí vrcholy do~vrstev podle vzdálenosti od zdroje a~odstraní pøebyteèné hrany). Ve~vrstevnaté síti najde blokující tok, pomocí nìho¾ zlep¹í tok~$f$. Pak opìt pokraèuje sestrojením sítì rezerv na~tomto vylep¹eném toku~$f$ atd.

\figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do~vrstev}{0.4\hsize}

\s{Algoritmus (Dinicùv)}

\algo
\:$f \leftarrow$ nulový tok.
\:Sestrojíme sí» rezerv~$R$ a~sma¾eme $e: r(e) = 0$.
\:$l \leftarrow$ délka nejkrat¹í cesty ze~$z$ do~$s$ v~$R$.
\:Pokud $l = \infty$, zastavíme se~a vrátíme~$f$.
\:Proèistíme sí» $R \rightarrow$ sí»~$C$.
\:$g \leftarrow$ blokující tok v~$C$.
\:Zlep¹íme tok~$f$ pomocí~$g$.
\:GOTO 2.
\endalgo

\s{Pozorování:} Pokud se~algoritmus zastaví, vydá maximální tok.

\proof
Víme, ¾e~$f$ je stále korektní tok (jediné, jak ho mìníme je pøièítání toku~$g$, co¾ je, jak jsme si~dokázali, \uv{ne¹kodná operace}). Jakmile neexistuje cesta ze~$z$ do~$s$ v~$R$, tak je $f$ maximální tok, nebo» v~tuto dobu by se~zastavil (a vydal maximální tok) i~Fordùv-Fulkersonùv algoritmus, který je korektní.
\qed

A teï je¹tì musíme ujasnit, jak budeme èistit sí» rezerv a~vybírat blokující tok~$g$.

\s{Algoritmus proèi¹tìní sítì rezerv}

\algo
\:Rozdìlíme vrcholy do~vrstev podle vzdálenosti od~$z$.
\:Odstraníme vrstvy za~$s$ (tedy vrcholy, které jsou od~$z$ vzdálenìj¹í ne¾~$s$), hrany do~minulých vrstev a~hrany uvnitø vrstev.
\:Odstraníme \uv{slepé ulièky}, tedy vrcholy s~$\deg^{out}(v) = 0$, a~to opakovanì pomocí fronty. (Nejdøíve zaøadíme do~fronty v¹echny vrcholy s~ $\deg^{out}(v) = 0$. Pak dokud není fronta prázdná, v¾dy vybereme vrchol~$v$ z~fronty, odstraníme~$v$ a~v¹echny hrany~$uv$. Pro~ka¾dý takový vrchol~$u$ zkontrolujeme, zda se~tím nesní¾il výstupní stupeò vrcholu~$u$ na~nulu ($\deg^{out}(u) = 0$). Pokud sní¾il, tak ho zaøadíme do~fronty.)
\endalgo

\figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a~slepé ulièky.}{0.45\hsize}

Hledání blokujícího toku zaèneme s~tokem nulovým. Pak vezmeme v¾dy orientovanou cestu ze~zdroje do~stoku v~síti~$C$. V~této cestì najdeme hranu s~nejni¾¹í hodnotou výrazu $r(e) - g(e)$ (neboli $c(e) - f(e)$ v~pùvodní síti). Tuto hodnotu oznaèíme~$\varepsilon$. Pak ke~ v¹em hranám na~této cestì pøièteme~$\varepsilon$. Pokud tok~$g$ na~nìjaké hranì dosáhne kapacity hrany, co¾ je zde~$r(e)$, tak hranu vyma¾eme. Následnì sí» doèistíme, aby splòovala podmínky vrstevnaté sítì. A~pokud je¹tì existuje nìjaká orientovaná cesta ze~zdroje do~stoku, tak opìt pokraèujeme s~touto cestou.

\s{Algoritmus hledání blokujícího toku}

\algo
\:$g \leftarrow$ nulový tok.
\:Dokud existuje orientovaná cesta~$P$ ze~$z$ do~$s$ v~$C$, opakuj:
\::$\varepsilon \leftarrow \min_{e \in P} (r(e) - g(e))$.
\::Pro~$\forall e \in P: g(e) \leftarrow g(e) + \varepsilon$.
\:::Pokud $g(e) = r(e)$, sma¾eme~$e$ z~$C$.
\::Doèistíme sí» zase pomocí fronty.
\endalgo

\s{Èasová slo¾itost} Rozeberme si~jednotlivé kroky algoritmu.

\numlist{\ndotted}
\:Inicializace toku~$f$ \dots $\O(m)$.
\:Sestrojení sítì rezerv a~smazání hran s~nulovou rezervou \dots $\O(m + n)$.
\:Najití nejkrat¹í cesty (prohledáváním do~¹íøky) \dots $\O(m + n)$.
\:Zkontrolování délky nejkrat¹í cesty \dots $\O(1)$.
\:Proèi¹tìní sítì \dots $\O(m + n)$.
        \numlist{\ndotted}
        \:Rozdìlení vrcholù do~vrstev -- provedlo ji¾ prohledávání do~¹íøky \dots $\O(1)$.
        \:Odstranìní nìkterých hran \dots $\O(m + n)$.
        \:Odstranìní \uv{slepých ulièek} pomocí fronty -- ka¾dou hranu odstraníme nejvý¹e jedenkrát, ka¾dý vrchol se~dostane do~fronty nejvý¹e jedenkrát \dots $\O(m + n)$.
        \endlist
\:Najití blokujícího toku~$g$ \dots $\O(m \cdot n)$.
        \numlist{\ndotted}
        \:Inicializace toku~$g$ \dots $\O(m)$.
        \:Najití orientované cesty v~proèi¹tìné síti rezerv (staèí vzít libovolnou cestu ze~zdroje, nebo» ka¾dá z~nich v~této síti vede do~stoku) \dots $\O(n)$.
        \:Výbìr minima z~výrazu $r(e) - g(e)$ pøes v¹echny hrany cesty -- ta mù¾e být dlouhá nejvý¹e~$n$ \dots $\O(n)$.
        \:Pøepoèítání v¹ech hran cesty \dots $\O(n)$.
        \:Smazání hran cesty, jejich¾ tok~$g(e)$ se~zvý¹il na~hodnotu~$r(e)$ \dots $\O(n)$.
        \:Doèi¹»ování vyøe¹me zvlá¹».
        \endlist
        
        Vnitøní cyklus (kroky 2 a¾ 6) provedeme nejvý¹e~$m$ krát, nebo» pøi~ka¾dém prùchodu vyma¾eme alespoò jednu hranu (tak jsme si~volili~$\varepsilon$).
        
        Èi¹tìní bìhem celého hledání blokujícího toku~$g$ v~proèi¹tìné síti rezerv trvá dohromady $\O(m + n)$, nebo» ka¾dou hranu a~vrchol sma¾eme nejvý¹e jedenkrát.
        
        Najití blokujícího toku bude tedy trvat $\O(m \cdot n + (m + n)) = \O(m \cdot n)$.
        
\:Zlep¹ení toku~$f$ pomocí toku~$g$ \dots $\O(m)$.
\:Skok na~2. krok \dots $\O(1)$.
\endlist

Zbývá nám jen urèit, kolikrát projdeme vnìj¹ím cyklem (fází). Doká¾eme si~lemma, ¾e hodnota~$l$ vzroste mezi prùchody vnìj¹ím cyklem (fázemi) alespoò o~1. Z~toho plyne, ¾e vnìj¹ím cyklem mù¾eme projít nejvý¹e $n$-krát, nebo» cesta v síti na~$n$ vrcholech mù¾e být dlouhá nejvý¹e $n$.

Uvìdomme si, ¾e uvnitø vnìj¹ího cyklu pøevládá èlen $\O(m \cdot n)$, tak¾e celková èasová slo¾itost bude $\O(n^2 \cdot m)$.

\s{Lemma:} Hodnota~$l$ (délka nejkrat¹í cesty ze~$z$ do~$s$ v~proèi¹tìné síti) vzroste mezi fázemi alespoò o~1.

\proof

Podíváme se~na~prùbìh jednoho prùchodu vnìj¹ím cyklem. Délku aktuálnì nejkrat¹í cesty ze~zdroje do~stoku oznaème~$l$. V¹echny pùvodní cesty délky~$l$ se~bìhem prùchodu zaruèenì nasytí, proto¾e tok~$g$ je blokující. Musíme v¹ak dokázat, ¾e nemohou vzniknout ¾ádné nové cesty délky~$l$ nebo men¹í. V~síti rezerv toti¾ mohou hrany nejen
ubývat, ale i~pøibývat: pokud po¹leme tok po~hranì, po~které je¹tì nic neteklo, tak v~protismìru z~dosud nulové rezervy vyrobíme nenulovou. Rozmysleme si~tedy, jaké hrany mohou pøibývat.

Hrany mohou pøibývat jen tehdy, kdy¾ jsme po~opaèné hranì nìco poslali. Ale my nìco posíláme po~hranách pouze z~vrstvy do~té následující. Hrany tedy pøibývají do~minulé vrstvy.

Vznikem nových hran by proto mohly vzniknout nové cesty ze~zdroje do~stoku, které pou¾ívají zpìtné hrany. Jen¾e cesta ze~zdroje do~stoku, která pou¾ije zpìtnou hranu, musí alespoò jednou skoèit o~vrstvu zpìt a~nikdy nemù¾e skoèit o~více ne¾ jednu vrstvu dopøedu, a~proto je její délka alespoò $l+2$. Pokud cesta novou zpìtnou hranu nepou¾ije, má buï délku~$> l$, co¾ je v~poøádku, nebo má délku~$= l$, pak je zablokovaná.

Tím je lemma dokázáno.
\qed

\figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.4\hsize}

V¹echna dokázaná tvrzení mù¾eme shrnout do~následující vìty:

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

\s{Poznámka:} Algoritmus se~chová hezky na~sítích s~malými celoèíselnými kapacitami, ale kupodivu i~na~rùzných jiných sítích. Èasto se~pou¾ívá, nebo» se~chová efektivnì. A~je mnoho zpùsobù, jak ho je¹tì vylep¹ovat, èi odhadovat ni¾¹í slo¾itost na~speciálních sítích.

\s{Poznámka:} Algoritmus nevy¾aduje racionální kapacity! Dal¹í z~dùvodù, proè maximální tok existuje i~v~síti s~iracionálními kapacitami.


%k,s,v,na,do,ke,pro,pøi,a,u,i,po,

\bye