3 \prednaska{3}{Goldbergùv algoritmus}{(zapsala Markéta Popelová)}
5 Pøedstavíme si~nový algoritmus pro~hledání maximálního toku v~síti, který se~uká¾e být stejnì dobrý jako {\I Dinicùv algoritmus} ($\O(MN^{2})$) a~po~nìkolika vylep¹eních bude i~lep¹í. Nejdøíve si~pøipomeòme definice, které budeme potøebovat:
7 \s{Definice:} Mìjme sí» $S=(V,E,z,s,c)$, tok~$f$ a~libovolný vrchol~$v$. Pak $f^{\Delta}(v)$ nazýváme {\I pøebytek} ve~vrcholu~$v$ a~definujeme ho: $$f^{\Delta}(v):=\sum_{uv \in E}{f(uv)} - \sum_{vu \in E}{f(vu)}.$$ Pøebytek ve~vrcholu~$v$ je tedy souèet v¹eho, co do~vrcholu~$v$ pøiteèe, minus souèet v¹eho, co z~$v$ odteèe.
9 \s{Definice:} Mìjme sí» $S=(V,E,z,s,c)$, tok~$f$ a~libovolnou hranu~$uv$. Pak $r(uv)$ je {\I rezerva} hrany $uv$ a~je definovaná: $$r(uv) = c(uv) - f(uv) + f(vu).$$ Rezerva hrany znaèí, co je¹tì je mo¾no po~té hranì poslat.
11 \s{Poznámka:} Budeme pou¾ívat znaèení, ¾e~$N$ je poèet vrcholù a~$M$ je poèet hran, tedy~$N = \vert V \vert$ a~$M = \vert E \vert$.
13 Goldbergùv algoritmus na~rozdíl od~Dinicova algoritmu zaèíná s~nìèím, co pravdìpodobnì tok není (budeme to nazývat {\I vlna}), a~postupnì to zmen¹uje a¾ na~korektní tok.
15 \s{Definice:} Funkce $f:E \rightarrow {\bb R}_{0}^{+}$ je {\I vlna} v~síti~$(V, E, z, s, c)$ tehdy, kdy¾ jsou splnìny následující dvì podmínky:
17 \:$\forall e \in E : f(e) \leq c(e) $
18 \:$ \forall v \in V \setminus \{z, s\} : f^{\Delta}(v) \geq 0 $.
21 \s{Pozorování:} Ka¾dý tok~$f$ je vlna. Nebo» $\forall e \in E : f(e) \leq c(e) $ a~$\forall v \ne z,s: f^{\Delta}(v) = 0$.
23 \s{Operace:} {\I Pøevedení pøebytku}
25 Algoritmus bude potøebovat pøevádìt pøebytky z~vrcholu~$u$ na~sousední vrcholL~$v$. Mìjme hranu~$uv$ s~kladnou rezervou: $r(uv) > 0$ a~kladným pøebytkem ve~vrcholu~$u$: $f^\Delta(u) > 0$. Èást pøebytku budeme chtít poslat z~vrcholu~$u$ do~vrcholu~$v$. Vezmeme $\delta := \min (f^\Delta(u), r(uv))$ a~po~hranì~$uv$ po¹leme tok o velikosti~$\delta$. Výsledná situace bude vypadat následovnì:
27 \:$f'^\Delta(u) = f^\Delta(u) - \delta$.
28 \:$f'^\Delta(v) = f^\Delta(v) + \delta$.
29 \:$r'(uv) = r(uv) - \delta$.
30 \:$r'(vu) = r(vu) + \delta$.
33 Kdybychom ov¹em nepøidali ¾ádnou jinou podmínku, ná¹ algoritmus by se~mohl krásnì zacyklit (napø. posílat pøebytek z~$u$ do~$v$ a~zase zpátky). Abychom se~tomu vyhnuli, zavedeme {\I vý¹ku vrcholu} $h: V \to {\bb N}$ a~dovolíme pøevádìt pøebytek pouze z~vy¹¹ího vrcholu~$u$ na~ni¾¹í $v$: $h(u) > h(v)$.
35 \s{Shrnutí:} Podímnky pro~pøevedení pøebytku po~hranì $uv \in E$:
37 \:Ve~vrcholu~$u$ je nenulový pøebytek: $f^{\Delta}(u) > 0$.
38 \:Vrchol~$u$ je vý¹ ne¾ vrchol~$v$: $h(u) > h(v)$.
39 \:Hrana~$uv$ má nenulovou rezervu: $r(uv)>0$.
42 \s{Definice:} Øekneme, ¾e pøevedení je {\I nasycené}, pokud po~pøevodu rezerva na~hranì~$uv$ klesla na~nulu, tedy $r(uv)=0$. Naopak pøevedení je {\I nenasycené}, pokud po~pøevodu klesl pøebytek ve~vrcholu~$u$ na~nulu, tedy $f^{\Delta}(u) = 0$. Pokud $r(uv)=0$ a~$f^{\Delta}(u) = 0$, budeme pøevedení pova¾ovat za~{\I nasycené}.
44 \s{Operace:} Pro~vrchol~$u \in V$ definujme {\I zvednutí vrcholu}:
45 Pokud bìhem výpoètu narazíme ve~vrcholu~$u$ na~pøebytek, který nelze nikam pøevést, zvìt¹íme vý¹ku vrcholu~$u$ o~jednièku, tj. $h(u) \leftarrow h(u)+1$.
48 \s{Algoritmus (Goldbergùv)}
51 \:$\forall v \in V: h(v)\leftarrow 0$ (v¹em vrcholùm nastavíme poèáteèní vý¹ku nula) a~$h(z)\leftarrow N$ (zdroj zvedneme do~vý¹ky~$N$).
52 \:$\forall e \in E: f(e)\leftarrow 0$ (po~hranách nejdøíve nenecháme protékat nic) a~$\forall zu \in E : f(zu)\leftarrow c(zu)$ (ze~zdroje pustíme maximální mo¾nou vlnu).
53 \:Dokud $\exists u \in V \setminus \{z,s\}: f^{\Delta}(u)>0$:
54 \::Pokud $\exists v \in V: uv \in E,~r(uv)>0$ a~$h(u)>h(v)$, pak pøevedeme pøebytek po~hranì z~$u$ do~$v$.
55 \::V~opaèném pøípadì zvedneme $u$:~$h(u) \leftarrow h(u) + 1$.
56 \:Vrátíme tok~$f$ jako výsledek.
60 Nyní bude následovat nìkolik lemmat a~invariantù, jimi¾ doká¾eme správnost a~koneènost Goldbergova algoritmu.
62 \s{Invariant A (základ):}
64 \:Funkce~$f$ je v~ka¾dém kroku algoritmu vlna.
65 \:$h(v)$ nikdy neklesá pro~¾ádné~$v$.
66 \:$h(z)=N$ a~$h(s)=0$ po~celou dobu algoritmu.
69 \proof Indukcí dle bìhu algoritmu.
71 Na zaèátku je v¹e v~poøádku ($f$ je nulová funkce, pøebytky v¹ech vrcholù jsou nezáporné, tedy~$f$ je vlna, $h(z)=N$ a~$h(s)=0$. V~prùbìhu se~tyto hodnoty mìní pouze pøi:
73 \:Pøevedení po~hranì~$uv$: Po hranì~$uv$ se~nepo¹le více ne¾ její rezerva. Pøebytek~$u$ se~sní¾í, ale nejménì na~nulu. Pøebytek~$v$ se~zvý¹í. Tedy~$f$ zùstává vlnou. Vý¹ky se~nemìní.
74 \:Zvednutí vrcholu~$u$: Mìní pouze vý¹ky -- a~to vrcholù rùzných od zdroje èi stoku -- a~pouze je zvy¹uje.
78 \s{Invariant S (o~Spádu):} Neexistuje hrana $uv \in E: r(uv)>0$ \& $h(u) > h(v)+1$ (s~kladnou rezervou a~spádem vìt¹ím ne¾ jedna).
80 \proof Indukcí dle bìhu algoritmu.
82 Na zaèátku mají v¹echny hrany ze~zdroje rezervu nulovou a~v¹echny ostatní vedou mezi vrcholy s~vý¹kou 0. V~prùbìhu by se~tento invariant mohl pokazit pouze dvìma zpùsoby:
84 \:Zvednutím vrcholu~$u$, ze~kterého vede hrana~$uv$ s~kladnou rezervou a~spádem 1. Tento pøípad nemù¾e nastat, nebo» hranu zvedáme pouze tehdy, kdy¾ neexistuje vrchol~$v$ takový, ¾e hrana~$uv$ má kladnou rezervu a~spád alespoò 1. Takový vrchol v~na¹em pøípadì existuje, proto se~místo zvednutí vrcholu~$u$ po¹le pøebytek po~hranì~$uv$.
85 \:Zvìt¹ením rezervy hrany se~spádem vìt¹ím ne¾ 1. Toto také nemù¾e nastat, nebo» rezervu bychom mohli zvìt¹it jedinì tak, ¾e bychom poslali nìco v~protismìru -- a~to nesmíme, jeliko¾ bychom poslali pøebytek z~ni¾¹ího vrcholu na~vy¹¹í.
89 \s{Lemma K (o~Korektnosti):} Kdy¾ se~algoritmus zastaví, je~$f$ maximální tok.
91 \proof Dùkaz rozlo¾me do~dvou krokù. Nejdøíve uká¾eme, ¾e~$f$ je tok, a~pak jeho maximalitu.
94 \:Nech» se~algoritmus zastavil. Pak nemohl existovat ¾ádný vrchol~$v$ (kromì zdroje a~stoku) s~kladným pøebytkem. Tedy $\forall v \in V~\setminus \{z,s\}: f^\Delta(v) = 0$. (Víme ji¾, ¾e~$f$ je po~celou dobu vlna, tak¾e pøebytek nemù¾e být nikdy záporný.) V~tom pøípadì splòuje~$f$ podmínky toku.
95 \:Pro spor pøedpokládejme, ¾e tok~$f$ není maximální. Pak existuje zlep¹ující cesta, tedy cesta ze~zdroje do~stoku, její¾ v¹echny hrany mají kladnou rezervu. Vezmìme si~libovolnou takovou cestu. Zdroj je stále ve~vý¹ce~$N$ a~spotøebiè ve~vý¹ce 0 (viz invariant A). Tato cesta tedy pøekonává vý¹ku~$N$, ale mù¾e mít nejvý¹e~$N-1$ hran. Proto existuje alespoò jedna hrana se~spádem alespoò 2. Tato hrana tedy nemù¾e mít kladnou rezervu (viz invariant S). Tato cesta proto nemù¾e být zlep¹ující, co¾ je spor. Tím jsme dokázali, ¾e~$f$ je nutnì maximální tok.
99 \s{Definice:} Cestu~$P$ nazveme {\I nenasycenou}, pokud v¹echny její hrany mají kladnou rezervu. Neboli $\forall e \in P: r(e) > 0$.
101 \s{Lemma C (Cesta):} Mìjme vrchol $v \in V$. Pokud $f^{\Delta}(v) > 0$, pak existuje nenasycená cesta z~vrcholu~$v$ do~zdroje.
105 Mìjme nìjaký vrchol~$v \in V$ takový, ¾e $f^{\Delta}(v) > 0$. Potom definujme mno¾inu $A := \{ u \in V : \exists$ nenasycená cesta z~$v$ do~$u \}$.
107 Seètìme pøebytky ve~v¹ech vrcholech mno¾iny~$A$. Pøebytek ka¾dého vrcholu se~spoèítá jako souèet tokù do~nìj vstupujících minus souèet tokù z~nìj vystupujících. V¹echny hrany, jejich¾ oba vrcholy le¾í v~$A$, se~jednou pøiètou a~jednou odeètou. Proto nás budou zajímat pouze hrany mezi~$A$ a~$V \setminus A$.
109 $$\sum_{u \in A}f^{\Delta}(u) = \underbrace{ \sum_{ab \in E \cap ( V \setminus A \times A )} f(ab) }\limits_{=0} - \underbrace{ \sum_{ab \in E \cap ( A \times V \setminus A )} f(ab) }\limits_{\geq 0}~\leq~0.$$
111 Uka¾me si, proè $\sum_{ab \in E \cap ( V \setminus A \times A )} f(ab) = 0$. Mìjme vrcholy $a \in V \setminus A$ a~$b \in A$ takové, ¾e $ab\in E$. O~nich víme, ¾e $r(ab) = 0$ (jinak by~$a$ patøilo do~$A$) $\Rightarrow f(ab)=0$. Proto do~$A$ nic nepøitéká.
113 \figure{Goldberg01.eps}{Obrázek k dùkazu lemmatu C}{0.2\hsize}
115 Druhý èlen $\sum_{ab \in E \cap ( A \times V \setminus A )} f(ab) \geq 0$ je zøejmý, nebo» tok na~hranì je v¾dy nezáporný a~souèet nezáporných èísel je nezáporné èíslo.
117 Proto $\sum_{u \in A}{f^\Delta(u) \le 0}$. Zároveò v¹ak v~$A$ je aspoò jeden vrchol s~kladným pøebytkem, toti¾~$v$, proto v~$A$ musí být také vrchol se~záporným pøebytkem -- a~jediný takový je zdroj. Tím je dokázáno, ¾e $z \in A$, tedy ¾e vede nenasycená cesta z~vrcholu~$v$ do~zdroje.
121 \s{Invariant V (Vý¹ka):} $\forall v \in V$ platí $h(v)\leq 2N$.
124 Kdyby existoval vrchol~$v$ s~vý¹kou $h(v) > 2N$, tak by musel být nìkdy zvednut z~vý¹ky~$2N$. Tehdy musel mít kladný pøebytek $f^\Delta(v)>0$ (jinak by nemohl být zvednut). Dle lemmatu C musela existovat nenasycená cesta z~$v$ do~zdroje. Tato cesta mìla spád alespoò~$N$, ale mohla mít nejvý¹e~$N-1$ hran (jinak by to nebyla cesta v~síti na~$N$ vrcholech). Tudí¾ musela na~této cestì existovat hrana se~spádem alespoò 2, co¾ je spor s~invariantem S (nebo» v¹echny hrany této cesty mají z~definice nenasycené cesty kladné rezervy).
127 \s{Lemma Z (poèet Zvednutí):} Poèet v¹ech zvednutí je maximálnì~$2N^{2}$.
130 Staèí si~uvìdomit, ¾e ka¾dý vrchol mù¾eme zvednout maximálnì~$2N$-krát a~vrcholù je~$N$.
133 \s{Lemma S (naSycená pøevedení):} Poèet v¹ech nasycených pøevedení je nejvý¹~$NM$.
136 Pro ka¾dou hranu~$uv$ spoèítejme poèet nasycených pøevedení (tedy takových pøevedení, ¾e po~nich klesne rezerva hrany na~nulu). Abychom dvakrát nasycenì pøevedli pøebytek (nebo jeho èást) z~vrcholu~$u$ do~vrcholu~$v$, tak jsme museli~$u$ mezitím alespoò dvakrát zvednout. Ale nejvý¹e mù¾eme hranu zvednout~$2N$-krát. V¹ech hran je~$M$, proto poèet v¹ech nasycených pøevedení je nejvý¹e~$NM$.
139 \s{Lemma N (Nenasycená pøevedení):} Poèet v¹ech nenasycených pøevedení je~$\O(N^2M)$.
142 Dùkaz provedeme pomocí potenciálové metody -- nadefinujme si~následující funkci jako potenciál:
143 $$ \Phi := \sum_{\scriptstyle{v: f^{\Delta}(v) > 0} \atop \scriptstyle{v \ne z,s}} h(v). $$
144 Nyní se~podívejme, jak se~ná¹ potenciál bìhem algoritmu vyvíjí a~jaké má vlastnosti:
147 \:Na poèátku je $ \Phi = 0 $.
148 \:Bìhem celého algoritmu je $ \Phi \ge 0 $, nebo» je souètem nezáporných èlenù.
149 \:Zvednutí vrcholu zvý¹í $\Phi$ o~jednièku (Aby byl vrchol zvednut, musel mít kladný pøebytek $\Rightarrow$ vrchol do~sumy ji¾ pøispíval, teï jen pøispìje èíslem o 1 vy¹¹ím.). Ji¾ víme, ¾e za~celý prùbìh algoritmu je v¹ech zvednutí maximálnì~$2N^2$, proto zvedáním vrcholù zvý¹íme potenciál dohromady nejvý¹e o~$2N^2$.
150 \:Nasycené pøevedení zvý¹í~$\Phi$ nejvý¹e o~$2N$, proto¾e buï po~pøevodu hranou~$uv$ v~$u$ zùstal nìjaký pøebytek, tak¾e se~mohl potenciál zvý¹it nejvý¹e o~$h(v) \leq 2N$, nebo je pøebytek v~$u$ po~pøevodu nulový a~potenciál se~dokonce o~jedna sní¾il. Za~celý prùbìh tak dojde k~maximálnì~$NM$ takovýmto pøevedením, díky nim¾ se~potenciál zvý¹í maximálnì o~$2N^2M$.
151 \:Koneènì kdy¾ pøevádíme po~hranì~$uv$ nenasycenì, tak od~potenciálu urèitì odeèteme vý¹ku vrcholu~$u$ (nebo» se~vynuluje pøebytek ve~vrcholu~$u$) a~mo¾ná pøièteme vý¹ku vrcholu~$v$. Jen¾e $h(v) = h(u) - 1$, a~proto nenasycené pøevedení potenciál v¾dy sní¾í alespoò o~jedna.
154 \>Z~tohoto rozboru chování potenciálu~$\Phi$ v~prùbìhu algoritmu získáváme, ¾e poèet v¹ech nenasycených pøevedení mù¾e být nejvý¹e $2N^2 + 2N^2M$, co¾ je $\O(N^2M)$.
159 Budeme si~pamatovat seznam~$P$ v¹ech vrcholù~$v \ne z,s$ s~kladným pøebytkem. Neboli
160 $$P = \{ v \in V \setminus \{z,s\} ~\vert~ f^{\Delta}(v) > 0 \}.$$
161 Kdy¾ mìníme pøebytek nìjakého vrcholu, mù¾eme ná¹ seznam v~konstantním èase aktualizovat (napø. tak, ¾e si~ka¾dý vrchol pamatuje pozici, na~které v~seznamu~$P$ je). V~konstantním èase také umíme odpovìdìt, zda existuje nìjaký vrchol s~pøebytkem.
163 Dále si~pro ka¾dý vrchol~$u \in V$ budeme pamatovat~$L(u)$ seznam hran~$uv \in E$ takových, které vedou dolù (mají spád alespoò 1) a~kladnou rezervu. Neboli
164 $$L(u) = \{ uv \in E ~\vert~ v \in V,~ r(uv) > 0,~ h(v) < h(u)\}.$$
165 Díky tomu mù¾eme pøistupovat k~patøièným sousedùm~$u$ v~èase $\O(1)$, stejnì jako pøidávat hrany do~$L(u)$, resp. je mazat. Opìt ka¾dá hrana si~bude pamatovat pozici, na~které se~nachází v~seznamu~$L$. %TODO
167 \s{Rozbor èasové slo¾itosti algoritmu:}
170 \:Inicializace vý¹ek \dots $\O(1)$.
171 \:Inicializace vlny~$f$ \dots $\O(M)$.
172 \:Výbìr vrcholu~$u$ s~kladným pøebytkem -- vezmeme první vrchol v~$P$ \dots $\O(1)$.
173 \:Výbìr vrcholu~$v$, do~kterého vede z~$u$ hrana s~kladnou rezervou a~který je ní¾e ne¾~$u$ -- vezmeme první hranu z~$L(u)$ \dots $\O(1)$.
175 Pøevedení pøebytku: \dots $\O(1)$.
177 \:Nasycené pøevedení \dots $\O(1)$.
179 \:Rezerva hrany~$uv$ klesne na~nulu $\Rightarrow$ hrana~$uv$ vypadne z~$L(u)$ \dots $\O(1)$.
180 \:Pøebytek vrcholu~$v$ se~zvý¹í $\Rightarrow$ pokud je¹tì nebyl v~seznamu~$P$, tak se~tam pøidá \dots $\O(1)$.
181 \:Pøebytek vrcholu~$u$ mo¾ná také klesne na~nulu $\Rightarrow$ pak by vrchol~$u$ vypadnul z~$P$ \dots $\O(1)$.
183 \:Nenasycené pøevedení \dots $\O(1)$.
185 \:Rezerva hrany~$uv$ zùstane nezáporná $\Rightarrow$ hrana~$uv$ zùstane v~$L(u)$ \dots $\O(1)$.
186 \:Vynuluje se~pøebytek vrcholu~$u$~$\Rightarrow$ vrchol $u$ vypadne z~$P$ \dots~$\O(1)$.
187 \:Pøebytek vrcholu~$v$ se~zvý¹í~$\Rightarrow$ pokud je¹tì nebyl v~seznamu~$P$, tak se~tam pøidá \dots $\O(1)$.
190 \:Zvednutí vrcholu~$u$ \dots $\O(N)$.
192 Musíme obejít v¹echny hrany do~$u$ a~z~$u$, kterých je nejvý¹e~$2N-2$, porovnat vý¹ky a~pøípadnì tyto hrany~$uv$ odebrat ze~seznamu~$L(u)$ resp. pøidat do~$L(v)$. Abychom pro~odebrání hrany~$uv$ ze~seznamu~$L(u)$ nemuseli procházet celý seznam, budeme si~$\forall v \in V$ pamatovat je¹tì $L^{-1}(v) := $ seznam ukazatelù na~hrany~$uv$ v~seznamech~$L(u)$.
195 Vidíme, ¾e ka¾dé zvednutí je sice drahé, ale je jich zase pomìrnì málo. Naopak pøevádìní pøebytkù je èastá operace, tak¾e je výhodné, ¾e trvá konstantní èas.
200 \:V¹ech zvednutí je $\O(N^2)$ (viz lemma Z), ka¾dé trvá $\O(N) \dots \O(N^3).$
201 \:V¹ech nasycených pøevedení je $\O(NM)$ (viz lemma S), ka¾dé trvá $\O(1) \dots \O(NM).$
202 \:V¹ech nenasycených pøevedení je $\O(N^2M)$ (viz lemma N), ka¾dé trvá $\O(1) \dots \O(N^2M).$
205 Dohromady má tedy Goldbergùv algoritmus èasovou slo¾itost $\O(N^2M)$. Vidíme, ¾e u¾ v~tomto obecném pøípadì to není hor¹í ne¾ Dinicùv algoritmus. Pøí¹tì si~uká¾eme, ¾e mù¾e mít i~mnohem lep¹í. Nejdøíve ale zformulujme v¹echna dokázaná tvrzení do~následující vìty:
207 \s{Vìta:} Goldbergùv algoritmus najde maximální tok v~èase $\O(N^2M)$.
209 %Dokázali jsme, ¾e algoritmus má èasovou slo¾itost $\O(N^2M)$ pro~libovolnou posloupnost zvedání a~pøevádìní. Nabízí se~otázka, zda není mo¾né vhodným výbìrem tìchto operací výpoèet zrychlit. Uká¾eme, ¾e pokud v~$5.$ kroku algoritmu budeme v¾dy brát vrchol~$u$ takový, ¾e~$h(u)$ je maximální, poèet nenasycených pøevedení se~sní¾í.
211 %\s{Lemma N':} Poèet nenasycených pøevedení v~upravené verzi Goldbergova algoritmu je $\O(N^2\sqrt{M})$, co¾ je maximálnì $\O(N^3)$. Díky tomu je i~slo¾itost celého algoritmu $\O(N^3)$.
214 %Viz pøí¹tí pøedná¹ku.
projects / ads2.git / blob