-\input lecnotes.tex\r
-\r
-\prednaska{4}{Goldgergùv algoritmus}{(zapsali R. Tupec, \r
-%J. Volec,\r
-J. Záloha)}\r
-\r
-\noindent\r
-Pøedstavíme si nový algoritmus pro hledání toku v síti, který se uká¾e stejnì dobrý jako\r
-{\I Dinicùv alogritmus} ($\O(mn^{2})$), a po nìkolika vylep¹eních bude i lep¹í.\r
-\r
-\s{Definice:} Funkce $f:E \rightarrow \bb{R}_{0}^{+}$ \r
-je {\I vlna} v síti ($V, E, z, s, c$), t.¾. $ \forall e \in E : f(e) \leq c(e) \wedge $ pro \r
-$ \forall v \ne z, v \ne s : f^{\Delta}(v) \geq 0 $.\r
-\r
-\s{Poznámka:} Funkce $f^{\Delta}(v)$ vrací pøebytek ve vrcholu \r
-$v$ : $$f^{\Delta}(v):=\sum_{(u,v) \in E}{f(u,v)} - \sum_{(v,u) \in E}{f(v,u)}$$\r
-Tok je vlna, kde $ f^{\Delta}(v) = 0 , \forall v \in V , v \ne z,s $.\r
-\r
-\noindent r(v,u)\r
-V algoritmu budeme provádìt dvì operace na vrcholech sítì. K tomu budeme potøebovat pøiøadit v¹em \r
-vrcholùm vý¹ky pomocí funkce $h : V \rightarrow \bb{N}$.\r
-\r
-\s{Operace:} pro $ (u,v) \in E$\r
-\r
-\algo\r
-\:{\I Pøevedení pøebytku} \r
-\r
-Pokud platí:\r
-\itemize\ibull\r
- \: $u : f^{\Delta}(v) > 0$\r
- \: $v : h(u) > h(v)$\r
- \: $r(u,v)>0$ \r
-\endlist\r
- 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$ .\r
-\r
-Øekneme, ¾e pøevedení je {\I nasycené}, pokud je po pøevodu rezerva na hranì $(u,v)$ nulová, tedy $r(u,v)=0$. \r
-Naopak pøevedení {\I nenasycené}, pokud po pøevodu $f^{\Delta}(v) = 0$. Pokud $r(u,v)=0 \wedge f^{\Delta}(v) = 0$\r
-budeme pøevedení pova¾ovat za {\I nasycené}.\r
-\r
-\:{\I Zvednutí vrcholu} $u$ \r
-\r
-Pokud v algoritmu narazíme na pøebytek, kterého se nelze pøevést, zvedneme vrchol $h(u):=h(u)+1$. \r
-\endalgo\r
-\r
-\s{Algoritmus:} (Goldberg)\r
-\r
-\algo\r
-\:$h(*)\leftarrow 0, h(z)\leftarrow \bb{N}$.\r
-\:$f(*)\leftarrow 0, \forall u \in V, (z,u) \in E : f(u,v)\leftarrow c(z,u)$.\r
-\:Dokud $\exists u \in V, u \ne z, u \ne s, f^{\Delta}(u)>0$: \r
-\:Pokud $\exists (u,v) \in E, r(u,v)>0 \wedge h(u)>h(v)$, tak prevedeme pøebytek po (u,v).\r
-\:Jinak zvedneme $u$.\r
-\:Vrátíme tok $f$ jako výsledek.\r
-\endalgo\r
-\r
-\s{Poznámka:} Pokud v síti neexistují nìkteré zpìtné hrany, tak je tam pøidáme s nulovou kapacitou\r
-\r
-\noindent\r
-Následovat bude nìkolik lemmat a invariantù, jimi¾ se doká¾e správnost a èasová slo¾itost vý¹e popsaného\r
-agoritmu.\r
-\r
-\s{Invariant A:} Funkce $f:E \rightarrow \bb{R}$ vrácená algoritmem je vlna. Pro $\forall v \in V, h(v)$ neklesá a\r
-$h(z)=N, h(s)=0$.\r
-\r
-\proof\r
-Pro první èást invariantu si staèí rozmyslet, ¾e v~¾ádném kroku algoritmu nepøekroèíme kapacity hran a~nevytvoøíme\r
-záporný pøebytek. Pro $\forall v \in V, v \ne z, v \ne$ skuteènì vý¹ku pouze zvy¹ujeme a z podmínky v tøetím kroku\r
-algoritmu vyplývá, ¾e nás pøebytky v $z$ a $s$ v podstatì nezajímají, tudí¾ ani nemìníme jejich vý¹ku. \r
-\qed\r
-\r
-\s{Invariant S(o spádu):} Pro $\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.\r
-\r
-\proof\r
-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 pøebytkem a nenasycená hrana $(v,u)$ a platí $h(v)=h(u)+1$ vrchol $v$ algoritmu 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.\r
-\qed \r
-\r
-\s{Lemma K (o korektnosti)} Kdy¾ se algorimus zastaví, vydá maxinální tok.\r
-\r
-\proof\r
-Vyjdìme z toho, ¾e $f$ je vlna a algorimus se mù¾e zastavit v tìchto pøípadech:\r
-\itemize\ibull\r
-\:ve vrcholech grafu nejsou ¾ádné pøebytky. Potom, ale $f$ je zároveò tok.\r
-\:pokud existuje nenasycená cesta $P$ ze zdroje do stoku. O té víme, ¾e má maximálnì $n-1$ hran. Zároveò v¹ak musí mít spád $N$, ale to znamená, ¾e existuje hrana $(u,v)$, pro kterou platí $h(u,v)>=2$, ale to je spor s Invariantem S.\r
-\endlist\r
-\qed\r
-\r
-\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$.\r
-\r
-\proof\r
-Mìjme nìjaký vrchol $v \in V(G)$ takový, ¾e $f^{\Delta}(v) > 0$.\r
-Potom definujme mno¾inu $A := \{ u \in V(G) : \exists$ nenasycená cesta z $v$ do $u \}$.\r
-Mìjme vrcholy $a \in A$ a $b \in V(G) - 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$.\r
-\r
-\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 tedy jedenkrát pøiètou a jedenkrát odeètou, platí:\r
-$$\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)$$\r
-Proto¾e v¹ak do $A$ nic neteèe, nebo\9d obsahuje zdroj (pokud není izolovaný, existují nenasycené zpìtné hrany), tento výraz musí být men¹í, 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$ musí být zdroj, proto¾e v¹echny ostatní vrcholy mají kladný pøebytek.\r
-\qed\r
-\s{Invariant V (vý¹ka)} Pro $\forall v \in V$ platí $h(v)<=2N$.\r
-\r
-\proof\r
-Víme, ¾e poèet hran v cestì ze $z$ do $\forall v \in V$ je maximálnì $N-1$.\r
-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 $\acute{v}$, musí platit $h(v)<=h(\acute{v})$ a tedy $v$ bude zvednut po 2N. 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 v cestì ze $z$ do $v$ existuje hrana se spádem vìt¹ím ne¾ 1 a to je spor s Invariantem S.\r
-\qed\r
-\r
-\s{Lemma Z (poèet zvednutí)} Poèet v¹ech zvednutí je maximálnì $2N^{2}$.\r
-\r
-\proof\r
-Staèí si uvìdomit, ¾e ka¾dý vrchol zvednut maximálnì 2N-krát a vrcholù je N.\r
-\qed\r
-%\r
-%\s{Definice:} Nasycené pøevedení je pøevedení pøebytku z vrcholu hranou takové, ¾e tato hrana bude nasycena.\r
-%\r
-%\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.\r
-\r
-\s{Lemma SY (sytá pøevedení)} Poìet v¹ech sytých pøevedení je maximálnì $NM$.\r
-\r
-\proof\r
-Mìjme hranu $(u,v) \in E$, kterou jsme právì nasytili. Tedy platí $h(v)<h(u)$ a zároveò $r(u, v)=0$. Aby se rezerva této hrany zmìnila, musel by ji nìkdo odsytit. Ale nutná podmínka pro odsycení hrany je, ¾e se otoèí nerovnost mezi vý¹kami koncových vrcholù. Tedy $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)$. Mezi dvìma nasyceními hrany $(u,v)$ probìhly minimálnì dvì zvednutí vrcholu $u$. Algoritmus nikdy vý¹ku vrcholu nesni¾uje, a tedy poèet v¹ech sytých pøevedení je skuteènì $NM$.\r
-\qed\r
-\r
-\r
-\r
-\end\r
+\input lecnotes.tex
+
+\prednaska{4}{Goldbergùv algoritmus}{}
+
+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.
+
+\h{Vlny a pøebytky}
+
+\s{Znaèení} z~minulých kapitol, které se nám bude hodit:
+
+\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
+
+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{Definice:} Funkce $f:E \rightarrow {\bb R}_0^+$ je {\I vlna} v~síti~$S$,
+splòuje-li obì následující podmínky:
+
+\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
+
+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
+\: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
+
+\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{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.
+
+\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:
+
+\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
+
+\s{Lemma K (o~Korektnosti):} Kdy¾ se~algoritmus zastaví, je~$f$ maximální tok.
+
+\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
+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 V (Vý¹ka):} Pro ka¾dý vrchol~$v$ je $h(v)\leq 2n$.
+
+\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 Z (poèet Zvednutí):} Bìhem výpoètu nastane nejvý¹e $2n^{2}$ zvednutí.
+
+\proof
+Z~pøedchozího invariantu plyne, ¾e ka¾dý vrchol mohl být zvednut nejvý¹e $2n$-krát.
+Vrcholù je~$n$.
+\qed
+
+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:
+
+\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í).
+
+\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{Potenciálová metoda:}
+Pøedchozí dvì lemmata jsme dokazovali \uv{lokálním} zpùsobem -- zvednutí jsme poèítali
+pro ka¾dý vrchol zvlá¹» a nasycená pøevedení pro ka¾dou hranu. Tento pøístup pro nenasycená
+pøevedení nefunguje, jeliko¾ jich lokálnì mù¾e být velmi mnoho.
+Podaøí se nám nicménì omezit jejich celkový poèet.
+
+Jedím ze~zpùsobù, jak taková \uv{globální} tvrzení o~chování algoritmù dokazovat,
+je pou¾ít {\I potenciál.} To je nìjaká {\I nezáporná} funkce, která popisuje stav výpoètu.
+Pro ka¾dou operaci pak stanovíme, jaký vliv má na hodnotu potenciálu. Z~toho odvodíme,
+¾e operací, které potenciál sni¾ují, nemù¾e být výraznì více ne¾ tìch, které ho zvy¹ují.
+Jinak by toti¾ potenciál musel nìkdy bìhem výpoètu klesnout pod nulu.
+
+S~tímto druhem dùkazu jsme se vlastnì u¾ setkali. To kdy¾ jsme v~kapitole o~vyhledávání v~textu
+odhadovali poèet prùchodù po~zpìtných hranách. Roli potenciálu tam hrálo èíslo stavu.
+
+V~následujícím lemmatu bude potenciál trochu slo¾itìj¹í. Zvolíme ho tak, aby
+operace, jejich¾ poèty u¾ známe (zvednutí, nasycené pøevedení), pøispívaly
+nanejvý¹ malými kladnými èísly, a~nenasycená pøevedení potenciál v¾dy
+sni¾ovala.
+
+\s{Lemma N (Nenasycená pøevedení):} Poèet v¹ech nenasycených pøevedení je~$\O(n^2m)$.
+
+\proof
+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
+
+\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
+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
+
+\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
+Dokazovat budeme opìt pomocí potenciálové metody. Vrcholy rozdìlíme do~hladin
+podle vý¹ky. Speciálnì nás bude zajímat {\I nejvy¹¹í hladina s~pøebytkem}:
+$$H := \max \{ h(v) \mid v \neq z,s ~\&~ f^\Delta(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
+
+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
+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
+\:{\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
+
+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
+
+\exercises
+
+\ex{Rozeberte chování Goldbergova algoritmu na sítích s~jednotkovými kapacitami.
+Bude rychlej¹í ne¾ ostatní algoritmy?}
+
+\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)$.}
+
+\ex{Co by se stalo, kdybychom v~inicializaci algoritmu umístili zdroj o~1 ní¾e?}
+
+\endexercises
+
+\bye
projects / ads2.git / blobdiff