From c4b7533943d77f47e0ae3999ce2263e65b59cf5d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 7 Nov 2011 21:41:09 +0100 Subject: [PATCH] Goldberg: Zmena znaceni: N->n, M->m, K->k --- 4-goldberg/4-goldberg.tex | 94 +++++++++++++++++++-------------------- 1 file changed, 47 insertions(+), 47 deletions(-) diff --git a/4-goldberg/4-goldberg.tex b/4-goldberg/4-goldberg.tex index f091177..6288dfb 100644 --- a/4-goldberg/4-goldberg.tex +++ b/4-goldberg/4-goldberg.tex @@ -3,7 +3,7 @@ \prednaska{4}{Goldbergùv algoritmus}{} Pøedstavíme si~nový algoritmus pro~hledání maximálního toku v~síti, který -se~uká¾e být stejnì dobrý jako {\I Dinicùv algoritmus} ($\O(MN^{2})$) +se~uká¾e být stejnì dobrý jako {\I Dinicùv algoritmus} ($\O(mn^{2})$) a~po~nìkolika vylep¹eních bude i~lep¹í. Nejdøíve si~pøipomeòme definice, které budeme potøebovat: @@ -17,8 +17,8 @@ v následovnì: $$r(uv) = c(uv) - f(uv) + f(vu).$$ Rezerva hrany znaèí, co je¹tì je mo¾no po~této hranì poslat. -\s{Poznámka:} Dále budeme oznaèovat písmenem~$N$ poèet vrcholù a~$M$ poèet -hran, tedy~$N = \vert V \vert$ a~$M = \vert E \vert$. +\s{Poznámka:} Dále budeme oznaèovat písmenem~$n$ poèet vrcholù a~$m$ poèet +hran, tedy~$n = \vert V \vert$ a~$m = \vert E \vert$. Goldbergùv algoritmus na~rozdíl od~Dinicova algoritmu zaèíná s~ohodnocením hran, které pravdìpodobnì není tokem (budeme ho nazývat {\I vlna}), a~postupnì @@ -59,7 +59,7 @@ Pokud b \s{Algoritmus (Goldbergùv)} \algo -\:$\forall v \in V: h(v)\leftarrow 0$ (v¹em vrcholùm nastavíme poèáteèní vý¹ku nula) a~$h(z)\leftarrow N$ (zdroj zvedneme do~vý¹ky~$N$). +\:$\forall v \in V: h(v)\leftarrow 0$ (v¹em vrcholùm nastavíme poèáteèní vý¹ku nula) a~$h(z)\leftarrow n$ (zdroj zvedneme do~vý¹ky~$n$). \:$\forall e \in E: f(e)\leftarrow 0$ (po~hranách nejdøíve nenecháme protékat nic) a~$\forall zu \in E : f(zu)\leftarrow c(zu)$ (ze~zdroje pustíme maximální mo¾nou vlnu). \: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)$, pak pøevedeme pøebytek po~hranì z~$u$ do~$v$. @@ -74,12 +74,12 @@ Nyn \numlist \ndotted \:Funkce~$f$ je v~ka¾dém kroku algoritmu vlna. \:$h(v)$ nikdy neklesá pro~¾ádné~$v$. - \:$h(z)=N$ a~$h(s)=0$ po~celou dobu bìhu algoritmu. + \:$h(z)=n$ a~$h(s)=0$ po~celou dobu bìhu algoritmu. \endlist \proof Indukcí dle poètu prùchodù cyklem (3. -- 5. krok algoritmu). -Na zaèátku je v¹e v~poøádku ($f$ je nulová funkce, pøebytky v¹ech vrcholù jsou nezáporné, tedy~$f$ je vlna, $h(z)=N$ a~$h(s)=0$). V~prùbìhu se~tyto hodnoty mìní pouze pøi: +Na zaèátku je v¹e v~poøádku ($f$ je nulová funkce, pøebytky v¹ech vrcholù jsou nezáporné, tedy~$f$ je vlna, $h(z)=n$ a~$h(s)=0$). V~prùbìhu se~tyto hodnoty mìní pouze pøi: \itemize\ibull \:Pøevedení po~hranì~$uv$: Po hranì~$uv$ se~nepo¹le více ne¾ její rezerva. Pøebytek~$u$ se~sní¾í, ale nejménì na~nulu. Pøebytek~$v$ se~zvý¹í. Tedy~$f$ zùstává vlnou. Vý¹ky se~nemìní. \:Zvednutí vrcholu~$u$: Mìní pouze vý¹ky -- a~to vrcholù rùzných od zdroje èi stoku -- a~pouze se zvy¹ují. @@ -105,7 +105,7 @@ Na za \numlist\ndotted \:Nech» se~algoritmus zastavil. Pak nemohl existovat ¾ádný vrchol~$v$ (kromì zdroje a~stoku) s~kladným pøebytkem. Tedy $\forall v \in V~\setminus \{z,s\}: f^\Delta(v) = 0$. (Víme ji¾, ¾e~$f$ je po~celou dobu vlna, tak¾e pøebytek nemù¾e být nikdy záporný.) V~tom pøípadì splòuje~$f$ podmínky toku. - \:Pro spor pøedpokládejme, ¾e tok~$f$ není maximální. Pak existuje nenasycená cesta ze~zdroje do~stoku. Vezmìme si~libovolnou takovou cestu. Zdroj je stále ve~vý¹ce~$N$ a~spotøebiè ve~vý¹ce 0 (viz invariant A). Tato cesta tedy pøekonává vý¹ku~$N$, ale mù¾e mít nejvý¹e~$N-1$ hran. Proto existuje alespoò jedna hrana se~spádem alespoò 2. Tato hrana tedy nemù¾e mít kladnou rezervu (viz invariant S). Tato cesta proto nemù¾e být zlep¹ující, co¾ je spor. Tím jsme dokázali, ¾e~$f$ je nutnì maximální tok. + \:Pro spor pøedpokládejme, ¾e tok~$f$ není maximální. Pak existuje nenasycená cesta ze~zdroje do~stoku. Vezmìme si~libovolnou takovou cestu. Zdroj je stále ve~vý¹ce~$n$ a~spotøebiè ve~vý¹ce 0 (viz invariant A). Tato cesta tedy pøekonává vý¹ku~$n$, ale mù¾e mít nejvý¹e~$n-1$ hran. Proto existuje alespoò jedna hrana se~spádem alespoò 2. Tato hrana tedy nemù¾e mít kladnou rezervu (viz invariant S). Tato cesta proto nemù¾e být zlep¹ující, co¾ je spor. Tím jsme dokázali, ¾e~$f$ je nutnì maximální tok. \qeditem \endlist @@ -127,23 +127,23 @@ Pro Proto $\sum_{u \in A}{f^\Delta(u) \le 0}$. Zároveò v¹ak v~$A$ je aspoò jeden vrchol s~kladným pøebytkem, toti¾~$v$, proto v~$A$ musí být také vrchol se~záporným pøebytkem -- a~jediný takový je zdroj. Tím je dokázáno, ¾e $z \in A$, tedy ¾e vede nenasycená cesta z~vrcholu~$v$ do~zdroje. \qed -\s{Invariant V (Vý¹ka):} $\forall v \in V$ platí $h(v)\leq 2N$. +\s{Invariant V (Vý¹ka):} $\forall v \in V$ platí $h(v)\leq 2n$. \proof -Kdyby existoval vrchol~$v$ s~vý¹kou $h(v) > 2N$, tak by musel být nìkdy zvednut z~vý¹ky~$2N$. Tehdy musel mít kladný pøebytek $f^\Delta(v)>0$ (jinak by nemohl být zvednut). Dle lemmatu C musela existovat nenasycená cesta z~$v$ do~zdroje. Tato cesta mìla spád alespoò~$N$, ale mohla mít nejvý¹e~$N-1$ hran (jinak by to nebyla cesta v~síti na~$N$ vrcholech). Tudí¾ musela na~této cestì existovat hrana se~spádem alespoò 2, co¾ je spor s~invariantem S (nebo» v¹echny hrany této cesty mají z~definice nenasycené cesty kladné rezervy). +Kdyby existoval vrchol~$v$ s~vý¹kou $h(v) > 2n$, tak by musel být nìkdy zvednut z~vý¹ky~$2n$. Tehdy musel mít kladný pøebytek $f^\Delta(v)>0$ (jinak by nemohl být zvednut). Dle lemmatu C musela existovat nenasycená cesta z~$v$ do~zdroje. Tato cesta mìla spád alespoò~$n$, ale mohla mít nejvý¹e~$n-1$ hran (jinak by to nebyla cesta v~síti na~$n$ vrcholech). Tudí¾ musela na~této cestì existovat hrana se~spádem alespoò 2, co¾ je spor s~invariantem S (nebo» v¹echny hrany této cesty mají z~definice nenasycené cesty kladné rezervy). \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 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í je {\I nasycené}, pokud po~pøevodu rezerva na~hranì~$uv$ klesla na~nulu, tedy $r(uv)=0$. V~opaèném pøípadì je {\I nenasycené}, a~tehdy urèitì klesne pøebytek ve~vrcholu~$u$ na~nulu, tedy $f^{\Delta}(u) = 0$ (pøi~nasyceném pøevedení se~to~ale mù¾e stát také). -\s{Lemma S (naSycená pøevedení):} Poèet v¹ech nasycených pøevedení je nejvý¹~$NM$. +\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: @@ -151,10 +151,10 @@ Pro ka 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 lemma~S). Po~této hranì tedy nemù¾eme u¾~nic více pøevést. Aby do¹lo k~druhému nasycenému pøevedení z~$u$ do~$v$, musíme nejprve opìt zvý¹it rezervu hrany~$uv$. 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 si~tedy, ¾e mezi ka¾dými dvìma nasycenými pøevedeními jsme vrchol~$u$ zvedli alespoò dvakrát. Nicménì libovolnou hranu mù¾eme zvednout nejvý¹e~$2N$-krát (viz invariant V). V¹ech hran je~$M$, tudí¾ poèet v¹ech nasycených pøevedení je nejvý¹e~$NM$. +Ukázali jsme si~tedy, ¾e mezi ka¾dými dvìma nasycenými pøevedeními jsme vrchol~$u$ zvedli alespoò dvakrát. Nicménì libovolnou hranu mù¾eme zvednout nejvý¹e~$2n$-krát (viz invariant V). V¹ech hran je~$m$, tudí¾ poèet v¹ech nasycených pøevedení je nejvý¹e~$nm$. \qed -\s{Lemma N (Nenasycená pøevedení):} Poèet v¹ech nenasycených pøevedení je~$\O(N^2M)$. +\s{Lemma N (Nenasycená pøevedení):} Poèet v¹ech nenasycených pøevedení je~$\O(n^2m)$. \proof Dùkaz provedeme pomocí potenciálové metody -- nadefinujme si~následující funkci jako potenciál: @@ -164,12 +164,12 @@ Nyn \itemize\ibull \:Na poèátku je $ \Phi = 0 $. \:Bìhem celého algoritmu je $ \Phi \ge 0 $, nebo» je souètem nezáporných èlenù. - \:Zvednutí vrcholu zvý¹í $\Phi$ o~jednièku (Aby byl vrchol zvednut, musel mít kladný pøebytek $\Rightarrow$ vrchol do~sumy ji¾ pøispíval, teï jen pøispìje èíslem o 1 vy¹¹ím.). Ji¾ víme, ¾e za~celý prùbìh algoritmu je v¹ech zvednutí maximálnì~$2N^2$, proto zvedáním vrcholù zvý¹íme potenciál dohromady nejvý¹e o~$2N^2$. - \:Nasycené pøevedení zvý¹í~$\Phi$ nejvý¹e o~$2N$, proto¾e buï po~pøevodu hranou~$uv$ v~$u$ zùstal nìjaký pøebytek, tak¾e se~mohl potenciál zvý¹it nejvý¹e o~$h(v) \leq 2N$, nebo je pøebytek v~$u$ po~pøevodu nulový a~potenciál se~dokonce o~jedna sní¾il. Za~celý prùbìh tak dojde k~maximálnì~$NM$ takovýmto pøevedením, díky nim¾ se~potenciál zvý¹í maximálnì o~$2N^2M$. + \:Zvednutí vrcholu zvý¹í $\Phi$ o~jednièku (Aby byl vrchol zvednut, musel mít kladný pøebytek $\Rightarrow$ vrchol do~sumy ji¾ pøispíval, teï jen pøispìje èíslem o 1 vy¹¹ím.). Ji¾ víme, ¾e za~celý prùbìh algoritmu je v¹ech zvednutí maximálnì~$2n^2$, proto zvedáním vrcholù zvý¹íme potenciál dohromady nejvý¹e o~$2n^2$. + \:Nasycené pøevedení zvý¹í~$\Phi$ nejvý¹e o~$2n$, proto¾e buï po~pøevodu hranou~$uv$ v~$u$ zùstal nìjaký pøebytek, tak¾e se~mohl potenciál zvý¹it nejvý¹e o~$h(v) \leq 2n$, nebo je pøebytek v~$u$ po~pøevodu nulový a~potenciál se~dokonce o~jedna sní¾il. Za~celý prùbìh tak dojde k~maximálnì~$nm$ takovýmto pøevedením, díky nim¾ se~potenciál zvý¹í maximálnì o~$2n^2m$. \: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 -\>Z~tohoto rozboru chování potenciálu~$\Phi$ v~prùbìhu algoritmu získáváme, ¾e poèet v¹ech nenasycených pøevedení mù¾e být nejvý¹e $2N^2 + 2N^2M$, co¾ je $\O(N^2M)$. +\>Z~tohoto rozboru chování potenciálu~$\Phi$ v~prùbìhu algoritmu získáváme, ¾e poèet v¹ech nenasycených pøevedení mù¾e být nejvý¹e $2n^2 + 2n^2m$, co¾ je $\O(n^2m)$. \qed \s{Implementace:} @@ -185,8 +185,8 @@ D \s{Rozbor èasové slo¾itosti algoritmu:} \numlist\ndotted -\:Inicializace vý¹ek \dots\ $\O(N)$. -\:Inicializace vlny~$f$ \dots\ $\O(M)$. +\:Inicializace vý¹ek \dots\ $\O(n)$. +\:Inicializace vlny~$f$ \dots\ $\O(m)$. \:Výbìr vrcholu~$u$ s~kladným pøebytkem -- vezmeme první vrchol v~$P$ \dots\ $\O(1)$. \:Výbìr vrcholu~$v$, do~kterého vede z~$u$ hrana s~kladnou rezervou a~který je ní¾e ne¾~$u$ -- vezmeme první hranu z~$L(u)$ \dots\ $\O(1)$. @@ -205,9 +205,9 @@ D \:Pøebytek vrcholu~$v$ se~zvý¹í~$\Rightarrow$ pokud je¹tì nebyl v~seznamu~$P$, tak se~tam pøidá \dots\ $\O(1)$. \endlist \endlist -\:Zvednutí vrcholu~$u$ \dots $\O(N)$. +\:Zvednutí vrcholu~$u$ \dots $\O(n)$. -Musíme obejít v¹echny hrany do~$u$ a~z~$u$, kterých je nejvý¹e~$2N-2$, porovnat +Musíme obejít v¹echny hrany do~$u$ a~z~$u$, kterých je nejvý¹e~$2n-2$, porovnat vý¹ky a~pøípadnì tyto hrany~$uv$ odebrat ze~seznamu~$L(v)$ resp. pøidat do~$L(u)$. Abychom pro~odebrání hrany~$uv$ ze~seznamu~$L(v)$ nemuseli procházet celý seznam, budeme si~$\forall u \in V$ pamatovat je¹tì $L^{-1}(u) := $ seznam @@ -220,21 +220,21 @@ Vid \s{Shrnutí:} \itemize\ibull -\:V¹ech zvednutí je $\O(N^2)$ (viz lemma Z), ka¾dé trvá $\O(N)$ \dots\ $\O(N^3).$ -\:V¹ech nasycených pøevedení je $\O(NM)$ (viz lemma S), ka¾dé trvá $\O(1)$ \dots\ $\O(NM).$ -\:V¹ech nenasycených pøevedení je $\O(N^2M)$ (viz lemma N), ka¾dé trvá $\O(1)$ \dots\ $\O(N^2M).$ +\:V¹ech zvednutí je $\O(n^2)$ (viz lemma Z), ka¾dé trvá $\O(n)$ \dots\ $\O(n^3).$ +\:V¹ech nasycených pøevedení je $\O(nm)$ (viz lemma S), ka¾dé trvá $\O(1)$ \dots\ $\O(nm).$ +\:V¹ech nenasycených pøevedení je $\O(n^2m)$ (viz lemma N), ka¾dé trvá $\O(1)$ \dots\ $\O(n^2m).$ \endlist -Dohromady má tedy Goldbergùv algoritmus èasovou slo¾itost $\O(N^2M)$. Vidíme, ¾e u¾ v~tomto obecném pøípadì to není hor¹í ne¾ Dinicùv algoritmus. Pøí¹tì si~uká¾eme, ¾e mù¾e mít i~mnohem lep¹í. Nejdøíve ale zformulujme v¹echna dokázaná tvrzení do~následující vìty: +Dohromady má tedy Goldbergùv algoritmus èasovou slo¾itost $\O(n^2m)$. Vidíme, ¾e u¾ v~tomto obecném pøípadì to není hor¹í ne¾ Dinicùv algoritmus. Pøí¹tì si~uká¾eme, ¾e mù¾e mít i~mnohem lep¹í. Nejdøíve ale zformulujme v¹echna dokázaná tvrzení do~následující vìty: -\s{Vìta:} Goldbergùv algoritmus najde maximální tok v~èase $\O(N^2M)$. +\s{Vìta:} Goldbergùv algoritmus najde maximální tok v~èase $\O(n^2m)$. \s{Pozorování:} Pokud bychom volili v¾dy nejvy¹¹í z~vrcholù s~pøebytkem, tak by se~mohl algoritmus chovat lépe. Podívejme se~na~to pozornìji a~vylep¹ený Goldebrgùv algoritmus oznaème G'. \s{Algoritmus (Vylep¹ený Goldbergùv algoritmus)} \algo -\:$\forall v \in V: h(v)\leftarrow 0$ (v¹em vrcholùm nastavíme poèáteèní vý¹ku nula) a~$h(z)\leftarrow N$ (zdroj zvedneme do~vý¹ky~$N$). +\:$\forall v \in V: h(v)\leftarrow 0$ (v¹em vrcholùm nastavíme poèáteèní vý¹ku nula) a~$h(z)\leftarrow n$ (zdroj zvedneme do~vý¹ky~$n$). \:$\forall e \in E: f(e)\leftarrow 0$ (po~hranách nejdøíve nenecháme protékat nic) a~$\forall zu \in E : f(zu)\leftarrow c(zu)$ (ze~zdroje pustíme maximální mo¾nou vlnu). \:Dokud $\exists u \in V \setminus \{z,s\}: f^{\Delta}(u)>0$: \::Vybereme z~vrcholù s~pøebytkem ten s~nejvy¹¹í vý¹kou, oznaèíme ho~$u$. @@ -243,52 +243,52 @@ Dohromady m \:Vrátíme tok~$f$ jako výsledek. \endalgo -Rozmysleme si, o~kolik bude vylep¹ený algoritmus G' lep¹í ne¾ ten pùvodní. Ten pùvodní mìl èasovou slo¾itost $\O(N^2M)$ a~pøevládal èlen, který odpovídal nenasyceným pøevedením. Zkusme tedy právì poèet nenasycených pøevedení odhadnout ve~vylep¹eném algoritmu o~nìco tìsnìji. +Rozmysleme si, o~kolik bude vylep¹ený algoritmus G' lep¹í ne¾ ten pùvodní. Ten pùvodní mìl èasovou slo¾itost $\O(n^2m)$ a~pøevládal èlen, který odpovídal nenasyceným pøevedením. Zkusme tedy právì poèet nenasycených pøevedení odhadnout ve~vylep¹eném algoritmu o~nìco tìsnìji. -\s{Lemma N' (Nenasycená pøevedení):} Algoritmus G' provede~$\O(N^3)$ nenasycených pøevedení. +\s{Lemma N' (Nenasycená pøevedení):} Algoritmus G' provede~$\O(n^3)$ nenasycených pøevedení. \proof Dokazovat budeme opìt pomocí potenciálové metody. Zadefinujme si~potenciál {\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)$. +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)$. +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{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¾¹í. +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í. +{\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í. +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},$$ +$$\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 \over K$. Rozmysleme si, jak nám ovlivní tento potenciál na¹e tøi operace: +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 \over k$. Rozmysleme si, jak nám ovlivní tento potenciál na¹e tøi operace: \itemize\ibull -\:{\bf Zvednutí}: Za~ka¾dý zvednutý vrchol pøibude nejvý¹e~$N \over 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). -\:{\bf 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 \over K$, nebo» do~$\Phi$ pøibude jen jeden sèítanec za~vrchol $v$ a~ten pøispìje nejvý¹e hodnotou~$N \over K$ (pod ním mù¾e být nejvíce~$N$ vrcholù). -\:{\bf 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) \over K$. Zároveò mù¾e zvý¹it pøebytek ve~$v$ z~nuly, ale~$\Phi$ stoupne nejvý¹e o~$p(v) \over K$. Celkem tedy~$\Phi$ klesne alespoò o~$p(u) - p(v) \over K$. +\:{\bf Zvednutí}: Za~ka¾dý zvednutý vrchol pøibude nejvý¹e~$n \over 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). +\:{\bf 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 \over k$, nebo» do~$\Phi$ pøibude jen jeden sèítanec za~vrchol $v$ a~ten pøispìje nejvý¹e hodnotou~$n \over k$ (pod ním mù¾e být nejvíce~$n$ vrcholù). +\:{\bf 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) \over k$. Zároveò mù¾e zvý¹it pøebytek ve~$v$ z~nuly, ale~$\Phi$ stoupne nejvý¹e o~$p(v) \over k$. Celkem tedy~$\Phi$ klesne alespoò o~$p(u) - p(v) \over 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~zadefinovali, ¾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 \over K} = 1$. Nenasycená pøevedení potenciál nezvy¹ují. +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~zadefinovali, ¾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 \over 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 \over K$. Nasycených pøevedení se provede celkem~$\O(NM)$ a~ka¾dé zvý¹í potenciál takté¾ nejvý¹e o~$N \over K$. Celkem se~tedy~$\Phi$ zvý¹í nejvý¹e o -$${N \over K} \O(N^2) + {N \over K} \O(NM) = \O \left({N^3 \over K} + {N^2M \over K}\right).$$ +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 \over k$. Nasycených pøevedení se provede celkem~$\O(nm)$ a~ka¾dé zvý¹í potenciál takté¾ nejvý¹e o~$n \over k$. Celkem se~tedy~$\Phi$ zvý¹í nejvý¹e o +$${n \over k} \O(n^2) + {n \over k} \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 \over K} + {N^2M \over 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}$. +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 \over k} + {n^2m \over 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})$. +Proto v¹ech nenasycených pøevedení je $\O(n^2\sqrt{m})$. \qed \bye -- 2.39.5