[ads2.git] / 3-dinic / 3-dinic.tex

\input lecnotes.tex

\prednaska{3}{Dinicùv algoritmus}{}

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

\h{Sí» rezerv a zlep¹ující toky}

\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$ pøi toku~$f$.

Je dùle¾ité si~uvìdomit, ¾e sí» rezerv konstruujeme pro konkrétní tok v~pùvodní síti.
Od pùvodní sítì se li¹í pouze tím, ¾e kapacit hran jsme nahradili jejich rezervami.
Pøipomeòme je¹tì, ¾e rezervu hrany~$uv$ jsme definovali jako
$$r(uv) = c(uv) - f(uv) + f(vu).$$
Nyní uká¾eme, jak toky zlep¹ovat pomocí tokù v~pøíslu¹né síti rezerv:

\s{Lemma (o~zlep¹ování tokù):} Pro libovolný tok~$f$ v~síti~$S$ a libovolný 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
Nejprve uká¾eme, jak tok~$f'$ sestrojit. V~druhém kroku doká¾eme, ¾e konstrukce
opravdu dává korektní tok. Nakonec nahlédneme, ¾e jeho velikost je taková, jakou
lemma slibuje.

\>{\I Konstrukce~$f'$:} Pro ka¾dou dvojici hran $uv$ a $vu$ urèíme $f'(uv)$ a $f'(vu)$ následovnì:

\def\irtri{\raise0.2ex\hbox{$\triangleright$}} % Signs frequently used for \itemize

\itemize\ibull
\:Pokud $g(uv)=g(vu)=0$, polo¾íme:
        \itemize\irtri
        \:$f'(uv) := f(uv)$,
        \:$f'(vu) := f(vu)$.
        \endlist
        
\:Pokud~$g(uv)>0$ a~$g(vu)=0$, pak polo¾me:
        \itemize\irtri
        \:$\varepsilon := \min (g(uv), f(vu))$,
        \:$f'(uv) := f(uv) + g(uv) - \varepsilon$.
        \:$f'(vu) := f(vu) - \varepsilon$,
        \endlist

\:Pøípad~$g(uv)=0$ a~$g(vu)>0$ vyøe¹íme symetricky.

\:V~ostatních pøípadech je $g(uv)>0$ i $g(vu)>0$. Tehdy odeèteme od~toku~$g$ cirkulaci po cyklu $uvu$:
        \itemize\irtri
        \:$\delta := \min (g(uv),g(vu))$,
        \:$g'(uv) := g(uv) - \delta$,
        \:$g'(vu) := g(vu) - \delta$.
        \endlist
  Tím jsme velikost toku~$g$ nezmìnili a alespoò jednu z~hodnot $g(uv)$ a $g(vu)$
  jsme vynulovali, tak¾e mù¾eme pou¾ít nìkterý z~pøedchozích pøípadù.
        
\endlist

\>{\I Funkce~$f'$ je tok:}
Nejprve si v¹imneme, ¾e na¹e konstrukce nikdy nevytváøí záporná èísla, ani èísla
pøekraèující kapacity (ovìøte si v~jednotlivých pøípadech a vyu¾ijte toho, ¾e funkce~$g$
je omezena kapacitami v~síti rezerv, èili rezervami v~pùvodní síti).

Zbývá ovìøit Kirchhoffùv zákon. Doká¾eme, ¾e seètením tokù seèteme i jejich pøebytky,
tedy ¾e pro v¹echny vrcholu~$v$ je $f'^\Delta(v) = f^\Delta(v) + g^\Delta(v)$.
Pokud tedy zákon platil pro $f$ i~$g$, musí platit i pro~$f'$.

Uvedenou rovnost ovìøíme takto: Víme, ¾e k~pøebytku vrcholu~$v$ ka¾dá dvojice hran
$uv$ a $vu$ pøispívá hodnotou $\delta = f(uv) - f(vu)$. Nahlédneme, ¾e tato hodnota se zvý¹í
o~$g(uv) - g(vu)$, co¾ je pøesnì pøíspìvek uvedené dvojice hran k~pøebytku~$g^\Delta(v)$:

        \itemize\irtri
        \:V~prvním pøípadì na¹í konstrukce se $\delta$ nemìní a $g(uv) = g(vu) = 0$.
        \:V~druhém pøípadì se $\delta$ zvìt¹í o~$g(uv) - \varepsilon + \varepsilon = g(uv)$,
          pøièem¾ $g(vu)=0$.
        \:Tøetí pøípad symetricky.
        \:Ve~ètvrtém pøípadì upravíme~$g$ tak, ¾e se nezmìní $g(uv)-g(vu)$ a pokraèujeme
          nìkterým z~pøedchozích pøípadù.
        \endlist

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

\>{\I Velikost toku~$f'$:}
Pou¾ijme právì dokázaný vztah pro souèet pøebytkù:
$$\vert f' \vert = f'^\Delta(s) = f^\Delta(s) + g^\Delta(s) = \vert f \vert + \vert g \vert.$$
\qeditem

\h{Dinicùv algoritmus}

Dinicùv algoritmus bude postupnì hledat nìjaké toky~$g$ v~síti rezerv, pùvodnì nulový
tok pomocí nich zlep¹ovat, a¾ se dostane k~maximálnímu toku. Poèet potøebných iterací
pøitom bude záviset na tom, jak \uv{kvalitní} je tok~$g$ -- na jednu stranu bychom
chtìli, aby byl podobný maximálnímu toku, na druhou stranu jeho výpoètem nechceme
trávit pøíli¹ mnoho èasu. Vhodným kompromisem jsou blokující toky:

\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)$
(té budeme øíkat {\I nasycená hrana}).

\s{Definice:} Sí» je {\I vrstevnatá (proèi¹tìná)}, pokud v¹echny její vrcholy
a~hrany le¾í na~nejkrat¹ích cestách ze~$z$ do~$s$. (Abychom vyhovìli na¹í definici
sítì, musíme ke~ka¾dé takové hranì pøidat hranu opaènou s~nulovou kapacitou,
ale ty ná¹ algoritmus nebude pou¾ívat a ani udr¾ovat v~pamìti.)

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

\s{Dinicùv algoritmus:}

\algo
\:$f \leftarrow \hbox{nulový tok.}$
\:Opakujeme:
\::Sestrojíme sí» rezerv~$R$ a~sma¾eme hrany s~nulovou rezervou.
\::$\ell \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$.
\::$g \leftarrow \hbox{blokující tok v~$R$.}$
\::Zlep¹íme tok~$f$ pomocí~$g$.
\endalgo

\s{Èi¹tìní sítì} podrobnìji:

\algo
\:Rozdìlíme vrcholy do~vrstev podle vzdálenosti od~$z$.
\:Odstraníme vrstvy za~$s$ (tedy vrcholy vzdálenìj¹í ne¾~$\ell$).
\:Odstraníme hrany do~pøedchozí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 $\deg^{out}(u)$ nesní¾il na~nulu. Pokud sní¾il,
zaøadíme~$u$ na konec~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}

\s{Hledání blokujícího toku podrobnìji:}
Zaèneme s~nulovým tokem~$g$ a budeme ho postupnì zlep¹ovat. Poka¾dé najdeme nìjakou
orientovanou cestu ze~zdroje do stoku -- to se ve~vrstevnaté síti dìlá snadno,
staèí vyrazit ze~zdroje a pak následovat libovolnou hranu. A¾ cestu najdeme,
tok~$g$ podél ní zlep¹íme, jak nejvíce to pùjde.

Pokud nyní tok na nìjaké hranì dosáhl její rezervy, hranu sma¾eme. Tím jsme
mohli poru¹it proèi¹tìnost -- to pokud jsme smazali nìjakému vrcholu poslední
odchozí nebo poslední pøíchozí hranu. Takových vrcholù se opìt pomocí fronty
postupnì zbavíme a sí» doèistíme. Pokraèujeme zlep¹ením po dal¹í cestì,
dokud nìjaké cesty existují.%
\foot{V¹imnìte si, ¾e algoritmus skonèí tím, ¾e sma¾e v¹echny vrcholy i hrany.
Také si v¹imnìte, ¾e vrcholy s~nulovým vstupním stupnìm jsme ani nemuseli
mazat, proto¾e se do nich algoritmus pøi hledání cest nikdy nedostane.}

Hledání blokujícího toku tedy mù¾eme zapsat takto:

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

\h{Analýza Dinicova algoritmu}

\s{Lemma (o~korektnosti):} Pokud se~algoritmus zastaví, vydá maximální tok.

\proof
Z~lemmatu o~zlep¹ování tokù plyne, ¾e~$f$ je stále korektní tok. Algoritmus
se zastaví tehdy, kdy¾ u¾ neexistuje cesta ze~$z$ do~$s$ po hranách s~kladnou
rezervou. To je pøesnì tehdy, kdy¾ se zastaví i Fordùv-Fulkersonùv algoritmus,
a ten, jak u¾ víme, je korektní.
\qed

Nyní rozebereme èasovou slo¾itost. Rozdìlíme si k~tomu úèelu algoritmus
na {\I fáze} -- tak budeme øíkat jednotlivým prùchodùm vnìj¹ím cyklem.
Pøedpokládejme, ¾e graf neobsahuje izolované vrcholy, tak¾e $n=\O(m)$.

\s{Lemma (o~slo¾itosti fází):} Ka¾dá fáze trvá $\O(nm)$.

\proof
Sestrojení sítì rezerv, mazání hran s~nulovou rezervou, hledání nejkrat¹í cesty
i koneèné zlep¹ování toku trvají $\O(m)$.

Èi¹tìní sítì (i se v¹emi doèi¹»ováními bìhem hledání blokujícího toku) pracuje
takté¾ v~$\O(m)$: Smazání hrany trvá konstantní èas, smazání vrcholu
po smazání v¹ech incidentních hran takté¾. Ka¾dý vrchol i hrana jsou smazány
nejvý¹e jednou za~fázi.

Hledání blokujícího toku projde nejvý¹e~$m$ cest, proto¾e poka¾dé ze~sítì
vypadne alespoò jedna hrana a u¾ se tam nevrátí. Nalezení cesty metodou
\uv{rovnou za nosem} pøitom trvá $\O(n)$. Celkem tedy $\O(nm)$ plus èi¹tìní,
které jsme ale u¾ zapoèítali.

Dohromady tedy jedna fáze dobìhne v~èase $\O(m + m + nm) = \O(nm)$.
\qed

Zbývá nám jen urèit, kolik probìhne fází. K~tomu se bude hodit následující
lemma:

\s{Lemma (o~délce cest):} Délka $\ell$ nejkrat¹í cesty ze~$z$ do~$s$ vypoètená v~kroku~4
Dinicova algoritmu po ka¾dé fázi vzroste alespoò o~1.

\proof
Oznaème~$R_i$ sí» rezerv v~$i$-té fázi poté, co jsme z~ní smazali hrany
s~nulovou rezervou, ale je¹tì pøed proèi¹tìním. Nech» nejkrat¹í cesta
ze~$z$ do~$s$ v~$R_i$ je dlouhá~$\ell$.

Jak se li¹í~$R_{i+1}$ od $R_i$? Pøedev¹ím z~ka¾dé cesty délky~$\ell$
jsme smazali alespoò jednu hranu: ka¾dá taková cesta toti¾ byla blokujícím
tokem zablokována, tak¾e alespoò jedné její hranì klesla rezerva na nulu, èím¾
hrana vypadla. ®ádná z~pùvodních cest délky~$\ell$ tedy ji¾ v~$R_{i+1}$ neexistuje.

To ov¹em nestaèí -- hrany mohou také pøibývat. Pokud nìjaká hrana mìla nulovou
rezervu a bìhem fáze jsme zvý¹ili tok v~protismìru, rezerva se zvìt¹ila a hrana
se v~$R_{i+1}$ najednou objevila. Uká¾eme ale, ¾e v¹echny cesty, které tím novì
vznikly, jsou pøíli¹ dlouhé.

Rozdìlme vrcholy grafu do~vrstev podle vzdáleností od zdroje v~$R_i$. Tok jsme
zvy¹ovali pouze na hranách vedoucích o~jednu vrstvu dopøedu, tak¾e jediné
hrany, které se mohou objevit, vedou o~jednu vrstvu zpìt. Ov¹em ka¾dá cesta
ze~zdroje do~spotøebièe, která se alespoò jednou vrátí o~vrstvu zpìt, musí
mít délku alespoò $\ell+2$ (proto¾e spotøebiè je v~$\ell$-té vrstvì a neexistují
hrany, které by vedly o~více ne¾~1 vrstvu dopøedu).

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^2m)$.

\proof
Jeliko¾ ka¾dá cesta obsahuje nejvý¹e~$n$ vrcholù, z~lemmatu o~délce cest plyne,
¾e fází probìhne nejvý¹e~$n$. Jedna fáze ov¹em trvá $\O(nm)$, co¾ dává celkovou
slo¾itost $\O(n^2m)$. Speciálnì se tedy algoritmus v¾dy zastaví, tak¾e podle
lemmatu o~korektnosti vydá maximální tok.
\qed

\ss{Pár poznámek na závìr:}

Na rozdíl od~Fordova-Fulkersonova algoritmu jsme tentokrát nikde nevy¾adovali
racionálnost kapacit -- odhad èasové slo¾itosti se o~kapacity vùbec neopírá.
Nezávisle jsme tedy dokázali, ¾e i v~sítích s~iracionálními kapacitami v¾dy
existuje alespoò jeden maximální tok.

V~sítích s~malými celoèíselnými kapacitami se algoritmus chová daleko lépe,
ne¾ øíká ná¹ odhad. Uveïme bez dùkazu alespoò jeden takový výsledek: pøi hledání
nejvìt¹ího párování pøevodem na~toky, který jsme si ukázali na minulé pøedná¹ce,
by Dinicùv algoritmus dobìhl v~èase $\O(\sqrt n \cdot m)$.

\bye