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

\input lecnotes.tex

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

V~minulé kapitole jsme ukázali Fordùv-Fulkersonùv algoritmus. Tento
algoritmus hledá maximální tok tak, ¾e zaène s~tokem nulovým a~postupnì ho
zvìt¹uje. Pro~ka¾dé zvìt¹ení potøebuje v~síti najít {\I nenasycenou cestu,}
tedy takovou, na~ní¾ mají v¹echny hrany kladnou rezervu. Podél takové cesty
pak tok zlep¹í.

Ukázali jsme, ¾e tato cesta existuje právì tehdy, kdy¾ tok je¹tì není
maximální. Také jsme dokázali, ¾e pro racionální kapacity je
algoritmus koneèný a v¾dy najde maximální tok. V~obecném pøípadì to
ov¹em mù¾e trvat velice dlouho.

Nyní uká¾eme trochu slo¾itìj¹í, ale výraznì rychlej¹í Dinicùv algoritmus zalo¾ený
na my¹lence nezlep¹ovat toky pomocí cest, ale rovnou 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 kapacity hran jsme nahradili jejich rezervami.
Pøipomeòme je¹tì, ¾e rezervu hrany~$uv$ jsme definovali vztahem
$$r(uv) = c(uv) - f(uv) + f(vu).$$
Nyní uká¾eme, jak tok zlep¹it pomocí toku v~pøíslu¹né síti rezerv:

\s{Lemma Z (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
Nejdøív uká¾eme, jak tok~$f'$ sestrojit. Poté doká¾eme, ¾e konstrukce opravdu
dává korektní tok. Nakonec nahlédneme, ¾e jeho velikost je taková, jakou
lemma slibuje.

{\I Zjednodu¹ení toku~$g$:} Abychom si usnadnili práci, upravíme nejprve tok~$g$ tak,
aby pro ka¾dou dvojici hran $uv$ a~$vu$ byl tok~$g$ nenulový nejvý¹e na jedné z~nich.
Kdyby toti¾ jak $g(uv)$, tak $g(vu)$ byly kladné, mù¾eme od obou hodnot odeèíst
tu men¹í z~nich. Tím jsme nezmìnili pøebytky vrcholù, tím pádem ani velikost toku,
a~tok po jedné z~hran jsme vynulovali.

{\I Konstrukce~$f'$:} Pro ka¾dou dvojici hran $uv$ a~$vu$ takovou, ¾e $g(vu)=0$,
definujeme funkci~$f'$ následovnì:
$$\eqalign{
        \delta &:= \min(f(vu), g(uv)) \cr
        f'(vu) &:= f(vu) - \delta \cr
        f'(uv) &:= f(uv) + g(uv) - \delta \cr
}$$
(To je vlastnì toté¾ jako pøi zlep¹ování toku ve~Fordovì-Fulkersonovì algoritmu.)

{\I Proè je to tok:} Funkce~$f'$ jistì není na ¾ádné hranì záporná. Kapacity
také nepøekroèí: na hranì~$vu$ tok pouze sni¾ujeme, na hranì~$uv$ ho zvý¹íme jen
tehdy, kdy¾ $\delta < g(uv)$. Tehdy musí být $\delta = f(vu)$. Vyu¾ijeme toho, ¾e
$g$ je tok v~síti rezerv, tak¾e $g(uv) \le r(uv) = c(uv) - f(uv) + f(vu)$.
Proto $f'(uv) = f(uv) + g(uv) - \delta \le f(uv) + c(uv) - f(uv) + f(vu) - f(vu)
= c(uv)$.

Je¹tì ovìøíme, ¾e $f'$~splòuje Kirchhoffùv zákon. Uká¾eme, ¾e pro ka¾dý vrchol~$v$
platí $f'^\Delta(v) = f^\Delta(v) + g^\Delta(v)$, tak¾e pokud zákon platil pro $f$
i~$g$, musí platit i pro~$f'$. Staèí si v¹imnout, ¾e za hranu~$uv$ na¹e konstrukce
zvý¹í $f^\Delta(u)$ o~$-g(uv)$ a~$f^\Delta(v)$ o~$g(uv)$. To je pøesnì tolik, èím
tato hrana pøispívá k~$g^\Delta(u)$ a~$g^\Delta(v)$. Pro hranu~$vu$, po které
neteklo nic, platí triviálnì toté¾.

{\I Velikost toku:} Staèí vyu¾ít toho, ¾e pøebytky se seèetly, abychom získali:
$$\vert f' \vert = f'^\Delta(s) = f^\Delta(s) + g^\Delta(s) = \vert f \vert + \vert g \vert.$$

{\I Èasová slo¾itost:} Jak zjednodu¹ení toku~$g$, tak výpoèet toku~$f'$ trvají
$\O(1)$ pro ka¾dou hranu, celkovì tedy $\O(m)$.
\qed

V¹imnìte si, ¾e zlep¹ení po nenasycené cestì je speciálním pøípadem tohoto
postupu -- odpovídá toti¾ toku v~síti rezerv, který je konstantní na oné cestì
a v¹ude jinde nulový.

\h{Dinicùv algoritmus}

Dinicùv algoritmus bude postupnì hledat nìjaké pomocné toky 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í} pomocné toky se¾ene -- na jednu stranu bychom
chtìli, aby byly podobné maximálnímu toku, na druhou stranu jejich výpoètem nechceme
trávit pøíli¹ mnoho èasu. Vhodným kompromisem jsou tzv. blokující toky:

\s{Definice:} Tok je {\I blokující}, jestli¾e na~ka¾dé orientované
cestì ze~zdroje do~spotøebièe existuje alespoò jedna hrana, na ní¾ je
tok roven kapacitì.

\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 algoritmus nebude pou¾ívat a ani udr¾ovat v~pamìti.)

\s{Pozorování:} Proèi¹tìná sí» se skládá z~vrstev. V~$i$-té vrstvì le¾í ty vrcholy,
jeji¾ vzdálenost od zdroje je rovna~$i$. Z~$i$-té vrstvy vedou hrany pouze do vrstev
$0,1,\ldots,i,i+1$ -- tedy pouze uvnitø vrstvy, zpìt a o~právì jednu vrstvu dopøedu.
Proto se takové síti také øíká {\I vrstevnatá.}

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

\algo{Dinic}
\algin Sí» $(V,E,c,z,s)$.
\:$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 $\ell = \infty$, zastavíme se~a vrátíme výsledek~$f$.
\::Proèistíme sí»~$R$.
\::$g \leftarrow \hbox{blokující tok v~$R$.}$
\::Zlep¹íme tok~$f$ pomocí~$g$.
\algout Maximální tok~$f$.
\endalgo

\proc{Èi¹tìníSítì}
\:Rozdìlíme vrcholy do~vrstev podle vzdálenosti od~$z$.
\:Odstraníme vrstvy za~$s$ (tedy vrcholy ve~vzdálenosti vìt¹í ne¾~$\ell$).
\:Odstraníme hrany do~pøedchozích vrstev a hrany uvnitø vrstev.
\:Odstraníme \uv{slepé ulièky}, tedy vrcholy s~$\deg^-(v) = 0$:
\::$F \leftarrow \{ v\ne s \mid \deg^+(v) = 0 \}.$ \cmt{fronta vrcholù ke~smazání}
\::Dokud $F\ne\emptyset$, opakujeme:
\:::Odebereme vrchol~$v$ z~$F$.
\:::Sma¾eme ze sítì vrchol~$v$ i v¹echny hrany, které do nìj vedou.
\:::Pokud nìjakému vrcholu klesl $\deg^+$ na~0, pøidáme ho do~$F$.
\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{Jak nalézt blokující tok:}
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ých hranách dosáhl jejich rezervy, tyto hrany sma¾eme. Tím jsme
mohli poru¹it proèi¹tìnost -- pakli¾e nìjaký vrchol pøi¹el o~poslední odchozí nebo poslední
pøíchozí hranu. Takových vrcholù se opìt pomocí fronty zbavíme a sí» doèistíme.
Pokraèujeme zlep¹ováním po dal¹ích cestách, dokud nìjaké 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.}

Celé hledání blokujícího toku tedy vypadá následovnì:

\nobreak

\proc{BlokujícíTok}
\algin Vrstevnatá sí»~$R$ s~rezervami~$r$.
\:$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 pro kteroukoliv~$e$ nastalo $g(e) = r(e)$, sma¾eme~$e$ z~$R$.
\::Doèistíme sí» pomocí fronty.
\algout Blokující tok~$g$.
\endalgo

\h{Analýza Dinicova algoritmu}

\s{Lemma K (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. Tehdy by se zastavil 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.
Také budeme pøedpokládat, ¾e sí» na vstupu neobsahuje izolované vrcholy, tak¾e
$\O(n+m) = \O(m)$.

\s{Lemma S (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 (ta, na ní¾ se v~kroku~3 nabývalo minimum)
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.

Celá jedna fáze proto 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 C (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 jsme z~ka¾dé cesty délky~$\ell$
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}

\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~C plyne,
¾e fází probìhne nejvý¹e~$n$. Ka¾dá fáze podle lemmatu~S trvá $\O(nm)$,
co¾ dává celkovou slo¾itost $\O(n^2m)$. Speciálnì se tedy algoritmus v¾dy zastaví, tak¾e podle
lemmatu~K vydá maximální tok.
\qed

\s{Poznámka:}
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 navíc algoritmus chová daleko lépe,
ne¾ øíká ná¹ odhad. Snadno se dá dokázat, ¾e pro jednotkové kapacity dobìhne
v~èase $\O(mn)$ (stejnì jako Fordùv-Fulkersonùv). Uveïme bez dùkazu je¹tì
jeden silnìj¹í výsledek: v~síti vzniklé pøi hledání nejvìt¹ího párování
algoritmem z~minulé kapitoly Dinicùv algoritmus pracuje v~èase $\O(\sqrt n \cdot m)$.

\exercises

\ex{Doka¾te, ¾e pro jednotkové kapacity Dinicùv algoritmus dobìhne v~èase $\O(mn)$.}

\ex{Blokující tok lze také sestrojit pomocí prohledávání do~hloubky.
Poka¾dé, kdy¾ projdeme hranou, pøepoèítáme prùbì¾né minimum. Pokud najdeme
stok, vracíme se do~koøene a upravujeme tok na~hranách. Pokud narazíme na slepou ulièku,
vrátíme se o~krok zpìt a sma¾eme hranu, po~ní¾ jsme pøi¹li. Doplòte detaily.}

\endexercises

\bye