Goldberg: Prepis

[ads2.git] / 4-goldberg / 4-goldberg.tex

\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,
který bude daleko jednodu¹¹í ne¾ Dinicùv algoritmus z~pøedchozí pøedná¹ky
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 pøedná¹ek, 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 následující dvì 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.

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:

\s{Algoritmus (Goldbergùv):}

\algo
\:Nastavíme poèáteèní vý¹ky (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 (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$.
\:Vrátíme tok~$f$ jako výsledek.
\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 postupnì 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 \in E: r(uv)>0$ \& $h(u)
> h(v)+1$ (nenasycená hrana se~spádem vìt¹ím ne¾ jedna).

\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» 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$.
\: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 na~vy¹¹í.
\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~vrcholu~$v$ 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ý dùkazový 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$ je aspoò jeden
vrchol s~kladným pøebytkem, toti¾~$v$, proto 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 to mohlo stát 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{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. Neboli
$$P = \{ v \in V \setminus \{z,s\} ~\vert~ f^{\Delta}(v) > 0 \}.$$
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 pamatovat 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 aktualizovat.

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. Nejprve definujeme {\I nejvy¹¹í hladinu 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í¾í. My víme, ¾e zvednutí je
v~celém algoritmu $\O(n^2)$. Zároveò si~mù¾eme uvìdomit, ¾e~$H$ je nezáporný
potenciál, kdy sní¾ení i~zvý¹ení ho zmìní o~1, tedy poèet sní¾ení bude stejný
jako poèet zvý¹ení, a~proto obojího je~$\O(n^2)$. Tudí¾ poèet fází je
také~$\O(n^2)$.

Je dùle¾ité, ¾e~bìhem jedné fáze 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ì to 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
Rozdìlme si~fáze na~dva druhy: laciné a~drahé podle toho, kolik se~v~nich
provede nenasycených pøevedení. Zvolme si~nìjaké nezáporné~$k$. Zatím nebudeme
urèovat jeho hodnotu. Uvidíme, ¾e~èasová slo¾itost algoritmu bude závislá
na~tomto parametru~$k$. Proto jeho hodnotu zvolíme a¾ pozdìji a~to tak, aby
byla slo¾itost co nejni¾¹í.

{\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é, bìhem nich¾
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 s~tìmi
jednodu¹¹ími -- s~lacinými. Víme, ¾e~v¹ech fází je~$\O(n^2)$. Tìch laciných
bude tedy urèitì také~$O(n^2)$. Nenasycených pøevedení se~bìhem jedné laciné
fáze provede nejvíce~$k$. Tedy celkem se~bìhem laciných fází provede~$\O(n^2k)$
nenasycených pøevedení.

Pro~poèet nenasycených pøevedení v~drahých fázích si~zaveïme nový potenciál
definovaný následovnì:
$$\Phi := \sum_{\scriptstyle{v \ne z,s} \atop \scriptstyle{f^{\Delta}(v) \ne 0}} {p(v) \over k},$$
kde~$p(v)$ je poèet takových 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é a~nejvý¹e má hodnotu~$n$. Dále víme,
¾e~$\Phi$ bude v¾dy nezáporné (nebo» je to souèet nezáporných èlenù) a~nejvý¹e
bude nabývat hodnoty~$n^2 / k$. Rozmysleme si, jak nám ovlivní tento
potenciál na¹e tøi operace:

\itemize\ibull
\:{\I Zvednutí}: Za~ka¾dý zvednutý vrchol pøibude nejvý¹e~$n / k$ (tento
vrchol mù¾e být nadzvednut nejvý¹e nad~v¹echny ostatní vrcholy) a~mo¾ná nìco
ubude (napø. kdy¾ vrchol vyzvedneme na~úroveò k~ostatním).
\:{\I Nasycené pøevedení} po~hranì $uv$: Mù¾e vynulovat pøebytek
ve~vrcholu~$u$, pak se~$\Phi$ sní¾í. Mù¾e zvý¹it pøebytek ve~$v$ z~nuly, pak
se~$\Phi$ zvý¹í. Ale nejvý¹e se~zvý¹í o~$n / k$, nebo» do~$\Phi$ pøibude
jen jeden sèítanec za~vrchol $v$ a~ten pøispìje nejvý¹e hodnotou~$n / k$
(pod ním mù¾e být nejvíce~$n$ vrcholù).
\:{\I Nenasycená pøevedení} po~hranì $uv$ v~drahých fázích: Tato operace
vynuluje pøebytek v~$u$, tedy~$\Phi$ klesne alespoò o~$p(u) / k$. Zároveò
mù¾e zvý¹it pøebytek ve~$v$ z~nuly, ale~$\Phi$ stoupne nejvý¹e o~$p(v) / k$.
Celkem tedy~$\Phi$ klesne alespoò o~$p(u) - p(v) / k$.
\endlist

Uvìdomme si, ¾e~pokud pøevádíme po~hranì~$uv$, tak platí, ¾e~$h(u) = h(v) + 1$.
Pak~$p(u) - p(v)$ je pøesnì poèet vrcholù na~hladinì~$H$. Tìch je alespoò
tolik, kolik je nenasycených pøevedení bìhem jedné fáze (to jsme dokázali ji¾
v~lemmatu N'), a~my jsme si~nadefinovali, ¾e v~drahé fázi je poèet nenasycených
pøevedení alespoò~$k$. Tedy~$p(u) - p(v) > k$. Proto bìhem jednoho nenasyceného
pøevedení~$\Phi$ klesne alespoò o~${k / k} = 1$. Nenasycená pøevedení
potenciál nezvy¹ují.

Potenciál~$\Phi$ se~mù¾e zvìt¹it pouze pøi~operacích zvednutí a~nasycené
pøevedení. Zvednutí se~provede celkem~$\O(n^2)$ a~ka¾dé zvý¹í potenciál nejvý¹e
o~$n / k$. Nasycených pøevedení se provede celkem~$\O(nm)$ a~ka¾dé zvý¹í
potenciál takté¾ nejvý¹e o~$n / k$. Celkem se~tedy~$\Phi$ zvý¹í nejvý¹e
o $${n \over k} \cdot \O(n^2) + {n \over k} \cdot \O(nm) = \O \left({n^3 \over k} + {n^2m
\over k}\right).$$

Teï vyu¾ijeme toho, ¾e~$\Phi$ je nezáporný potenciál, tedy kdy¾ ka¾dé
nenasycené pøevdení v~drahé fázi sní¾í~$\Phi$ alespoò o~1, tak v¹ech
nenasycených pøevdení v~drahých fázích je~$\O({n^3 / k} + {n^2m / k})$.
U¾ jsme ukázali, ¾e~nenasycených pøevední v~laciných fázích je~$\O(n^2k)$.
Proto celkem v¹ech nenasycených pøevedení je $$\O \left(n^2k + {n^3 \over k}
+ {n^2m \over k} \right) = \O \left(n^2k + {n^2m \over k} \right)$$ (nebo»
pro~souvislé grafy platí, ¾e~$m \geq n \Rightarrow n^2m \geq n^3$). A~my
chceme, aby jich bylo co nejménì. Tato funkce má minimum tehdy, kdy¾ $n^2k
= {n^2m \over k}$, èili $k = \sqrt{m}$.

Proto v¹ech nenasycených pøevedení je $\O(n^2\sqrt{m})$.
\qed
\bye