X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=4-goldberg%2F4-goldberg.tex;h=c7cffd2f2677fe835dc84e5e451b648561509ab5;hb=db09518ff28f6b7857abec8cab109d8a91aff178;hp=56f39ca79669a48a87d7952d36f29539018b57ff;hpb=be3502110aea505a6f8aa610374f58670c325524;p=ads2.git diff --git a/4-goldberg/4-goldberg.tex b/4-goldberg/4-goldberg.tex index 56f39ca..c7cffd2 100644 --- a/4-goldberg/4-goldberg.tex +++ b/4-goldberg/4-goldberg.tex @@ -1,147 +1,419 @@ -%version 1.8 - \input lecnotes.tex -\prednaska{4}{Goldbergùv algoritmus}{(zapsali R. Tupec, -J. Volec, -J. Záloha)} +\prednaska{4}{Goldbergùv algoritmus}{} -\noindent -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¹í. +Pøedstavíme si je¹tì jeden algoritmus pro~hledání maximálního toku v~síti. +Bude daleko jednodu¹¹í ne¾ Dinicùv algoritmus z~pøedchozí kapitoly +a po pár snadných úpravách bude mít stejnou nebo dokonce lep¹í èasovou +slo¾itost. Jednoduchost algoritmu bude ale vykoupena trochu slo¾itìj¹ím +rozborem jeho správnosti a efektivity. -\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í. +\h{Vlny a pøebytky} -\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)$ rozumíme {\I pøebytek}, který pøebývá ve~vrcholu~$v$, co¾ je souèet v¹eho, co do~vrcholu~$v$ pøiteèe, mínus 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$. +\s{Znaèení} z~minulých kapitol, které se nám bude hodit: -\noindent -Algoritmus pou¾ívá sít rezerv, kterou jsme nadefinovali ji¾ v~pøedchozí kapitole vìnované Dinicovi. +\itemize\ibull +\:{\I sí»} $S=(V,E,z,s,c)$: $V$ je mno¾ina vrcholù, $E$ mno¾ina hran, +$z$~{\I zdroj,} $s$~{\I spotøebiè} a $c$~funkce udávající {\I kapacity} hran. +\:$n$ udává poèet vrcholù grafu, $m$~poèet jeho hran. +\:$f^\Delta(v)$ je {\I pøebytek} vrcholu~$v$ pøi ohodnocení hran funkcí~$f$, +tedy souèet hodnot~$f$ na hranách vedoucích do~$v$ minus souèet na hranách +vedoucích z~$v$ ven. +\:$r(uv) = c(uv) - f(uv) + f(vu)$ je {\I rezerva} hrany~$uv$; ta øíká, kolik +jednotek toku mù¾eme po této hranì je¹tì poslat, a~to buï pøiètením po smìru +hrany nebo odeètením proti smìru. Hranám s~kladnou rezervou øíkáme {\I nenasycené,} +stejnì øíkáme cestám slo¾eným ze~samých takových hran. +\endlist -\noindent -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}$. +Pøedchozí algoritmy zaèínaly s~nulovým tokem a postupnì ho zlep¹ovaly, +a¾ se stal maximálním. Goldbergùv algoritmus naproti tomu zaène s~ohodnocením +hran, které ani nemusí být tokem, a~postupnì ho upravuje a zmen¹uje, a¾ se +z~nìj stane tok, a~to dokonce maximální. -\s{Operace:} Pro~hranu~$uv \in E$ definujme {\I pøevedení pøebytku}: +\s{Definice:} Funkce $f:E \rightarrow {\bb R}_0^+$ je {\I vlna} v~síti~$S$, +splòuje-li obì následující podmínky: -\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$, +\itemize\ibull +\:$\forall e \in E : f(e) \leq c(e)$ (vlna nepøekroèí kapacity hran), +\:$\forall v \in V \setminus \{z, s\} : f^\Delta(v) \geq 0$ (pøebytek ve~vrcholech je nezáporný). \endlist -\noindent pøevedeme tok o~velikosti $\delta:=\min(f^{\Delta}(u),r(uv))$ z~$u$ do~$v$ tímto zpùsobem: + +Ka¾dý tok je tedy vlnou, ale opaènì tomu tak být nemusí -- potøebujeme se +postupnì zbavit nenulových pøebytkù ve~v¹ech vrcholech kromì zdroje a spotøebièe. +K~tomu nám bude slou¾it následující operace: + +\s{Definice:} {\I Pøevedení pøebytku} po hranì~$uv$, pøièem¾ $f^\Delta(u)>0$ a $r(uv)>0$, +provedeme tak, ¾e po hranì~$uv$ po¹leme $\delta = \min(f^\Delta(u), r(uv))$ jednotek toku, +podobnì jako v~pøedchozích algoritmech buï pøiètením po smìru nebo odeètením proti smìru. + +\s{Pozorování:} Pøevedení zmìní pøebytky a rezervy následovnì: + +$$\eqalign{ +f'^\Delta(u) &= f^\Delta(u) - \delta \cr +f'^\Delta(v) &= f^\Delta(v) + \delta \cr +r'(uv) &= r(uv) - \delta \cr +r'(vu) &= r(vu) + \delta \cr +}$$ + +Rádi bychom postupným pøevádìním v¹echny pøebytky buï pøepravili do spotøebièe +nebo, pokud je vlna pøíli¹ velká, je pøelili zpìt do zdroje. Chceme se ov¹em vyhnout +pøelévání pøebytkù tam a zase zpìt, tak¾e vrcholùm pøiøadíme {\I vý¹ky} -- to budou +nìjaká pøirozená èísla $h(v)$. + +Pøebytek pak budeme ochotni pøevádìt pouze z~vy¹¹ího vrcholu do~ni¾¹ího. Pokud se +stane, ¾e nalezneme vrchol s~pøebytkem, ze kterého nevede ¾ádná nenasycená hrana +smìrem dolù, budeme tento vrchol {\I zvedat} -- tedy zvy¹ovat mu vý¹ku po jedné, +ne¾ se dostane dostateènì vysoko, aby z~nìj pøebytek mohl odtéci. + +Získáme tak následující algoritmus: + +\algo{Goldberg} +\algin Sí». +\:Nastavíme poèáteèní vý¹ky: \cmt{zdroj ve~vý¹ce~$n$, ostatní ve~vý¹ce~0} +\::$h(z)\leftarrow n$ +\::$h(v)\leftarrow 0$ pro v¹echny $v\ne z$ +\:Vytvoøíme poèáteèní vlnu: \cmt{v¹echny hrany ze~$z$ na maximum, jinde~0} +\::$f\leftarrow \hbox{v¹ude nulová funkce}$ +\::$f(zv)\leftarrow c(zv)$, kdykoliv $zv\in E$ +\:Dokud $\exists u \in V \setminus \{z,s\}: f^{\Delta}(u)>0$: +\::Pokud $\exists v \in V: uv \in E,~r(uv)>0$ a~$h(u)>h(v)$, \hfil\break {\I pøevedeme pøebytek} po~hranì~$uv$. +\::V~opaèném pøípadì {\I zvedneme} $u$:~$h(u) \leftarrow h(u) + 1$. +\algout Maximální tok~$f$. +\endalgo + +\h{Analýza algoritmu} + +Algoritmus je jednoduchý, ale na první pohled není vidìt ani to, ¾e se v¾dy +zastaví, nato¾ ¾e by mìl vydat maximální tok. Postupnì o~nìm doká¾eme nìkolik +invariantù a lemmat a pomocí nich se dobereme k~dùkazu správnosti a èasové slo¾itosti. + +\s{Invariant A (základní):} \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$. +\:Funkce~$f$ je v~ka¾dém kroku algoritmu vlna. +\:Vý¹ka $h(v)$ ¾ádného vrcholu~$v$ nikdy neklesá. +\:$h(z)=n$ a~$h(s)=0$ po~celou dobu bìhu algoritmu. \endlist -\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é}. +\proof Indukcí dle poètu prùchodù cyklem (7. -- 9. krok algoritmu): + +\itemize\ibull +\:Po inicializaci algoritmu je v¹e v~poøádku: pøebytky v¹ech vrcholù mimo zdroj +jsou nezáporné, vý¹ky souhlasí. +\:Pøi pøevedení pøebytku: Z~definice pøevedení pøímo plyne, ¾e neporu¹uje +kapacity a nevytváøí záporné pøebytky. Vý¹ky se nemìní. +\:Pøi zvednutí vrcholu: Tehdy se naopak mìní jen vý¹ky, ale pouze u~vrcholù rùzných +od~zdroje a stoku. Vý¹ky navíc pouze rostou. +\qeditem +\endlist -\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$. +\s{Invariant S (o~Spádu):} Neexistuje hrana~$uv$, která by mìla kladnou rezervu +a spád $h(u) - h(v)$ vìt¹í ne¾~1. -\s{Algoritmus (hledání maximálního toku v síti, Goldberg)} +\proof Indukcí dle bìhu algoritmu. +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 výpoètu by se~tento invariant mohl pokazit pouze +dvìma zpùsoby: -\algo -\:$\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 +\itemize\ibull +\:Zvednutím vrcholu~$u$, ze~kterého vede hrana~$uv$ s~kladnou rezervou +a~spádem 1. Tento pøípad nemù¾e nastat, nebo» algoritmus by dal pøednost +pøevedení pøebytku po~této hranì pøed zvednutím. +\: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 pøevádìli +pøebytek z~ni¾¹ího vrcholu do~vy¹¹ího. +\qeditem +\endlist -\noindent -Nyní bude následovat nìkolik lemmat a invariantù, jimi¾ doká¾eme správnost a èasovou slo¾itost vý¹e popsaného algoritmu. +\s{Lemma K (o~Korektnosti):} Kdy¾ se~algoritmus zastaví, je~$f$ maximální tok. -\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 +Nejprve uká¾eme, ¾e {\I $f$ je tok:} Omezení na kapacity splòuje tok stejnì +jako vlna, tak¾e postaèí dokázat, ¾e platí Kirchhoffùv zákon. Ten po¾aduje, +aby pøebytky ve~v¹ech vrcholech kromì zdroje a spotøebièe byly nulové. To ov¹em +musí být, proto¾e nenulový pøebytek by musel být kladný a algoritmus by se dosud +nezastavil. + +Zbývá zdùvodnit, ¾e {\I $f$ je maximální:} Pro spor pøedpokládejme, ¾e tomu tak není. +Ze~správnosti Fordova-Fulkersonova algoritmu plyne, ¾e tehdy musí existovat nenasycená +cesta ze~zdroje do~stoku. Uva¾me 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á spád~$n$, +ale mù¾e mít nejvý¹e~$n-1$ hran. Proto se v~ní nachází alespoò jedna hrana se~spádem +alespoò~2. Jeliko¾ je tato hrana souèástí nenasycené cesty, musí být sama nenasycená, +co¾ je spor s~invariantem~S. Tok je tedy maximální. +\qed + +\s{Lemma C (Cesta do zdroje):} Mìjme vrchol~$v$, jeho¾ pøebytek $f^{\Delta}(v)$ je kladný. +Pak existuje nenasycená cesta z~tohoto vrcholu do~zdroje. \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. 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í. +Buï~$v$ vrchol s~kladným pøebytkem. +Uva¾me mno¾inu $A := \{ u \in V \mid \hbox{existuje nenasycená cesta z~$v$ do~$u$} \}$. +Uká¾eme, ¾e tato mno¾ína obsahuje zdroj. + +Pou¾ijeme u¾ mírnì okoukaný trik: seèteme pøebytky ve~v¹ech vrcholech mno¾iny~$A$. +V¹echny hrany le¾ící celé uvnitø~$A$ nebo celé venku pøispìjí dohromady nulou. +Nenulou mohou pøispìt pouze hrany vedoucí ven z~$A$ nebo naopak zvenku dovnitø. +Získáme: +$$ + \sum_{u \in A}f^{\Delta}(u) = + \underbrace{ \sum_{ba \in E(V\setminus A,A)} f(ba) }\limits_{=0} - + \underbrace{ \sum_{ab \in E(A,V\setminus A)} f(ab) }\limits_{\geq 0} + \leq~0. +$$ + +Uka¾me si, proè je první svorka rovna nule. Mìjme hranu~$ab$ ($a\in A$, $b \in V \setminus A$). +Ta musí mít nulovou rezervu -- jinak by toti¾ i vrchol~$b$ patøil do~$A$. +Proto po hranì $ba$ nemù¾e nic téci. + +\figure{Goldberg01.eps}{Obrázek k dùkazu lemmatu C}{0.2\hsize} + +Druhá svorka je evidentnì nezáporná, proto¾e je to souèet nezáporných ohodnocení hran. + +Proto $\sum_{u \in A}{f^\Delta(u) \le 0}$. Zároveò v¹ak v~$A$ le¾í aspoò jeden +vrchol s~kladným pøebytkem, toti¾~$v$, tudí¾ v~$A$ musí být také nìjaký vrchol +se~záporným pøebytkem -- a~jediný takový je zdroj. Tím je dokázáno, ¾e $z$ le¾í v~$A$, +tedy ¾e vede nenasycená cesta z~vrcholu~$v$ do~zdroje. \qed -\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$. +\s{Invariant V (Vý¹ka):} Pro ka¾dý vrchol~$v$ je $h(v)\leq 2n$. -\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 +\proof +Kdyby existoval vrchol~$v$ s~vý¹kou $h(v) > 2n$, mohl se do této vý¹ky +dostat pouze zvednutím z~vý¹ky alespoò~$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 nicménì pøekonávala spád alespoò~$n$, ale mohla mít nejvý¹e~\hbox{$n-1$} hran (na cestách +se vrcholy neopakují). Tudí¾ musela obsahovat nenasycenou hranu se~spádem alespoò~2, co¾ je +spor s~invariantem~S. +\qed -\s{Lemma K (o~Korektnosti):} Kdy¾ se algoritmus zastaví, je $f$ maximální tok. +\s{Lemma Z (poèet Zvednutí):} Bìhem výpoètu nastane nejvý¹e $2n^{2}$ zvednutí. \proof -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 (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 +Z~pøedchozího invariantu plyne, ¾e ka¾dý vrchol mohl být zvednut nejvý¹e $2n$-krát. +Vrcholù je~$n$. +\qed -\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$. +Teï nám je¹tì zbývá urèit poèet provedených pøevedení. Bude se~nám hodit, kdy¾ pøevedení rozdìlíme na~dva druhy: -\proof -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$. +\s{Definice:} Øekneme, ¾e pøevedení po hranì~$uv$ je {\I nasycené}, pokud po~pøevodu +rezerva $r(uv)$ klesla na~nulu. V~opaèném pøípadì je {\I nenasycené}, a~tehdy urèitì +klesne pøebytek $f^\Delta(u)$ na~nulu (to se nicménì mù¾e stát i pøi nasyceném pøevedení). -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$. +\s{Lemma S (naSycená pøevedení):} Poèet v¹ech nasycených pøevedení je nejvý¹~$nm$. + +\proof +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: + +Po~prvním nasyceném pøevedení z~vrcholu~$u$ do~vrcholu~$v$ se~vynulovala +rezerva hrany~$uv$. Uvìdomme si, ¾e pøi~této operaci muselo být~$u$ vý¹e +ne¾~$v$, a~dokonce víme, ¾e bylo vý¹e pøesnì o~1 (viz invariant~S). Ne¾ nastane +dal¹í pøevedení po~této hranì, musíme její rezervu z~nuly opìt zvý¹it. +Jediný zpùsob, jak toho lze dosáhnout, je pøevést èást pøebytku z~$v$ zpátky do~$u$. +K~tomu se~musí~$v$ dostat (alespoò o~1) vý¹e ne¾~$u$. Po~pøelití bude rezerva~$uv$ +opìt kladná. A~abychom provedli nasycené pøevedení znovu ve~smìru z~$u$ do~$v$, +musíme zase~$u$ dostat (alespoò o~1) vý¹e ne¾~$v$. Proto musíme~$u$ alespoò o~2 +zvednout -- nejprve na~úroveò~$v$ a~pak je¹tì o~1 vý¹e. + +Ukázali jsme tedy, ¾e mezi ka¾dými dvìma nasycenými pøevedeními musel být vrchol~$u$ +zvednut alespoò dvakrát. Podle lemmatu~V se~$u$ mohlo zvedat maximálnì $2n$-krát za celý +výpoèet, tak¾e v¹ech nasycených pøevedení po~hranì~$uv$ je nejvý¹e~$n$ a po~v¹ech hranách +dohromady nejvý¹e~$nm$. \qed -\s{Invariant V (Vý¹ka):} $\forall v \in V$ platí $h(v)\le 2N$. + +\s{Lemma N (Nenasycená pøevedení):} Poèet v¹ech nenasycených pøevedení je~$\O(n^2m)$. \proof -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. +Dùkaz provedeme potenciálovou metodou. Uva¾ujme následující potenciál: +$$ \Phi := \sum_{\scriptstyle{v \ne z,s} \atop \scriptstyle{f^{\Delta}(v) > 0}} h(v). $$ +Nyní se~podívejme, jak se~ná¹ potenciál bìhem algoritmu vyvíjí: + + \itemize\ibull + \:Na poèátku je $ \Phi = 0 $. + \:Bìhem celého algoritmu je $ \Phi \ge 0 $, nebo» potenciál je souètem nezáporných èlenù. + \:Zvednutí vrcholu zvý¹í $\Phi$ o~jednièku. (Aby byl vrchol zvednut, musel mít kladný + pøebytek, tak¾e 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$. + \: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. + Podle lemmatu~S nastane nejvý¹e~$nm$ takových nasycených pøevedení a ta celkovì + 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$ (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. + \endlist + +\>Potenciál celkovì stoupne o~nejvy¹e $2n^2 + 2n^2m = \O(n^2m)$, klesá pouze pøi nenasycených +pøevedeních a poka¾dé alespoò o~1. Proto je v¹ech nenasycených pøevedení $\O(n^2m)$. \qed -\s{Lemma Z (poèet Zvednutí):} Poèet v¹ech zvednutí je maximálnì $2N^{2}$. +\h{Implementace} + +Zbývá vyøe¹it, jak sí» a vý¹ky reprezentovat, abychom dokázali rychle hledat +vrcholy s~pøebytkem a nenasycené hrany vedoucí s~kopce. + +Budeme si~pamatovat seznam~$P$ v¹ech vrcholù s~kladným pøebytkem. +Kdy¾ mìníme pøebytek nìjakého vrcholu, mù¾eme tento seznam v~konstantním èase +aktualizovat -- buïto vrchol do seznamu pøidat nebo ho naopak odebrat. (K~tomu se +hodí, aby si vrcholy pamatovaly ukazatel na svou polohu v~seznamu~$P$). +V~konstantním èase také umíme odpovìdìt, zda existuje nìjaký vrchol s~pøebytkem. + +Dále si pro ka¾dý vrchol $u \in V$ budeme udr¾ovat seznam~$L(u)$. Ten bude +obsahovat v¹echny nenasycené hrany, které vedou z~$u$ dolù (mají spád alespoò 1). +Opìt pøi zmìnách rezerv mù¾eme tyto seznamy v~konstantním èase upravit. + +Jednotlivé operace budou mít tyto slo¾itosti: + +\itemize\ibull +\:{\I Inicializace} algoritmu -- trivialnì $\O(m)$. +\:{\I Výbìr vrcholu} s~kladným pøebytkem a nalezení nenasycené hrany vedoucí dolù -- $\O(1)$ + (staèí se podívat na poèátky pøíslu¹ných seznamù). +\:{\I Pøevedení pøebytku} po~hranì~$uv$ -- zmìny rezerv $r(uv)$ a $r(vu)$ zpùsobí pøepoèítání + seznamù~$L(u)$ a~$L(v)$, zmìny pøebytkù $f^\Delta(u)$ a~$f^\Delta(v)$ mohou zpùsobit + zmìnu v~seznamu~$P$. V¹e v~èase $\O(1)$. +\:{\I Zvednutí vrcholu~$u$} -- musíme obejít v¹echny hrany do~$u$ a~z~$u$, kterých je nejvý¹e~$2n$, + porovnat vý¹ky a~pøípadnì tyto hrany~$uv$ odebrat ze~seznamu~$L(v)$ resp. pøidat + do~$L(u)$. To trvá $\O(n)$. +\endlist + +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. + +\s{Vìta:} Goldbergùv algoritmus najde maximální tok v~èase $\O(n^2m)$. \proof -Staèí si uvìdomit, ¾e ka¾dý vrchol mù¾eme zvednout maximálnì $2N$-krát a vrcholù je $N$. +Inicializace algoritmu trvá $\O(m)$. Pak algoritmus provede nejvý¹e~$2n^2$ zvednutí +(viz lemma~Z), nejvý¹e $nm$ nasycených pøevedení (lemma~N) a nejvý¹e $n^2m$ nenasycených +pøevedení. Vynásobením slo¾itostmi jednotlivých operací dostaneme èas $\O(n^3 + nm + n^2m) = \O(n^2m)$. +Podle lemmatu~K po~zastavení vydá maximální tok. \qed -\s{Lemma S (naSycená pøevedení):} Poèet v¹ech nasycených pøevedení je nejvý¹ $NM$. +\h{Vylep¹ení Goldbergova algoritmu} + +Základní verze Goldbervova algoritmu tedy dosáhla stejné slo¾itosti jako Dinicùv algoritmus. +Nyní uká¾eme, ¾e pokud budeme volit vrchol, ze~kterého budeme pøevádìt pøebytek, ¹ikovnìji +-- toti¾ jako nejvy¹¹í z~vrcholù s~nenulovým pøebytkem~--, slo¾itost se je¹tì zlep¹í. + +V~èasové slo¾itosti pùvodního algoritmu byl nejvýznamnìj¹í èlen $\O(n^2m)$ za~nenasycená +pøevedení. Pokusme se jejich poèet ve~vylep¹eném algoritmu odhadnout tìsnìji. + +\s{Lemma N' (Nenasycená pøevedení):} Goldbergùv algoritmus s~volbou nejvy¹¹ího vrcholu +provede $\O(n^3)$ nenasycených pøevedení. \proof -Mìjme hranu~$uv \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) 0\}.$$ +Rozdìlíme bìh algoritmu na~{\I fáze}. Ka¾dá fáze konèí tím, ¾e~se~$H$ zmìní. +Jak se~mù¾e zmìnit? Buï se~$H$ zvý¹í, co¾ znamená, ¾e~nìjaký vrchol s~pøebytkem +v~nejvy¹¹í hladinì byl o~1 zvednut, nebo se~$H$ sní¾í. U¾ víme, ¾e v~prùbìhu +výpoètu nastane $\O(n^2)$ zvednutí, co¾ shora omezuje poèet zvý¹ení~$H$. +Zároveò si~mù¾eme uvìdomit, ¾e~$H$ je nezáporný potenciál a sni¾uje se i zvy¹uje +pøesnì o~1. Poèet sní¾ení bude proto omezen poètem zvý¹ení. Tím pádem nastane +v¹eho v¹udy $\O(n^2)$ fází. + +Bìhem jedné fáze pøitom provedeme nejvý¹e jedno nenasycené pøevedení +z~ka¾dého vrcholu. Po~ka¾dém nenasyceném pøevedení po~hranì $uv$ se~toti¾ +vynuluje pøebytek v~$u$ a~aby se~provedlo dal¹í nenasycené pøevedení +z~vrcholu~$u$, muselo by nejdøíve být co~pøevádìt. Muselo by tedy do~$u$ nìco +pøitéci. My ale víme, ¾e pøevádíme pouze shora dolù a~$u$ je v~nejvy¹¹í hladinì +(to zajistí právì ono vylep¹ení algoritmu), tedy nejdøíve by musel být nìjaký +jiný vrchol zvednut. Tím by se~ale zmìnilo~$H$ a~skonèila by tato fáze. + +Proto poèet v¹ech nenasycených pøevedení bìhem jedné fáze je nejvý¹e~$n$. A ji¾ jsme dokázali, ¾e~fází je~$\O(n^2)$. Tedy poèet v¹ech nenasycených pøevedení je~$\O(n^3)$. \qed -\s{Lemma N (Nenasycená pøevedení):} Poèet v¹ech nenasycených pøevedení je $\O(N^2M)$. +Tento odhad je hezký, ale stále není tìsný a~algoritmus se~chová lépe. Doka¾me si~je¹tì jeden tìsnìj¹í odhad na~poèet nenasycených pøevedení. + +\s{Lemma N'' (Nenasycená pøevedení):} Poèet nenasycených pøevedení je~$\O(n^2 \sqrt{m})$. + +\s{Poznámka:} Tato èasová slo¾itost je výhodná napøíklad pro~øídké grafy. Ty mají toti¾ pomìrnì malý poèet hran. \proof -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: +Zaveïme fáze stejnì jako v~dùkazu pøedchozí verze lemmatu a rozdìlme je +na~dva druhy: laciné a~drahé podle toho, kolik se~v~nich provede nenasycených +pøevedení. Pro ka¾dý druh fází pøitom odhadneme celkový poèet pøevedení +jiným zpùsobem. + +Nech» $k$~je nìjaké kladné èíslo, jeho¾ hodnotu urèíme pozdìji. +{\I Laciné fáze} budou ty, bìhem nich¾ se~provede nejvý¹e~$k$ nenasycených +pøevedení. {\I Drahé fáze} budou ty ostatní, tedy takové, ve~kterých +se~provede více jak~$k$ nenasycených pøevedení. + +Teï potøebujeme odhadnout, kolik nás budou stát oba typy fází. Zaènìme tìmi +jednodu¹¹ími -- lacinými. Jejich poèet shora odhadneme poètem v¹ech fází, +tedy~$\O(n^2).$ Nenasycených pøevedení se~bìhem jedné laciné fáze provede +nejvíce~$k$. Bìhem v¹ech laciných fází dohromady jich proto bude $\O(n^2k)$. + +Pro~poèet nenasycených pøevedení v~drahých fázích si~zaveïme nový potenciál: +$$\Psi := \sum_{\scriptstyle{v \ne z,s} \atop \scriptstyle{f^{\Delta}(v) \ne 0}} p(v),$$ +kde~$p(v)$ je poèet vrcholù~$u$, které nejsou vý¹e ne¾~$v$. Neboli: +$$p(v) = \vert \{ u \in V \mid h(u) \leq h(v) \} \vert.$$ +Tedy platí, ¾e~$p(v)$ je v¾dy nezáporné nikdy nepøesáhne poèet v¹ech vrcholù~$n$. +Proto~$\Psi$ bude také v¾dy nezáporné a nepøekroèí $n^2$. Rozmysleme si, jak +bude potenciál ovlivòován operacemi algoritmu: + \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ý¹í $\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. +\:{\I Inicializace:} Poèáteèní potenciál je nejvý¹e~$n^2$. +\:{\I Zvednutí vrcholu~$v$}: Hodnota $p(v)$ se zvý¹í nejvý¹e o~$n$ +a v¹echna ostatní~$p(w)$ se buïto nezmìní, nebo klesnou o~1. Bez ohledu +na pøebytky vrcholù se tedy potenciál zvý¹í nejvý¹e~o~$n$. +\:{\I Nasycené pøevedení} po~hranì $uv$: Hodnoty $p(\ldots)$ se nezmìní, +ale mìní se pøebytky -- vrcholu~$u$ se sni¾uje, vrcholu~$v$ zvy¹uje. +Z~potenciálu proto mù¾e zmizet èlen $p(u)$ a naopak pøibýt $p(v)$. +Potenciál~$\Psi$ tedy vzroste nejvý¹e o~$n$. +\:{\I Nenasycené pøevedení} po~hranì $uv$: Hodnoty $p(\ldots)$ se opìt +nemìní. Pøebytek v~$u$ se vynuluje, co¾ sní¾í~$\Psi$ o~$p(u)$. Pøebytek~$v$ +se naopak zvý¹í, tak¾e pokud byl pøedtím nulový, $\Psi$~se zvý¹í o~$p(v)$. +Celkovì tedy $\Psi$ klesne alespoò o~$p(u)-p(v)$. + +Teï vyu¾ijeme toho, ¾e~pokud pøevádíme po~hranì~$uv$, má tato hrana spád~1. +Výraz $p(u)-p(v)$ tedy udává poèet vrcholù na~hladinì $h(u)$, co¾ je nejvy¹¹í +hladina s~pøebytkem. Z~pøedchozího dùkazu víme, ¾e tìchto vrcholù je alespoò +tolik, kolik je nenasycených pøevedení bìhem dané fáze. + +Z~toho plyne, ¾e nenasycená pøevedení provedená bìhem drahých fází sní¾í +potenciál alespoò o~$k$. Ty v~laciných fázích ho nesni¾ují tak výraznì, +ale urèitì ho nezvý¹í. \endlist -\>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)$. +Potenciál~$\Psi$ se~tedy mù¾e zvìt¹it pouze pøi~operacích inicializace, zvednutí a~nasyceného +pøevedení. Inicializace pøispìje~$n^2$. V¹ech zvednutí se~provede celkem~$\O(n^2)$ a~ka¾dé zvý¹í potenciál nejvý¹e +o~$n$. Nasycených pøevedení se provede celkem~$\O(nm)$ a~ka¾dé zvý¹í +potenciál takté¾ nejvý¹e o~$n$. Celkem se~tedy~$\Psi$ zvý¹í nejvý¹e +o $$n^2 + n \cdot \O(n^2) + n \cdot \O(nm) = \O(n^3 + n^2m).$$ + +Teï vyu¾ijeme toho, ¾e~$\Psi$ je nezáporný potenciál, tedy kdy¾ ho ka¾dé +nenasycené pøevedení v~drahé fázi sní¾í~$\Psi$ alespoò o~$k$, mù¾e takových +pøevedení nastat nejvý¹e $\O(n^3/k + n^2m/k)$. To nyní seèteme s~odhadem +pro laciné fáze a dostaneme, ¾e v¹ech nenasycených pøevedení probìhne +$$\O \left(n^2k + {n^3 \over k} + {n^2m \over k} \right) = \O \left(n^2k + {n^2m \over k} \right)$$ +(vyu¾ili jsme toho, ¾e v~souvislých grafech je $m\ge n$, a~tedy $n^2m \ge n^3$). + +Tento odhad ov¹em platí pro libovolnou volbu~$k$. Proto zvolíme takové~$k$, +aby byl co nejni¾¹í. Jeliko¾ první èlen s~rostoucím~$k$ roste a druhý klesá, +asymptotické minimum nastane tam, kde se tyto èleny vyrovnají, tedy kdy¾ +$n^2k = n^2m / k$. + +Nastavíme tedy $k=\sqrt{m}$ a získáme ký¾ený odhad $\O(n^2\sqrt{m})$. \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)$. +\exercises -\s{Vìta:} Goldbergùv algoritmus najde maximální tok v~èase $\O(N^2M)$. +\ex{Rozeberte chování Goldbergova algoritmu na sítích s~jednotkovými kapacitami. +Bude rychlej¹í ne¾ ostatní algoritmy?} -\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~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 ? +\ex{Navrhnìte implementaci vylep¹eného Goldbergova algoritmu se zvedáním nejvy¹¹ího +vrcholu s~pøebytkem. Sna¾te se dosáhnout èasové slo¾itosti $\O(n^2\sqrt m)$.} -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í¾í. +\ex{Co by se stalo, kdybychom v~inicializaci algoritmu umístili zdroj o~1 ní¾e?} -\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)$. +\endexercises -\proof -Viz pøí¹tí pøedná¹ku. \bye