2-dinic/2-dinic.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{2}{Dinicùv algoritmus}{(zapsala Markéta Popelová)}
   4
   5
   6 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.
   7
   8 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.
   9
  10 \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$.
  11
  12 \s{Konvence:} Pro~hranu~$e$ znaèí~$\overleftarrow{e}$ hranu opaènou. Napø. pokud $e=uv$, tak $\overleftarrow{e}=vu$.
  13
  14 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})$.
  15
  16 Ne¾ si~uká¾eme samotný algoritmus, doká¾eme si~následující lemma.
  17
  18 \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$.
  19
  20 \proof
  21
  22 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$.
  23
  24 \>{\it 1. konstrukce~$f'$}
  25
  26 \noindent
  27 Pro ka¾dou dvojici hran~$e, \overleftarrow{e}$ urèíme~$f'(e)$ a~$f'(\overleftarrow{e})$ následovnì:
  28
  29 \itemize\ibull
  30 \:Pokud~$g(e) = g(\overleftarrow{e}) = 0$, pak nastavme:
  31         \itemize\ibull
  32         \:$f'(e) := f(e)$,
  33         \:$f'(\overleftarrow{e}) := f(\overleftarrow{e})$.
  34         \endlist
  35
  36 \:Pokud~$g(e) > 0$ a~$g(\overleftarrow{e}) = 0$, pak polo¾me:
  37         \itemize\ibull
  38         \:$\varepsilon := \min (g(e), f(\overleftarrow{e}))$,
  39         \:$f'(e) := f(e) + g(e) - \varepsilon$,
  40         \:$f'(\overleftarrow{e}) := f(\overleftarrow{e}) - \varepsilon$.
  41         \endlist
  42
  43 \:Pøípad~$g(e) = 0$ a~$g(\overleftarrow{e}) > 0$ vyøe¹íme obdobnì.
  44
  45 \: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}$:
  46         \itemize\ibull
  47         \:$\delta := \min (g(e),g(\overleftarrow{e}))$,
  48         \:$g'(e) := g(e) - \delta$,
  49         \:$g'(\overleftarrow{e}) := g(\overleftarrow{e}) - \delta$.
  50         \endlist
  51
  52         A tímto jsme to pøevedli na~nìkterý z~pøedchozích pøípadù, které u¾ umíme vyøe¹it.
  53
  54 \endlist
  55
  56 \>{\it 2. $f'$ je tok}
  57
  58 \numlist{\ndotted}
  59
  60 \: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:
  61
  62         \numlist{\ndotted}
  63
  64         \: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é.
  65
  66
  67         \: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$.
  68
  69         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
  70         $$f'(e) = f(e) + g(e) - f(\overleftarrow{e}) \leq $$
  71         $$\leq f(e) + \left[ c(e) - f(e) + f(\overleftarrow{e}) \right] - f(\overleftarrow{e}) = c(e).$$
  72         Vyu¾ili jsme, ¾e~$g$ je tok v~síti rezerv, tedy $g(e) \leq  c(e) - f(e) + f(\overleftarrow{e})$.
  73
  74         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})$.
  75
  76         Tím jsme dokázali, ¾e~$f'(e)$ i~$f'(\overleftarrow{e})$ dodr¾ují kapacity.
  77
  78         \: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.
  79
  80         \endlist
  81
  82 \: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.$$
  83         % neboli $$\forall v~\in V \setminus \{z,s\}: \sum_{u: uv \in E}{f'(uv)}=\sum_{u: vu \in E}{f'(vu)}.$$
  84
  85         Vezmìme si~libovolnou hranu~$e = uv \in E$, ¾e $e=uv$. Uvìdomme si, ¾e pøi~pøechodu z~$f(e)$ na~$f'(e)$ a~z~$f(\overleftarrow{e})$ na~$f'(\overleftarrow{e})$ bylo:
  86         \itemize\idot
  87         \:$f^\Delta(u)$ sní¾eno o~$g(e)$
  88         \:$f^\Delta(v)$ zvý¹eno o~$g(e)$.
  89         \endlist
  90         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).$$
  91
  92         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$.
  93
  94 \endlist
  95
  96 Tím jsme dokázali, ¾e~$f'$ je tok v~síti~$S$.
  97
  98 \>{\it 3. $\vert f' \vert = \vert f \vert + \vert g \vert$}
  99
 100 Pou¾ijme vztah pro souèet pøebytkù z pøedchozího kroku:
 101 $$\vert f' \vert = f'^\Delta(s) = f^\Delta(s) + g^\Delta(s) = \vert f \vert + \vert g \vert.$$
 102 \qed
 103
 104
 105 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ù.
 106
 107 \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)$.
 108
 109 \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$.
 110
 111 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.
 112
 113 \figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do~vrstev}{0.4\hsize}
 114
 115 \s{Algoritmus (Dinicùv)}
 116
 117 \algo
 118 \:$f \leftarrow$ nulový tok.
 119 \:Sestrojíme sí» rezerv~$R$ a~sma¾eme $e: r(e) = 0$.
 120 \:$l \leftarrow$ délka nejkrat¹í cesty ze~$z$ do~$s$ v~$R$.
 121 \:Pokud $l = \infty$, zastavíme se~a vrátíme~$f$.
 122 \:Proèistíme sí» $R \rightarrow$ sí»~$C$.
 123 \:$g \leftarrow$ blokující tok v~$C$.
 124 \:Zlep¹íme tok~$f$ pomocí~$g$.
 125 \:GOTO 2.
 126 \endalgo
 127
 128 \s{Pozorování:} Pokud se~algoritmus zastaví, vydá maximální tok.
 129
 130 \proof
 131 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í.
 132 \qed
 133
 134 A teï je¹tì musíme ujasnit, jak budeme èistit sí» rezerv a~vybírat blokující tok~$g$.
 135
 136 \s{Algoritmus proèi¹tìní sítì rezerv}
 137
 138 \algo
 139 \:Rozdìlíme vrcholy do~vrstev podle vzdálenosti od~$z$.
 140 \:Odstraníme vrstvy za~$s$, hrany do~minulých vrstev a~hrany uvnitø vrstev.
 141 \: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.)
 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 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 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.
 147
 148 \s{Algoritmus hledání blokujícího toku}
 149
 150 \algo
 151 \:$g \leftarrow$ nulový tok.
 152 \:Dokud existuje orientovaná cesta~$P$ ze~$z$ do~$s$ v~$C$, opakuj:
 153 \::$\varepsilon \leftarrow \min_{e \in P} (r(e) - g(e))$.
 154 \::Pro~$\forall e \in P: g(e) \leftarrow g(e) + \varepsilon$.
 155 \:::Pokud $g(e) = r(e)$, sma¾eme~$e$ z~$C$.
 156 \::Doèistíme sí» zase pomocí fronty.
 157 \endalgo
 158
 159 \s{Èasová slo¾itost} Rozeberme si~jednotlivé kroky algoritmu.
 160
 161 \numlist{\ndotted}
 162 \:Inicializace toku~$f$ \dots $\O(1)$.
 163 \:Sestrojení sítì rezerv a~smazání hran s~nulovou rezervou \dots $\O(m + n)$.
 164 \:Najití nejkrat¹í cesty (prohledáváním do~¹íøky) \dots $\O(m + n)$.
 165 \:Zkontrolování délky nejkrat¹í cesty \dots $\O(1)$.
 166 \:Proèi¹tìní sítì \dots $\O(m + n)$.
 167         \numlist{\ndotted}
 168         \:Rozdìlení vrcholù do~vrstev -- provedlo ji¾ prohledávání do~¹íøky \dots $\O(1)$.
 169         \:Odstranìní nìkterých hran \dots $\O(m + n)$.
 170         \: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)$.
 171         \endlist
 172 \:Najití blokujícího toku~$g$ \dots $\O(m \cdot n)$.
 173         \numlist{\ndotted}
 174         \:Inicializace toku~$g$ \dots $\O(1)$.
 175         \: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)$.
 176         \: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)$.
 177         \:Pøepoèítání v¹ech hran cesty \dots $\O(n)$.
 178         \:Smazání hran cesty, jejich¾ tok~$g(e)$ se~zvý¹il na~hodnotu~$r(e)$ \dots $\O(n)$.
 179         \:Doèi¹»ování vyøe¹me zvlá¹».
 180         \endlist
 181
 182         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$).
 183
 184         È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.
 185
 186         Najití blokujícího toku bude tedy trvat $\O(m \cdot n + (m + n)) = \O(m \cdot n)$.
 187
 188 \:Zlep¹ení toku~$f$ pomocí toku~$g$ \dots $\O(m)$.
 189 \:Skok na~2. krok \dots $\O(1)$.
 190 \endlist
 191
 192 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 vnjì¹í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$.
 193
 194 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)$.
 195
 196 \s{Lemma:} Hodnota~$l$ vzroste mezi fázemi alespoò o~1.
 197
 198 \proof
 199
 200 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
 201 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.
 202
 203 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..
 204
 205 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á.
 206
 207 Tím je lemma dokázáno.
 208 \qed
 209
 210 \figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.4\hsize}
 211
 212 V¹echna dokázaná tvrzení mù¾eme shrnout do~následující vìty:
 213
 214 \s{Vìta:} Dinicùv algoritmus najde maximální tok v~èase $\O(n^2\cdot m)$.
 215
 216 \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.
 217
 218 \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.
 219
 220
 221 %k,s,v,na,do,ke,pro,pøi,a,u,i,po,
 222
 223 \bye