4-goldberg/4-goldberg.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{4}{Goldgergùv algoritmus}{(zapsali R. Tupec,
   4 J. Volec,
   5 J. Záloha)}
   6
   7 \noindent
   8 Pøedstavíme si nový algoritmus pro hledání toku v síti, který se uká¾e stejnì dobrý jako
   9 {\I Dinicùv alogritmus} ($\O(mn^{2})$), a po nìkolika vylep¹eních bude i lep¹í.
  10
  11 \noindent
  12 Tento algoritmus narozdíl od {\I Dinicova algoritmu} zaèíná s pøebytky v sousedních vrcholech zdroje a sna¾í se jich zbavit pomocí pøevedení. Abychom se pøi pøi tomto pøevádìní nezacyklili, definujeme vý¹ku vrcholu a pøevádíme pouze z kopce.
  13
  14 \s{Definice:} Funkce $f:E \rightarrow \bb{R}_{0}^{+}$
  15 je {\I vlna} v síti ($V, E, z, s, c$), taková ¾e $ \forall (u,v) \in E : f(u,v) \leq c(u,v) $, kde $c(u,v)$ je kapacita hrany$(u,v)$, a $ \forall v \ne z, v \ne s : f^{\Delta}(v) \geq 0 $.
  16
  17 \s{Poznámka:} Funkci $f^{\Delta}(v)$ definujeme pro libovolnou funkci $f : E \rightarrow \bb R$
  18 : $$f^{\Delta}(v):=\sum_{(u,v) \in E}{f(u,v)} - \sum_{(v,u) \in E}{f(v,u)}$$
  19 Tok je vlna, kde $ f^{\Delta}(v) = 0 , \forall v \in V , v \ne z,s $.
  20
  21 \noindent
  22 Algoritmus pracuje se sítí rezerv. To je funkce $r(u, v), u,v \in V$ taková, ¾e pro $\forall (u, v) \in E: r(u,v)+f(u,v)=c(u,v)$. Pokud v síti neexistují nìkteré zpìtné hrany, tak je pøidáme s nulovou kapacitou.
  23
  24 \noindent
  25 V algoritmu budeme provádìt dvì operace na vrcholech sítì. K tomu budeme potøebovat pøiøadit v¹em
  26 vrcholùm vý¹ky pomocí funkce $h : V \rightarrow \bb{N}$.
  27
  28 \s{Operace:} pro $ (u,v) \in E$
  29
  30 \algo
  31 \:{\I Pøevedení pøebytku}
  32
  33 Pokud platí:
  34 \itemize\ibull
  35         \: $f^{\Delta}(u) > 0$
  36         \: $h(u) > h(v)$
  37         \: $r(u,v)>0$
  38 \endlist
  39  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$ .
  40
  41 Øekneme, ¾e pøevedení je {\I nasycené}, pokud je po pøevodu rezerva na hranì $(u,v)$ nulová, tedy $r(u,v)=0$.
  42 Naopak pøevedení {\I nenasycené}, pokud po pøevodu $f^{\Delta}(u) = 0$. Pokud $r(u,v)=0$ a $f^{\Delta}(u) = 0$
  43 budeme pøevedení pova¾ovat za {\I nasycené}.
  44
  45 \:{\I Zvednutí vrcholu} $u$
  46
  47 Pokud v algoritmu narazíme na pøebytek, který nelze pøevést, zvedneme vrchol $h(u):=h(u)+1$.
  48 \endalgo
  49
  50 \s{Algoritmus:} (Goldberg)
  51
  52 \algo
  53 \:$h(*)\leftarrow 0, h(z)\leftarrow N$.
  54 \:$f(*)\leftarrow 0, \forall u \in V, (z,u) \in E : f(z,u)\leftarrow c(z,u)$.
  55 \:Dokud $\exists u \in V \setminus \{u,v\}, f^{\Delta}(u)>0$:
  56 \::Pokud $\exists (u,v) \in E, r(u,v)>0$ a $h(u)>h(v)$, tak pøevedeme pøebytek po (u,v).
  57 \::Jinak zvedneme $u$.
  58 \:Vrátíme tok $f$ jako výsledek.
  59 \endalgo
  60
  61 %\s{Poznámka:} Pokud v síti neexistují nìkteré zpìtné hrany, tak je tam pøidáme s nulovou kapacitou
  62
  63 \noindent
  64 Následovat bude nìkolik lemmat a invariantù, jimi¾ se doká¾e správnost a èasová slo¾itost vý¹e popsaného
  65 agoritmu.
  66
  67 \s{Invariant A:} Funkce $f:E \rightarrow \bb{R}$, se kterou algoritmus pracuje, je vlna. $\forall v \in V$: $h(v)$ neklesá a $h(z)=n$, $h(s)=0$.
  68
  69 \proof
  70 Pro první èást invariantu si staèí rozmyslet, ¾e v~¾ádném kroku algoritmu nepøekroèíme kapacity hran a~nevytvoøíme záporný pøebytek. $\forall v \in V \setminus \{z,s\}$ skuteènì vý¹ku pouze zvy¹ujeme a z podmínky v tøetím kroku algoritmu vyplývá, ¾e nás pøebytky v $z$ a $s$ v podstatì nezajímají, tudí¾ ani nemìníme jejich vý¹ku.
  71 \qed
  72
  73 \s{Invariant S (o spádu):} $\forall (u,v) \in E, r(u,v)>0 : h(u) \leq h(v)+1$. Tedy neexistuje hrana se spádem vìt¹ím ne¾ jedna a nenulovou rezervou.
  74
  75 \proof
  76 Podívejme se, kdy by mohla vzniknout nenasycená hrana se spádem vìt¹ím ne¾ 1. V druhé fázi algoritmu k tomu nedojde. Pokud ji¾ existuje vrchol $v$ s kladným pøebytkem, dále existuje nenasycená hrana $(v,u)$ a $h(v)=h(u)+1$, vrchol $v$ algoritmus nezvedá a rovnou pøebytek posílá po této hranì. Uva¾me tedy je¹tì druhý pøípad, kdy existuje nasycená hrana $(u,v)$ se spádem vìt¹ím ne¾ jedna a tuto hranu se pokusíme odsytit. Jen¾e to také nejde, proto¾e kdybychom cokoli poslali proti smìru této hrany, bude to proti smìru funkce $h$, ale to nejde.
  77 \qed
  78
  79 \s{Lemma K (o korektnosti):} Kdy¾ se algorimus zastaví, vydá maximální tok $f$.
  80
  81 \proof
  82 Nejprve uká¾eme, ¾e $f$ je tok a pak jeho maximalitu. Vyjdìme z toho, ¾e $f$ je vlna a algorimus se mù¾e zastavit jen pokud nastanou oba tyto pøípady souèasnì:
  83 \itemize\ibull
  84 \:ve vrcholech grafu nejsou ¾ádné pøebytky. Potom, ale $f$ je zároveò tok.
  85 \:pokud neexistuje nenasycená cesta $P$ ze zdroje do stoku. O té víme, ¾e má maximálnì $n-1$ hran. Zároveò by v¹ak musela mít spád $n$. Ale to znamená, ¾e existuje hrana $(u,v)$, pro kterou platí $h(u,v)>=2$, co¾ je spor s Invariantem S.
  86 \endlist
  87 \qed
  88
  89 \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$.
  90
  91 \proof
  92 Mìjme nìjaký vrchol $v \in V(G)$ takový, ¾e $f^{\Delta}(v) > 0$.
  93 Potom definujme mno¾inu $A := \{ u \in V(G) : \exists$ nenasycená cesta z $v$ do $u \}$.
  94 Mìjme vrcholy $a \in A$ a $b \in V(G) \setminus A$ takové, ¾e $(b,a)\in E$. O nich víme, ¾e $f(b, a)=0$, proto¾e pokud by tomu tak nebylo, muselo by platit $r(a, b)>0$, a tedy $b$ patøí do mno¾iny $A$.
  95
  96 \noindent Seètìme pøebytky ve v¹ech vrcholech $A$. Proto¾e pøebytek ka¾dého vrcholu se spoèítá jako souèet tokù do nìj vstupujících minus souèet tokù z nìj vystupujících a v¹echny hrany, jejich¾ oba vrcholy le¾í v $A$, se jedenkrát pøiètou a jedenkrát odeètou, platí:
  97 $$\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)$$
  98 Proto¾e v¹ak do $A$ nic neteèe, nebo» obsahuje zdroj (pokud není izolovaný, existují nenasycené zpìtné hrany), tento výraz musí být men¹í nebo roven nule. Odtud vyplývá, ¾e pokud nìco odtéká ven z $A$, nebo $A$ obsahuje $s$, pak $\exists u \in A, f^{\Delta}(u)<0$. Toto $u$ v¹ak musí být zdroj, proto¾e v¹echny ostatní vrcholy mají kladný pøebytek.
  99 \qed
 100 \s{Invariant V (vý¹ka):} $\forall v \in V$ platí $h(v)\le 2n$.
 101
 102 \proof
 103 Víme, ¾e poèet hran v cestì ze $z$ do $\forall v \in V$ je maximálnì $n-1$.
 104 Pokud by existoval vrchol $v$ s vý¹kou $h(v)>2n$, musel by být zvednut alespoò $2n$-krát. To ale znamená, ¾e by po $2n-1$ zvednutích musel mít stále pøebytek. Pokud tento pøebytek nelze pøevést do ¾ádného jiného vrcholu ${u} \in E$, musí platit $h(v)\le h({u})$ a tedy $v$ bude zvednut po $2n$-té. To ale znamená, ¾e by platilo $h(v)-h(z)=n$. Dále víme z Invariantu C, ¾e existuje nenasycená cesta z $v$ do $z$. Potom ale na cestì ze $z$ do $v$ existuje hrana se spádem vìt¹ím ne¾ 1, a to je spor s Invariantem S.
 105 \qed
 106
 107 \s{Lemma Z (poèet zvednutí):} Poèet v¹ech zvednutí je maximálnì $2n^{2}$.
 108
 109 \proof
 110 Staèí si uvìdomit, ¾e ka¾dý vrchol mù¾eme zvednout maximálnì $2n$-krát a vrcholù je $n$.
 111 \qed
 112 %
 113 %\s{Definice:} Nasycené pøevedení je pøevedení pøebytku z vrcholu hranou takové, ¾e tato hrana bude nasycena.
 114 %
 115 %\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.
 116
 117 \s{Lemma SY (sytá pøevedení):} Poèet v¹ech sytých pøevedení je maximálnì $NM$.
 118
 119 \proof
 120 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. Pro odsycení hrany se musí otoèit 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$.
 121 \qed
 122
 123 \s{Lemma N (nenasycená pøevedení):} Poèet v¹ech nenasycených pøevedení je $\O(N^2M)$.
 124
 125 \proof
 126 Dùkaz provedeme pomocí potenciálu - nadefinujme si následující potenciál (funkci):
 127 $$ \psi = \sum_{ v: f^{\Delta}(v) > 0, v \ne z,s} h(v) $$ % !todo! dvouradkovy dolni index sumy
 128 Nyní se podívejme, jak se ná¹ potenciál bìhem algoritmu vyvíjí a jaké má vlastnosti:
 129 \itemize\ibull
 130 \: Bìhem celého algoritmu je $ \psi \ge 0 $, nebo» je souètem nezáporných èlenù.
 131 \: Na poèátku je $ \psi = 0 $.
 132 \: Zvednutí vrcholu zvý¹í potencíál o $1$. Ji¾ víme, ¾e za~celý prùbìh algoritmu je zvednutí maximálnì $2N^2$, proto zvedáním vrcholù zvý¹íme potenciál nejvý¹e o~$2N^2$.
 133 \: Nasycené pøevedení zvý¹í potenciál nejvý¹e o~$2N$, nebo» èistì nasyceným pøevedením mù¾eme potenciál zvý¹it a¾ o~$2N$, pokud nejde o~èistì nasycené pøevedení, potenciál se dokonce o~$1$ sní¾í. Za~celý prùbìh tak dojde k~maximálnì $NM$ takovýchto pøevedení, díky nim¾ se potenciál zvý¹í maximálnì o~$2N^2M$.
 134 \: Koneènì kdy¾ pøevadím po~hranì $(u,v)$ nenasycenì, tak od~potenciálu urèitì odeètu vý¹ku vrcholu $u$ a mo¾ná pøiètu vý¹ku vrcholu $v$. Jen¾e $h(v) = h(u) - 1$, proto nenasycené pøevedení potenciál v¾dy sní¾í alespoò o~$1$.
 135 \endlist
 136 Rozebrali jsme tedy v¹echny události, které mohou v~prùbìhu algoritmu nastat, proto z~uvedených vlastností na¹eho potenciálu $\psi$ vidíme, ¾e poèet nenasycených pøevedení mù¾e být nejvý¹e $2N^2 + 2N^2M$, co¾ je $\O(N^2M)$.
 137 \qed
 138
 139 \s{Vìta:} Goldbergùv algoritmus najde maximální tok v~èase $\O(N^2M)$.
 140
 141 \proof
 142 Z~lemmatu Z vyplývá, ¾e celkový poèet zvednutí je maximálnì $2N^2$, pøièem¾ ka¾dé zvednutí jsme schopni provést v~èase $\O(N)$. Tak¾e dohromady pro~zvedání spotøebujeme èas $\O(N^3)$, co¾ je pro souvislé sítì urèitì $\O(N^2M)$. Z~lemmatu SY prozmìnu vyplývá, ¾e nasycená pøevedení nás stojí $\O(NM)$, a na~závìr z~lemmatu N dostáváme èasovou slo¾itost $\O(N^2M)$ pro~pøevedení nenasycená. Proto celková slo¾itost algoritmu je $\O(N^2M)$.
 143 \qed
 144
 145 \s{Implementace:}
 146 Budeme si pamatovat seznam $P$ v¹ech vrcholù $v \ne z,s$ takových, ¾e $f^{\Delta}(v) > 0$. Kdy¾ mìníme pøebytek nìjakeho vrcholu, tak mù¾eme ná¹ seznam v~konstantním èase zaktualizovat (napø. tak, ¾e si ka¾dý vrchol pamatuje pozici, na~které v~seznamu je). A v~konstantním èase také umíme odpovìdìt, zda existuje nìjaký vrchol s~pøebytkem. Dále si $\forall v \in V$ budeme pamatovat $L(v) := $ seznam $(v,u) \in E$ takových, ¾e $r(v,u) > 0$ a $h(u) < h(v)$. Díky tomu mù¾eme pøistupovat k~patøièným sousedùm $v$ v~èase $\O(1)$, stejnì jako provádìt operace pøidání do~$L(v)$ resp. smazání v~nìm. Pøi~pøevádìní nìjakého vrcholu $v$ vyhodíme $v$ nejvý¹e jednou, a to opìt v~èase $\O(1)$. A koneènì zvedání vrcholu nám zabere èas $\O(N)$.
 147
 148 Nabízí se otázka, jak algoritmus zrychlit? Následující úprava $3.$ kroku algoritmu sní¾í poèet nenasycených pøevedení - Dokud $\exists u \in V \setminus \{u,v\}, f^{\Delta}(u)>0, h(u)$ je maximální: - co¾ je dùsledek následujícího lemmatu.
 149
 150 \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)$.
 151
 152 \bye