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