3-dinic/3-dinic.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{3}{Dinicùv algoritmus}{}
   4
   5 Na~minulé pøedná¹ce jsme si~ukázali Fordùv-Fulkersonùv algoritmus. Tento
   6 algoritmus hledal maximální tok tak, ¾e zaèal s~tokem nulovým a~postupnì ho
   7 zvìt¹oval. Pro~ka¾dé zvìt¹ení potøeboval v~síti najít cestu, na~které mají
   8 v¹echny hrany kladnou rezervu (po takovéto cestì mù¾eme poslat více, ne¾ po~ní
   9 aktuálnì teèe). Ukázali jsme, ¾e pokud takováto cesta existuje, jde tok
  10 vylep¹it (zvìt¹it). Zároveò pokud tok jde vylep¹it, pak takováto cesta
  11 existuje. Dokázali jsme, ¾e pro~racionální kapacity je algoritmus koneèný
  12 a~najde maximální tok.
  13
  14 Fordùv-Fulkersonùv algoritmus má ov¹em znaèné nevýhody. Funguje pouze
  15 pro~racionální kapacity a~je pomìrnì pomalý. Nyní si~uká¾eme jiný algoritmus,
  16 který nevylep¹uje tok pomocí cest, ale pomocí tokù~\dots
  17
  18 \h{Sí» rezerv a zlep¹ující toky}
  19
  20 \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)$,
  21 kde~$r(e)$ je rezerva hrany~$e$ pøi toku~$f$.
  22
  23 Je dùle¾ité si~uvìdomit, ¾e sí» rezerv konstruujeme pro konkrétní tok v~pùvodní síti.
  24 Od pùvodní sítì se li¹í pouze tím, ¾e kapacit hran jsme nahradili jejich rezervami.
  25 Pøipomeòme je¹tì, ¾e rezervu hrany~$uv$ jsme definovali jako
  26 $$r(uv) = c(uv) - f(uv) + f(vu).$$
  27 Nyní uká¾eme, jak toky zlep¹ovat pomocí tokù v~pøíslu¹né síti rezerv:
  28
  29 \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)$
  30 lze v~èase $\O(m)$ nalézt tok~$f'$ v~síti~$S$ takový, ¾e
  31 $\vert f' \vert = \vert f \vert + \vert g \vert$.
  32
  33 \proof
  34 Nejprve uká¾eme, jak tok~$f'$ sestrojit. V~druhém kroku doká¾eme, ¾e konstrukce
  35 opravdu dává korektní tok. Nakonec nahlédneme, ¾e jeho velikost je taková, jakou
  36 lemma slibuje.
  37
  38 \>{\I Konstrukce~$f'$:} Pro ka¾dou dvojici hran $uv$ a $vu$ urèíme $f'(uv)$ a $f'(vu)$ následovnì:
  39
  40 \def\irtri{\raise0.2ex\hbox{$\triangleright$}} % Signs frequently used for \itemize
  41
  42 \itemize\ibull
  43 \:Pokud $g(uv)=g(vu)=0$, polo¾íme:
  44         \itemize\irtri
  45         \:$f'(uv) := f(uv)$,
  46         \:$f'(vu) := f(vu)$.
  47         \endlist
  48
  49 \:Pokud~$g(uv)>0$ a~$g(vu)=0$, pak polo¾me:
  50         \itemize\irtri
  51         \:$\varepsilon := \min (g(uv), f(vu))$,
  52         \:$f'(uv) := f(uv) + g(uv) - \varepsilon$.
  53         \:$f'(vu) := f(vu) - \varepsilon$,
  54         \endlist
  55
  56 \:Pøípad~$g(uv)=0$ a~$g(vu)>0$ vyøe¹íme symetricky.
  57
  58 \:V~ostatních pøípadech je $g(uv)>0$ i $g(vu)>0$. Tehdy odeèteme od~toku~$g$ cirkulaci po cyklu $uvu$:
  59         \itemize\irtri
  60         \:$\delta := \min (g(uv),g(vu))$,
  61         \:$g'(uv) := g(uv) - \delta$,
  62         \:$g'(vu) := g(vu) - \delta$.
  63         \endlist
  64   Tím jsme velikost toku~$g$ nezmìnili a alespoò jednu z~hodnot $g(uv)$ a $g(vu)$
  65   jsme vynulovali, tak¾e mù¾eme pou¾ít nìkterý z~pøedchozích pøípadù.
  66
  67 \endlist
  68
  69 \>{\I Funkce~$f'$ je tok:}
  70 Nejprve si v¹imneme, ¾e na¹e konstrukce nikdy nevytváøí záporná èísla, ani èísla
  71 pøekraèující kapacity (ovìøte si v~jednotlivých pøípadech a vyu¾ijte toho, ¾e funkce~$g$
  72 je omezena kapacitami v~síti rezerv, èili rezervami v~pùvodní síti).
  73
  74 Zbývá ovìøit Kirchhoffùv zákon. Doká¾eme, ¾e seètením tokù seèteme i jejich pøebytky,
  75 tedy ¾e pro v¹echny vrcholu~$v$ je $f'^\Delta(v) = f^\Delta(v) + g^\Delta(v)$.
  76 Pokud tedy zákon platil pro $f$ i~$g$, musí platit i pro~$f'$.
  77
  78 Uvedenou rovnost ovìøíme takto: Víme, ¾e k~pøebytku vrcholu~$v$ ka¾dá dvojice hran
  79 $uv$ a $vu$ pøispívá hodnotou $\delta = f(uv) - f(vu)$. Nahlédneme, ¾e tato hodnota se zvý¹í
  80 o~$g(uv) - g(vu)$, co¾ je pøesnì pøíspìvek uvedené dvojice hran k~pøebytku~$g^\Delta(v)$:
  81
  82         \itemize\irtri
  83         \:V~prvním pøípadì na¹í konstrukce se $\delta$ nemìní a $g(uv) = g(vu) = 0$.
  84         \:V~druhém pøípadì se $\delta$ zvìt¹í o~$g(uv) - \varepsilon + \varepsilon = g(uv)$,
  85           pøièem¾ $g(vu)=0$.
  86         \:Tøetí pøípad symetricky.
  87         \:Ve~ètvrtém pøípadì upravíme~$g$ tak, ¾e se nezmìní $g(uv)-g(vu)$ a pokraèujeme
  88           nìkterým z~pøedchozích pøípadù.
  89         \endlist
  90
  91 Tím jsme dokázali, ¾e~$f'$ je tok v~síti~$S$.
  92
  93 \>{\I Velikost toku~$f'$:}
  94 Pou¾ijme právì dokázaný vztah pro souèet pøebytkù:
  95 $$\vert f' \vert = f'^\Delta(s) = f^\Delta(s) + g^\Delta(s) = \vert f \vert + \vert g \vert.$$
  96 \qeditem
  97
  98 \h{Dinicùv algoritmus}
  99
 100 Dinicùv algoritmus bude postupnì hledat nìjaké toky~$g$ v~síti rezerv, pùvodnì nulový
 101 tok pomocí nich zlep¹ovat, a¾ se dostane k~maximálnímu toku. Poèet potøebných iterací
 102 pøitom bude záviset na tom, jak \uv{kvalitní} je tok~$g$ -- na jednu stranu bychom
 103 chtìli, aby byl podobný maximálnímu toku, na druhou stranu jeho výpoètem nechceme
 104 trávit pøíli¹ mnoho èasu. Vhodným kompromisem jsou blokující toky:
 105
 106 \s{Definice:} Tok~$f$ je {\I blokující}, jestli¾e pro~ka¾dou orientovanou
 107 cestu~$P$ ze~$z$ do~$s$ existuje hrana~$e \in P$ taková, ¾e $f(e) = c(e)$
 108 (té budeme øíkat {\I nasycená hrana}).
 109
 110 \s{Definice:} Sí» je {\I vrstevnatá (proèi¹tìná)}, pokud v¹echny její vrcholy
 111 a~hrany le¾í na~nejkrat¹ích cestách ze~$z$ do~$s$. (Abychom vyhovìli na¹í definici
 112 sítì, musíme ke~ka¾dé takové hranì pøidat hranu opaènou s~nulovou kapacitou,
 113 ale ty ná¹ algoritmus nebude pou¾ívat a ani udr¾ovat v~pamìti.)
 114
 115 \figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do~vrstev}{0.4\hsize}
 116
 117 \s{Dinicùv algoritmus:}
 118
 119 \algo
 120 \:$f \leftarrow \hbox{nulový tok.}$
 121 \:Opakujeme:
 122 \::Sestrojíme sí» rezerv~$R$ a~sma¾eme hrany s~nulovou rezervou.
 123 \::$\ell \leftarrow$ délka nejkrat¹í cesty ze~$z$ do~$s$ v~$R$.
 124 \::Pokud $l = \infty$, zastavíme se~a vrátíme~$f$.
 125 \::Proèistíme sí»~$R$.
 126 \::$g \leftarrow \hbox{blokující tok v~$R$.}$
 127 \::Zlep¹íme tok~$f$ pomocí~$g$.
 128 \endalgo
 129
 130 \s{Èi¹tìní sítì} podrobnìji:
 131
 132 \algo
 133 \:Rozdìlíme vrcholy do~vrstev podle vzdálenosti od~$z$.
 134 \:Odstraníme vrstvy za~$s$ (tedy vrcholy vzdálenìj¹í ne¾~$\ell$).
 135 \:Odstraníme hrany do~pøedchozích vrstev a hrany uvnitø vrstev.
 136 \:Odstraníme \uv{slepé ulièky}, tedy vrcholy s~$\deg^{out}(v) = 0$, a~to
 137 opakovanì pomocí fronty. (Nejdøíve zaøadíme do~fronty v¹echny vrcholy s~
 138 $\deg^{out}(v) = 0$. Pak dokud není fronta prázdná, v¾dy vybereme vrchol~$v$
 139 z~fronty, odstraníme~$v$ a~v¹echny hrany~$uv$. Pro~ka¾dý takový vrchol~$u$
 140 zkontrolujeme, zda se $\deg^{out}(u)$ nesní¾il na~nulu. Pokud sní¾il,
 141 zaøadíme~$u$ na konec~fronty.)
 142 \endalgo
 143
 144 \figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a~slepé ulièky.}{0.45\hsize}
 145
 146 \s{Hledání blokujícího toku podrobnìji:}
 147 Zaèneme s~nulovým tokem~$g$ a budeme ho postupnì zlep¹ovat. Poka¾dé najdeme nìjakou
 148 orientovanou cestu ze~zdroje do stoku -- to se ve~vrstevnaté síti dìlá snadno,
 149 staèí vyrazit ze~zdroje a pak následovat libovolnou hranu. A¾ cestu najdeme,
 150 tok~$g$ podél ní zlep¹íme, jak nejvíce to pùjde.
 151
 152 Pokud nyní tok na nìjaké hranì dosáhl její rezervy, hranu sma¾eme. Tím jsme
 153 mohli poru¹it proèi¹tìnost -- to pokud jsme smazali nìjakému vrcholu poslední
 154 odchozí nebo poslední pøíchozí hranu. Takových vrcholù se opìt pomocí fronty
 155 postupnì zbavíme a sí» doèistíme. Pokraèujeme zlep¹ením po dal¹í cestì,
 156 dokud nìjaké cesty existují.%
 157 \foot{V¹imnìte si, ¾e algoritmus skonèí tím, ¾e sma¾e v¹echny vrcholy i hrany.
 158 Také si v¹imnìte, ¾e vrcholy s~nulovým vstupním stupnìm jsme ani nemuseli
 159 mazat, proto¾e se do nich algoritmus pøi hledání cest nikdy nedostane.}
 160
 161 Hledání blokujícího toku tedy mù¾eme zapsat takto:
 162
 163 \algo
 164 \:$g \leftarrow$ nulový tok.
 165 \:Dokud v~$R$ existuje orientovaná cesta~$P$ ze~$z$ do~$s$, opakujeme:
 166 \::$\varepsilon \leftarrow \min_{e \in P} \left(r(e) - g(e)\right)$.
 167 \::Pro v¹echny $e \in P: g(e) \leftarrow g(e) + \varepsilon$.
 168 \::Pokud $g(e) = r(e)$, sma¾eme~$e$ z~$R$.
 169 \::Doèistíme sí» pomocí fronty.
 170 \endalgo
 171
 172 \h{Analýza Dinicova algoritmu}
 173
 174 \s{Lemma (o~korektnosti):} Pokud se~algoritmus zastaví, vydá maximální tok.
 175
 176 \proof
 177 Z~lemmatu o~zlep¹ování tokù plyne, ¾e~$f$ je stále korektní tok. Algoritmus
 178 se zastaví tehdy, kdy¾ u¾ neexistuje cesta ze~$z$ do~$s$ po hranách s~kladnou
 179 rezervou. To je pøesnì tehdy, kdy¾ se zastaví i Fordùv-Fulkersonùv algoritmus,
 180 a ten, jak u¾ víme, je korektní.
 181 \qed
 182
 183 Nyní rozebereme èasovou slo¾itost. Rozdìlíme si k~tomu úèelu algoritmus
 184 na {\I fáze} -- tak budeme øíkat jednotlivým prùchodùm vnìj¹ím cyklem.
 185 Pøedpokládejme, ¾e graf neobsahuje izolované vrcholy, tak¾e $n=\O(m)$.
 186
 187 \s{Lemma (o~slo¾itosti fází):} Ka¾dá fáze trvá $\O(nm)$.
 188
 189 \proof
 190 Sestrojení sítì rezerv, mazání hran s~nulovou rezervou, hledání nejkrat¹í cesty
 191 i koneèné zlep¹ování toku trvají $\O(m)$.
 192
 193 Èi¹tìní sítì (i se v¹emi doèi¹»ováními bìhem hledání blokujícího toku) pracuje
 194 takté¾ v~$\O(m)$: Smazání hrany trvá konstantní èas, smazání vrcholu
 195 po smazání v¹ech incidentních hran takté¾. Ka¾dý vrchol i hrana jsou smazány
 196 nejvý¹e jednou za~fázi.
 197
 198 Hledání blokujícího toku projde nejvý¹e~$m$ cest, proto¾e poka¾dé ze~sítì
 199 vypadne alespoò jedna hrana a u¾ se tam nevrátí. Nalezení cesty metodou
 200 \uv{rovnou za nosem} pøitom trvá $\O(n)$. Celkem tedy $\O(nm)$ plus èi¹tìní,
 201 které jsme ale u¾ zapoèítali.
 202
 203 Dohromady tedy jedna fáze dobìhne v~èase $\O(m + m + nm) = \O(nm)$.
 204 \qed
 205
 206 Zbývá nám jen urèit, kolik probìhne fází. K~tomu se bude hodit následující
 207 lemma:
 208
 209 \s{Lemma (o~délce cest):} Délka $\ell$ nejkrat¹í cesty ze~$z$ do~$s$ vypoètená v~kroku~4
 210 Dinicova algoritmu po ka¾dé fázi vzroste alespoò o~1.
 211
 212 \proof
 213 Oznaème~$R_i$ sí» rezerv v~$i$-té fázi poté, co jsme z~ní smazali hrany
 214 s~nulovou rezervou, ale je¹tì pøed proèi¹tìním. Nech» nejkrat¹í cesta
 215 ze~$z$ do~$s$ v~$R_i$ je dlouhá~$\ell$.
 216
 217 Jak se li¹í~$R_{i+1}$ od $R_i$? Pøedev¹ím z~ka¾dé cesty délky~$\ell$
 218 jsme smazali alespoò jednu hranu: ka¾dá taková cesta toti¾ byla blokujícím
 219 tokem zablokována, tak¾e alespoò jedné její hranì klesla rezerva na nulu, èím¾
 220 hrana vypadla. ®ádná z~pùvodních cest délky~$\ell$ tedy ji¾ v~$R_{i+1}$ neexistuje.
 221
 222 To ov¹em nestaèí -- hrany mohou také pøibývat. Pokud nìjaká hrana mìla nulovou
 223 rezervu a bìhem fáze jsme zvý¹ili tok v~protismìru, rezerva se zvìt¹ila a hrana
 224 se v~$R_{i+1}$ najednou objevila. Uká¾eme ale, ¾e v¹echny cesty, které tím novì
 225 vznikly, jsou pøíli¹ dlouhé.
 226
 227 Rozdìlme vrcholy grafu do~vrstev podle vzdáleností od zdroje v~$R_i$. Tok jsme
 228 zvy¹ovali pouze na hranách vedoucích o~jednu vrstvu dopøedu, tak¾e jediné
 229 hrany, které se mohou objevit, vedou o~jednu vrstvu zpìt. Ov¹em ka¾dá cesta
 230 ze~zdroje do~spotøebièe, která se alespoò jednou vrátí o~vrstvu zpìt, musí
 231 mít délku alespoò $\ell+2$ (proto¾e spotøebiè je v~$\ell$-té vrstvì a neexistují
 232 hrany, které by vedly o~více ne¾~1 vrstvu dopøedu).
 233
 234 Tím je lemma dokázáno.
 235 \qed
 236
 237 \figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.4\hsize}
 238
 239 V¹echna dokázaná tvrzení mù¾eme shrnout do~následující vìty:
 240
 241 \s{Vìta:} Dinicùv algoritmus najde maximální tok v~èase $\O(n^2m)$.
 242
 243 \proof
 244 Jeliko¾ ka¾dá cesta obsahuje nejvý¹e~$n$ vrcholù, z~lemmatu o~délce cest plyne,
 245 ¾e fází probìhne nejvý¹e~$n$. Jedna fáze ov¹em trvá $\O(nm)$, co¾ dává celkovou
 246 slo¾itost $\O(n^2m)$. Speciálnì se tedy algoritmus v¾dy zastaví, tak¾e podle
 247 lemmatu o~korektnosti vydá maximální tok.
 248 \qed
 249
 250 \ss{Pár poznámek na závìr:}
 251
 252 Na rozdíl od~Fordova-Fulkersonova algoritmu jsme tentokrát nikde nevy¾adovali
 253 racionálnost kapacit -- odhad èasové slo¾itosti se o~kapacity vùbec neopírá.
 254 Nezávisle jsme tedy dokázali, ¾e i v~sítích s~iracionálními kapacitami v¾dy
 255 existuje alespoò jeden maximální tok.
 256
 257 V~sítích s~malými celoèíselnými kapacitami se algoritmus chová daleko lépe,
 258 ne¾ øíká ná¹ odhad. Uveïme bez dùkazu alespoò jeden takový výsledek: pøi hledání
 259 nejvìt¹ího párování pøevodem na~toky, který jsme si ukázali na minulé pøedná¹ce,
 260 by Dinicùv algoritmus dobìhl v~èase $\O(\sqrt n \cdot m)$.
 261
 262 \bye