X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=4-goldberg%2F4-goldberg.tex;h=9d996b4a5c159520e765847fb100f080c7ae7301;hb=11f70ce017a9492477ec69d359fcf99598407b12;hp=8498f554090b16c36ca76c6367ead4f65747ae39;hpb=2f84c73cc47144d28896fc6d77c86971456b72f7;p=ads2.git diff --git a/4-goldberg/4-goldberg.tex b/4-goldberg/4-goldberg.tex old mode 100755 new mode 100644 index 8498f55..9d996b4 --- a/4-goldberg/4-goldberg.tex +++ b/4-goldberg/4-goldberg.tex @@ -1,152 +1,147 @@ +%version 1.8 + \input lecnotes.tex -\prednaska{4}{Goldgergùv algoritmus}{(zapsali R. Tupec, +\prednaska{4}{Goldbergùv algoritmus}{(zapsali R. Tupec, J. Volec, J. Záloha)} \noindent -Pøedstavíme si nový algoritmus pro hledání toku v síti, který se uká¾e stejnì dobrý jako -{\I Dinicùv alogritmus} ($\O(mn^{2})$), a po nìkolika vylep¹eních bude i lep¹í. - -\noindent -Tento algoritmus narozdíl od {\I Dinicova algoritmu} zaèíná s pøebytky v sousedních vrcholech zdroje a sna¾í se jich zbavit pomocí pøevedení. Abychom se pøi pøi tomto pøevádìní nezacyklili, definujeme vý¹ku vrcholu a pøevádíme pouze z kopce. +Pøedstavíme si nový algoritmus pro~hledání maximálního toku v~síti, který se uká¾e stejnì dobrý jako {\I Dinicùv algoritmus} ($\O(MN^{2})$) a po~nìkolika vylep¹eních bude i lep¹í. -\s{Definice:} Funkce $f:E \rightarrow \bb{R}_{0}^{+}$ -je {\I vlna} v síti ($V, E, z, s, c$), taková ¾e $ \forall (u,v) \in E : f(u,v) \leq c(u,v) $, kde $c(u,v)$ je kapacita hrany$(u,v)$, a $ \forall v \ne z, v \ne s : f^{\Delta}(v) \geq 0 $. +\noindent +Tento algoritmus narozdíl od~Dinicova algoritmu zaèíná s~pøebytky v~sousedních vrcholech zdroje a sna¾í se jich zbavit pomocí pøevádìní. Pokud bychom toto pøevádìní dìlali \uv{tupým zpùsobem}, mohl by se algoritmus zacyklit. Proto pro~ka¾dý vrchol budeme definovat vý¹ku, a jak uvidíme, s~její pomocí se vyhneme zacyklení. -\s{Poznámka:} Funkci $f^{\Delta}(v)$ definujeme pro libovolnou funkci $f : E \rightarrow \bb R$ -: $$f^{\Delta}(v):=\sum_{(u,v) \in E}{f(u,v)} - \sum_{(v,u) \in E}{f(v,u)}$$ -Tok je vlna, kde $ f^{\Delta}(v) = 0 , \forall v \in V , v \ne z,s $. +\s{Definice:} Funkce $f:E \rightarrow {\bb R}_{0}^{+}$ +je {\I vlna} v~síti~$(V, E, z, s, c)$ tehdy, kdy¾ $ \forall uv \in E : f(uv) \leq c(uv) $, kde $c(uv)$ je kapacita hrany~$uv$, a $ \forall v \ne z, s : f^{\Delta}(v) \geq 0 $. Funkcí $f^{\Delta}(v)$ pro libovolný vrchol~$v$ rozumíme {\I pøebytek} v~tomto vrcholu, co¾ je souèet v¹eho, co do~vrcholu~$v$ pøiteèe, minus souèet v¹eho, co z~$v$ odteèe. To mù¾eme zapsat jako: + $$f^{\Delta}(v):=\sum_{uv \in E}{f(uv)} - \sum_{vu \in E}{f(vu)}.$$ +Ka¾dý tok je vlna, kde $\forall v \ne z,s: f^{\Delta}(v) = 0$. \noindent -Algoritmus pracuje se sítí rezerv. To je funkce $r(u, v), u,v \in V$ taková, ¾e pro $\forall (u, v) \in E: r(u,v)+f(u,v)=c(u,v)$. Pokud v síti neexistují nìkteré zpìtné hrany, tak je pøidáme s nulovou kapacitou. +Algoritmus pou¾ívá sít rezerv, kterou jsme nadefinovali ji¾ v~pøedchozí kapitole vìnované Dinicovi. \noindent -V algoritmu budeme provádìt dvì operace na vrcholech sítì. K tomu budeme potøebovat pøiøadit v¹em -vrcholùm vý¹ky pomocí funkce $h : V \rightarrow \bb{N}$. +Dále budeme provádìt následující dvì operace na~vrcholech sítì. K~tomu budeme potøebovat pøiøadit v¹em vrcholùm vý¹ku pomocí funkce $h : V \rightarrow \bb{N}$. -\s{Operace:} pro $ (u,v) \in E$ - -\algo -\:{\I Pøevedení pøebytku} +\s{Operace:} Pro~hranu~$uv \in E$ definujme {\I pøevedení pøebytku}: -Pokud platí: -\itemize\ibull - \: $f^{\Delta}(u) > 0$ - \: $h(u) > h(v)$ - \: $r(u,v)>0$ +\noindent +Pokud platí, ¾e: +\numlist \ndotted + \:ve~vrcholu~$u$ je nenulový pøebytek, tj. $f^{\Delta}(u) > 0$, + \:vrchol~$u$ je vý¹ ne¾ vrchol~$v$, tj. $h(u) > h(v)$, a + \:hrana $uv$ má nenulovou rezervu, tj. $r(uv)>0$, +\endlist +\noindent pøevedeme tok o~velikosti $\delta:=\min(f^{\Delta}(u),r(uv))$ z~$u$ do~$v$ tímto zpùsobem: +\numlist \ndotted + \:$f^{\Delta}(u) \leftarrow f^{\Delta}(u)-\delta$ a $f^{\Delta}(v) \leftarrow f^{\Delta}(v)+\delta$, + \:$r(uv) \leftarrow r(uv)-\delta$ a $r(vu) \leftarrow r(vu)+\delta$. \endlist - pøevedeme tok o velikosti $\delta:=min(f^{\Delta}(u),r(u,v))$ z $u$ do $v$ takto: $f^{\Delta}(u):=f^{\Delta}(u)-\delta$, $f^{\Delta}(v):=f^{\Delta}(v)+\delta$, $r(u,v)=r(u,v)-\delta$ a $r(v,u)=r(v,u)+\delta$ . -Øekneme, ¾e pøevedení je {\I nasycené}, pokud je po pøevodu rezerva na hranì $(u,v)$ nulová, tedy $r(u,v)=0$. -Naopak pøevedení {\I nenasycené}, pokud po pøevodu $f^{\Delta}(u) = 0$. Pokud $r(u,v)=0$ a $f^{\Delta}(u) = 0$ -budeme pøevedení pova¾ovat za {\I nasycené}. +\s{Definice:} Øekneme, ¾e pøevedení je {\I nasycené}, pokud je po~pøevodu rezerva na~hranì $uv$ nulová, tedy $r(uv)=0$. +Naopak pøevedení je {\I nenasycené}, pokud po~pøevodu $f^{\Delta}(u) = 0$. Pokud $r(uv)=0$ a $f^{\Delta}(u) = 0$, +budeme pøevedení pova¾ovat za~{\I nasycené}. -\:{\I Zvednutí vrcholu} $u$ +\s{Operace:} Pro~vrchol~$u \in V$ definujme {\I zvednutí vrcholu}: +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$. -Pokud v algoritmu narazíme na pøebytek, který nelze pøevést, zvedneme vrchol $h(u):=h(u)+1$. -\endalgo - -\s{Algoritmus:} (Goldberg) +\s{Algoritmus (hledání maximálního toku v síti, Goldberg)} \algo -\:$h(*)\leftarrow 0, h(z)\leftarrow N$. -\:$f(*)\leftarrow 0, \forall u \in V, (z,u) \in E : f(z,u)\leftarrow c(z,u)$. -\:Dokud $\exists u \in V \setminus \{u,v\}, f^{\Delta}(u)>0$: -\::Pokud $\exists (u,v) \in E, r(u,v)>0$ a $h(u)>h(v)$, tak pøevedeme pøebytek po (u,v). -\::Jinak zvedneme $u$. +\:$\forall v \in V: h(v)\leftarrow 0$ (v¹em vrcholùm nastavíme poèáteèní vý¹ku nula). +\:$h(z)\leftarrow N$ (zdroj zvedneme do~vý¹ky $N$). +\:$\forall e \in E: f(e)\leftarrow 0$ (po~hranách na~poèátku nenecháme protékat nic). +\:$\forall zu \in E : f(zu)\leftarrow c(zu)$ (ze~zdroje pustíme maximální mo¾nou vlnu). +\:Dokud $\exists u \in V \setminus \{z,s\}, f^{\Delta}(u)>0$: +\::Pokud $\exists uv \in E, r(uv)>0$ a $h(u)>h(v)$: pøevedeme pøebytek po~hranì $uv$. +\::V~opaèném pøípadì zvedneme $u$. \:Vrátíme tok $f$ jako výsledek. \endalgo -%\s{Poznámka:} Pokud v síti neexistují nìkteré zpìtné hrany, tak je tam pøidáme s nulovou kapacitou - \noindent -Následovat bude nìkolik lemmat a invariantù, jimi¾ se doká¾e správnost a èasová slo¾itost vý¹e popsaného -agoritmu. +Nyní bude následovat nìkolik lemmat a invariantù, jimi¾ doká¾eme správnost a èasovou slo¾itost vý¹e popsaného algoritmu. -\s{Invariant A:} Funkce $f:E \rightarrow \bb{R}$, se kterou algoritmus pracuje, je vlna. $\forall v \in V$: $h(v)$ neklesá a $h(z)=n$, $h(s)=0$. +\s{Invariant A:} Funkce $f:E \rightarrow \bb{R}$ je v~ka¾dém kroku algoritmu vlna, $h(v)$ nikdy neklesá, $h(z)=N$ a $h(s)=0$. \proof -Pro první èást invariantu si staèí rozmyslet, ¾e v~¾ádném kroku algoritmu nepøekroèíme kapacity hran a~nevytvoøíme záporný pøebytek. $\forall v \in V \setminus \{z,s\}$ skuteènì vý¹ku pouze zvy¹ujeme a z podmínky v tøetím kroku algoritmu vyplývá, ¾e nás pøebytky v $z$ a $s$ v podstatì nezajímají, tudí¾ ani nemìníme jejich vý¹ku. +Pro~první èást invariantu si staèí rozmyslet, ¾e v~¾ádném kroku algoritmu nepøekroèíme kapacity hran a nevytvoøíme záporný pøebytek. Pro~$v \in V \setminus \{z,s\}$ skuteènì vý¹ku pouze zvy¹ujeme a z~podmínky v~pátém kroku algoritmu vyplývá, ¾e nás pøebytky v~$z$ a $s$ v~podstatì nezajímají, tudí¾ se $h(z)$ a $h(s)$ nemìní. \qed -\s{Invariant S (o spádu):} $\forall (u,v) \in E, r(u,v)>0 : h(u) \leq h(v)+1$. Tedy neexistuje hrana se spádem vìt¹ím ne¾ jedna a nenulovou rezervou. +\s{Invariant S (o~Spádu):} Neexistuje hrana se~spádem vìt¹ím ne¾ jedna a nenulovou rezervou, neboli $\forall uv \in E, r(uv)>0 : h(u) \leq h(v)+1$. -\proof -Podívejme se, kdy by mohla vzniknout nenasycená hrana se spádem vìt¹ím ne¾ 1. V druhé fázi algoritmu k tomu nedojde. Pokud ji¾ existuje vrchol $v$ s kladným pøebytkem, dále existuje nenasycená hrana $(v,u)$ a $h(v)=h(u)+1$, vrchol $v$ algoritmus nezvedá a rovnou pøebytek posílá po této hranì. Uva¾me tedy je¹tì druhý pøípad, kdy existuje nasycená hrana $(u,v)$ se spádem vìt¹ím ne¾ jedna a tuto hranu se pokusíme odsytit. Jen¾e to také nejde, proto¾e kdybychom cokoli poslali proti smìru této hrany, bude to proti smìru funkce $h$, ale to nejde. -\qed +\proof %todo pøeformulovat:BEGIN OK +Podívejme se, kdy by mohla vzniknout nenasycená hrana se~spádem vìt¹ím ne¾ jedna. Bìhem inicializace k~tomu evidentnì nedojde, proto¾e v¹echny hrany jsou nenasycené nebo mají kapacitu nula, proto je mù¾eme vypustit. Bìhem práce algoritmu k~tomu v¹ak také nedojde, jak uvidíme z~rozebrání následujících pøípadù. Pokud ji¾ existuje vrchol~$v$ s~kladným pøebytkem, dále existuje nenasycená hrana $vu$ a $h(v)=h(u)+1$, vrchol~$v$ algoritmus nezvedne, ale pøebytek po¹le po~této hranì. Uva¾me tedy je¹tì druhý pøípad, kdy existuje nasycená hrana $uv$ se~spádem vìt¹ím ne¾ jedna a tuto hranu se pokusíme odsytit. Jen¾e pokud bychom chtìli nìco poslat v protismìru, sna¾ili bychom se o pøelití proti smìru funkce $h$. +\qed %todo pøeformulovat:END -\s{Lemma K (o korektnosti):} Kdy¾ se algorimus zastaví, vydá maximální tok $f$. +\s{Lemma K (o~Korektnosti):} Kdy¾ se algoritmus zastaví, je $f$ maximální tok. \proof -Nejprve uká¾eme, ¾e $f$ je tok a pak jeho maximalitu. Vyjdìme z toho, ¾e $f$ je vlna a algorimus se mù¾e zastavit jen pokud nastanou oba tyto pøípady souèasnì: +Nejprve uká¾eme, ¾e $f$ je tok, a pak jeho maximalitu. Vyjdìme z~toho, ¾e $f$ je vlna a algoritmus se mù¾e zastavit, jen pokud nastanou oba následující pøípady souèasnì: \itemize\ibull -\:ve vrcholech grafu nejsou ¾ádné pøebytky. Potom, ale $f$ je zároveò tok. -\:pokud neexistuje nenasycená cesta $P$ ze zdroje do stoku. O té víme, ¾e má maximálnì $n-1$ hran. Zároveò by v¹ak musela mít spád $n$. Ale to znamená, ¾e existuje hrana $(u,v)$, pro kterou platí $h(u,v)>=2$, co¾ je spor s Invariantem S. +\:Ve~vrcholech grafu nejsou ¾ádné pøebytky (mimo $z$ a~$s$), proto¾e jinak by se algoritmus nezastavil a pokraèoval dále ve~výpoètu. Tudí¾ $f$ je tok. +\:Neexistuje nenasycená cesta ze~zdroje do~stoku, èím¾ z~{\I Ford-Fulkersonovy vìty} okam¾itì vyplývá, ¾e $f$ je tok maximální. A jak tuto neexistenci nahlédneme? Pro~spor pøedpokládejme, ¾e nìjaká nenasycená cesta~$P$ ze~$z$ do~$s$ existuje. Tato cesta mù¾e mít maximálnì $N-1$ hran. O~nich víme, ¾e v¹echny mají kladnou rezervu, a dále víme, ¾e po~celou dobu výpoètu je vý¹ka zdroje $N$ a vý¹ka stoku $0$. Tak¾e celkový spád cesty $P$ je $N$, co¾ ale znamená, ¾e na cestì $P$ existuje hrana s~kladnou rezervou, která má spád alespoò $2$. To je v¹ak v~rozporu s~invariantem~S. +\qeditem \endlist -\qed -\s{Invarinat C (cesta domù, do zdroje):} Je-li $v \in V(G), v \neq z,s, f^{\Delta}(v) > 0$, pak existuje nenasycená cesta z $v$ do $z$. +\s{Invariant C (Cesta domù, do~zdroje):} Je-li $v \in V \setminus \{z,s\}$ a $f^{\Delta}(v) > 0$, pak existuje nenasycená cesta z~$v$ do~$z$. \proof -Mìjme nìjaký vrchol $v \in V(G)$ takový, ¾e $f^{\Delta}(v) > 0$. -Potom definujme mno¾inu $A := \{ u \in V(G) : \exists$ nenasycená cesta z $v$ do $u \}$. -Mìjme vrcholy $a \in A$ a $b \in V(G) \setminus A$ takové, ¾e $(b,a)\in E$. O nich víme, ¾e $f(b, a)=0$, proto¾e pokud by tomu tak nebylo, muselo by platit $r(a, b)>0$, a tedy $b$ patøí do mno¾iny $A$. +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 \}$. +Mìjme vrcholy $a \in A$ a $b \in V \setminus A$ takové, ¾e $ba\in E$. O~nich víme, ¾e $f(ba)=0$, proto¾e pokud by tomu tak nebylo, muselo by platit $r(ab)>0$, a tudí¾ by $b$ patøilo do~mno¾iny $A$. -\noindent Seètìme pøebytky ve v¹ech vrcholech $A$. Proto¾e 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 a v¹echny hrany, jejich¾ oba vrcholy le¾í v $A$, se jedenkrát pøiètou a jedenkrát odeètou, platí: -$$\sum_{u \in A}f^{\Delta}(u)=\sum_{(a,b)\in E \cap (\bar{A}\times A)}f(a,b)-\sum_{(b,a)\in E \cap (A\times \bar{A})}f(b,a)$$ -Proto¾e v¹ak do $A$ nic neteèe, nebo» obsahuje zdroj (pokud není izolovaný, existují nenasycené zpìtné hrany), tento výraz musí být men¹í nebo roven nule. Odtud vyplývá, ¾e pokud nìco odtéká ven z $A$, nebo $A$ obsahuje $s$, pak $\exists u \in A, f^{\Delta}(u)<0$. Toto $u$ v¹ak musí být zdroj, proto¾e v¹echny ostatní vrcholy mají kladný pøebytek. +Seètìme pøebytky ve~v¹ech vrcholech mno¾iny $A$. Proto¾e 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 a v¹echny hrany, jejich¾ oba vrcholy le¾í v~$A$, se jednou pøiètou a jednou odeètou, platí: + $$\sum_{u \in A}f^{\Delta}(u)=\sum_{\scriptstyle{ab \in E \cap {\bb A}} \atop \scriptstyle{{\bb A} = \bar{A}\times A}} f(a,b)-\sum_{{\scriptstyle ba \in E \cap {\bb A}} \atop {\scriptstyle {\bb A} = A\times \bar{A}}} f(b,a).$$ +My v¹ak víme, ¾e do~$A$ nic neteèe, a proto $\sum_{v \in A}{f^\Delta(v) \le 0}$. Zároveò v¹ak v~$A$ je 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 $z$. \qed -\s{Invariant V (vý¹ka):} $\forall v \in V$ platí $h(v)\le 2n$. +\s{Invariant V (Vý¹ka):} $\forall v \in V$ platí $h(v)\le 2N$. \proof -Víme, ¾e poèet hran v cestì ze $z$ do $\forall v \in V$ je maximálnì $n-1$. -Pokud by existoval vrchol $v$ s vý¹kou $h(v)>2n$, musel by být zvednut alespoò $2n$-krát. To ale znamená, ¾e by po $2n-1$ zvednutích musel mít stále pøebytek. Pokud tento pøebytek nelze pøevést do ¾ádného jiného vrcholu ${u} \in E$, musí platit $h(v)\le h({u})$ a tedy $v$ bude zvednut po $2n$-té. To ale znamená, ¾e by platilo $h(v)-h(z)=n$. Dále víme z Invariantu C, ¾e existuje nenasycená cesta z $v$ do $z$. Potom ale na cestì ze $z$ do $v$ existuje hrana se spádem vìt¹ím ne¾ 1, a to je spor s Invariantem S. +Víme, ¾e poèet hran na~cestì ze~$z$ do~$\forall v \in V$ je maximálnì $N-1$. Pokud by existoval vrchol~$v$ s~vý¹kou $h(v)>2N$, museli jsme tento vrchol zvednout alespoò $(2N+1)$-krát. Snadno si uvìdomíme, ¾e $z$ nikdy nezvedáme, a tudí¾ by na cestì ze $z$ do $v$ musela být hrana se spádem vìt¹ím ne¾ jedna, co¾ je spor s~invariantem~S. \qed -\s{Lemma Z (poèet zvednutí):} Poèet v¹ech zvednutí je maximálnì $2n^{2}$. +\s{Lemma Z (poèet Zvednutí):} Poèet v¹ech zvednutí je maximálnì $2N^{2}$. \proof -Staèí si uvìdomit, ¾e ka¾dý vrchol mù¾eme zvednout maximálnì $2n$-krát a vrcholù je $n$. +Staèí si uvìdomit, ¾e ka¾dý vrchol mù¾eme zvednout maximálnì $2N$-krát a vrcholù je $N$. \qed -% -%\s{Definice:} Nasycené pøevedení je pøevedení pøebytku z vrcholu hranou takové, ¾e tato hrana bude nasycena. -% -%\s{Definice:} Nenasycené pøevedení je takové pøevedení, které není syté a pøi nìm¾ dojde k odstranìní pøebytku z vrcholu. -\s{Lemma SY (sytá pøevedení):} Poèet v¹ech sytých pøevedení je maximálnì $NM$. +\s{Lemma S (naSycená pøevedení):} Poèet v¹ech nasycených pøevedení je nejvý¹ $NM$. \proof -Mìjme hranu $(u,v) \in E$, kterou jsme právì nasytili. Tedy platí $h(v)h(u)$. Proto, abychom tuto hranu opìt nasytili, musíme opìt zmìnit nerovnost vý¹ek na $h(v)h(u)$. Proto, abychom tuto hranu opìt nasytili, musíme opìt zmìnit nerovnost vý¹ek na~$h(v) 0, v \ne z,s} h(v) $$ % !todo! dvouradkovy dolni index sumy +Dùkaz provedeme pomocí potenciálu -- nadefinujme si následující funkci jako potenciál: + $$ \psi := \sum_{\scriptstyle{v: f^{\Delta}(v) > 0} \atop \scriptstyle{v \ne z,s}} h(v). $$ Nyní se podívejme, jak se ná¹ potenciál bìhem algoritmu vyvíjí a jaké má vlastnosti: \itemize\ibull -\: Bìhem celého algoritmu je $ \psi \ge 0 $, nebo» je souètem nezáporných èlenù. -\: Na poèátku je $ \psi = 0 $. -\: Zvednutí vrcholu zvý¹í potencíál o $1$. Ji¾ víme, ¾e za~celý prùbìh algoritmu je zvednutí maximálnì $2N^2$, proto zvedáním vrcholù zvý¹íme potenciál nejvý¹e o~$2N^2$. -\: Nasycené pøevedení zvý¹í potenciál nejvý¹e o~$2N$, nebo» èistì nasyceným pøevedením mù¾eme potenciál zvý¹it a¾ o~$2N$, pokud nejde o~èistì nasycené pøevedení, potenciál se dokonce o~$1$ sní¾í. Za~celý prùbìh tak dojde k~maximálnì $NM$ takovýchto pøevedení, díky nim¾ se potenciál zvý¹í maximálnì o~$2N^2M$. -\: Koneènì kdy¾ pøevadím po~hranì $(u,v)$ nenasycenì, tak od~potenciálu urèitì odeètu vý¹ku vrcholu $u$ a mo¾ná pøiètu vý¹ku vrcholu $v$. Jen¾e $h(v) = h(u) - 1$, proto nenasycené pøevedení potenciál v¾dy sní¾í alespoò o~$1$. +\:Bìhem celého algoritmu je $ \psi \ge 0 $, nebo» je souètem nezáporných èlenù. +\:Na poèátku je $ \psi = 0 $. +\:Zvednutí vrcholu zvý¹í $\psi$ o~jednièku. 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$. +\:Nasycené pøevedení zvý¹í $\psi$ 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 a¾ o~$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$. +\:Koneènì kdy¾ pøevádíme po~hranì $uv$ nenasycenì, tak od~potenciálu urèitì odeèteme vý¹ku 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. \endlist -Rozebrali jsme tedy v¹echny události, které mohou v~prùbìhu algoritmu nastat, proto z~uvedených vlastností na¹eho potenciálu $\psi$ vidíme, ¾e poèet nenasycených pøevedení mù¾e být nejvý¹e $2N^2 + 2N^2M$, co¾ je $\O(N^2M)$. + +\>Z~tohoto rozboru chování potenciálu $\psi$ 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)$. \qed +\s{Implementace:} +Budeme si pamatovat seznam $P$ v¹ech vrcholù $v \ne z,s$ takových, ¾e $f^{\Delta}(v) > 0$. 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 je). A v~konstantním èase také umíme odpovìdìt, zda existuje nìjaký vrchol s~pøebytkem. Dále si $\forall u \in V$ budeme pamatovat $L(u) := $ seznam $uv \in E$ takových, ¾e $r(uv) > 0$ a $h(v) < h(u)$. Díky tomu mù¾eme pøistupovat k~patøièným sousedùm $u$ v~èase $\O(1)$, stejnì jako provádìt operace pøidání do~$L(u)$, resp. smazání v~nìm. Ka¾dé pøevedení po~hranì $uv$ nás stojí konstantní èas na~aktualizaci rezerv hran $uv$ a $vu$, stejnì tak i na aktualizaci pøebytkù ve~vrcholech $u$ a $v$. V~pøípadì, ¾e se jedná o~nasycené pøevedení, musíme je¹tì odstranit hranu~$uv$ z~$L(u)$, co¾ také stihneme v~èase $\O(1)$. A koneènì zvedání vrcholu~$v$ nám zabere èas $\O(N)$, proto¾e musíme obejít v¹echny hrany~$uv$, kterých je $\O(N)$, porovnat vý¹ky a pøípadnì odebrat $uv$ z~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)$. + \s{Vìta:} Goldbergùv algoritmus najde maximální tok v~èase $\O(N^2M)$. \proof -Z~lemmatu Z vyplývá, ¾e celkový poèet zvednutí je maximálnì $2N^2$, pøièem¾ ka¾dé zvednutí jsme schopni provést v~èase $\O(N)$. Tak¾e dohromady pro~zvedání spotøebujeme èas $\O(N^3)$, co¾ je pro souvislé sítì urèitì $\O(N^2M)$. Z~lemmatu SY prozmìnu vyplývá, ¾e nasycená pøevedení nás stojí $\O(NM)$, a na~závìr z~lemmatu N dostáváme èasovou slo¾itost $\O(N^2M)$ pro~pøevedení nenasycená. Proto celková slo¾itost algoritmu je $\O(N^2M)$. -\qed - -\s{Implementace:} -Budeme si pamatovat seznam $P$ v¹ech vrcholù $v \ne z,s$ takových, ¾e $f^{\Delta}(v) > 0$. Kdy¾ mìníme pøebytek nìjakeho vrcholu, tak mù¾eme ná¹ seznam v~konstantním èase zaktualizovat (napø. tak, ¾e si ka¾dý vrchol pamatuje pozici, na~které v~seznamu je). A v~konstantním èase také umíme odpovìdìt, zda existuje nìjaký vrchol s~pøebytkem. Dále si $\forall v \in V$ budeme pamatovat $L(v) := $ seznam $(v,u) \in E$ takových, ¾e $r(v,u) > 0$ a $h(u) < h(v)$. Díky tomu mù¾eme pøistupovat k~patøièným sousedùm $v$ v~èase $\O(1)$, stejnì jako provádìt operace pøidání do~$L(v)$ resp. smazání v~nìm. Pøi~pøevádìní nìjakého vrcholu $v$ vyhodíme $v$ nejvý¹e jednou, a to opìt v~èase $\O(1)$. A koneènì zvedání vrcholu nám zabere èas $\O(N)$. +Z~lemmatu~Z vyplývá, ¾e celkový poèet zvednutí je maximálnì $2N^2$, pøièem¾ ka¾dé zvednutí jsme schopni provést v~èase $\O(N)$. Tak¾e dohromady pro~zvedání spotøebujeme èas $\O(N^3)$, co¾ je pro souvislé sítì urèitì $\O(N^2M)$. Z~lemmatu~S pro~zmìnu vyplývá, ¾e nasycená pøevedení nás stojí $\O(NM)$, a na~závìr z~lemmatu~N dostáváme èasovou slo¾itost $\O(N^2M)$ pro~pøevedení nenasycená. Proto celková slo¾itost algoritmu je $\O(N^2M)$. +\qed %todo ? pro zmìnu vs. prozmenu ? -Nabízí se otázka, jak algoritmus zrychlit? Následující úprava $3.$ kroku algoritmu sní¾í poèet nenasycených pøevedení - Dokud $\exists u \in V \setminus \{u,v\}, f^{\Delta}(u)>0, h(u)$ je maximální: - co¾ je dùsledek následujícího lemmatu. +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í¾í. \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)$. - + +\proof +Viz pøí¹tí pøedná¹ku. \bye