4-goldberg/4-goldberg.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{4}{Goldbergù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í 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¹í.
   9
  10 \noindent %todo pøeformulovat:BEGIN
  11 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í. Abychom se pøi~tomto pøevádìní nezacyklili, definujeme vý¹ku vrcholu a pøevádíme pouze s~kopce.
  12 %todo pøeformulovat:END
  13
  14 \s{Definice:} Funkce $f:E \rightarrow {\bb R}_{0}^{+}$
  15 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 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
  16  $$f^{\Delta}(v):=\sum_{uv \in E}{f(uv)} - \sum_{vu \in E}{f(vu)}.$$
  17 Tok je vlna, kde $ f^{\Delta}(v) = 0 , \forall v \ne z,s $.
  18
  19 \noindent
  20 Algoritmus pou¾ívá sít rezerv, kterou jsme nadefinovali ji¾ v~pøedchozí kapitole vìnované Dinicovi.
  21
  22 \noindent
  23 Dále budeme provádìt dvì operace na~vrcholech sítì. K~tomu budeme potøebovat pøiøadit v¹em vrcholùm vý¹ky pomocí funkce $h : V \rightarrow \bb{N}$.
  24
  25 \s{Operace:} Pro~hranu $uv \in E$ definujme {\I pøevedení pøebytku}:
  26
  27 \noindent
  28 Pokud platí, ¾e
  29 \numlist \ndotted
  30         \:ve~vrcholu $u$ je nenulový pøebytek, tj. $f^{\Delta}(u) > 0$,
  31         \:vrchol $u$ je vý¹ ne¾ vrchol $v$, tj. $h(u) > h(v)$, a
  32         \:hrana $uv$ má nenulovou rezervu, tj. $r(uv)>0$,
  33 \endlist
  34 \noindent pøevedeme tok o~velikosti $\delta:=\min(f^{\Delta}(u),r(uv))$ z~$u$ do~$v$ tímto zpùsobem:
  35 \numlist \ndotted
  36   \:$f^{\Delta}(u):=f^{\Delta}(u)-\delta$ a $f^{\Delta}(v):=f^{\Delta}(v)+\delta$,
  37   \:$r(uv):=r(uv)-\delta$ a $r(vu)=r(vu)+\delta$.
  38 \endlist
  39 Øekneme, ¾e pøevedení je {\I nasycené}, pokud je po~pøevodu rezerva na~hranì $uv$ nulová, tedy $r(uv)=0$.
  40 Naopak pøevedení {\I nenasycené}, pokud po~pøevodu $f^{\Delta}(u) = 0$. Pokud $r(uv)=0$ a $f^{\Delta}(u) = 0$,
  41 budeme pøevedení pova¾ovat za~{\I nasycené}.
  42
  43 \s{Operace:} Pro~vrchol $u \in V$ definujme {\I zvednutí vrcholu}:
  44 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~$1$, tj. $h(u)=h(u)+1$.
  45
  46 \s{Algoritmus:} (Goldbergùv)
  47
  48 \algo
  49 \:$\forall v \in V: h(v)\leftarrow 0$ (v¹em vrcholùm nastavíme poèáteèní vý¹ku na~$0$).
  50 \:$h(z)\leftarrow N$ (zdroj zvedneme do~vý¹ky $N$).
  51 \:$\forall e \in E: f(e)\leftarrow 0$ (po~hranách na~poèátku nenecháme protékat nic).
  52 \:$\forall zu \in E : f(zu)\leftarrow c(zu)$ (ze~zdroje pustíme maximální mo¾nou vlnu).
  53 \:Dokud $\exists u \in V \setminus \{z,s\}, f^{\Delta}(u)>0$:
  54 \::Pokud $\exists uv \in E, r(uv)>0$ a $h(u)>h(v)$, pøevedeme pøebytek po~hranì $uv$.
  55 \::V~opaèném pøípadì zvedneme $u$.
  56 \:Vrátíme tok $f$ jako výsledek.
  57 \endalgo
  58
  59 \noindent
  60 Následovat bude nìkolik lemmat a invariantù, jimi¾ doká¾eme správnost a èasovou slo¾itost vý¹e popsaného algoritmu.
  61
  62 \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$.
  63
  64 \proof
  65 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~tøetí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í.
  66 \qed
  67
  68 \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$.
  69
  70 \proof %todo pøeformulovat:BEGIN
  71 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.
  72 \qed %todo pøeformulovat:END
  73
  74 \s{Lemma K (o~Korektnosti):} Kdy¾ se algoritmus zastaví, je $f$ maximální tok.
  75
  76 \proof
  77 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ì:
  78 \itemize\ibull
  79 \:Ve~vrcholech grafu nejsou ¾ádné pøebytky (mimo~*$z$ a $s$). Potom ale $f$ je zároveò tok. %todo check ? mimo~ ?
  80 \: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 $uv$, pro~kterou platí $h(uv) \ge 2$, co¾ je spor s~Invariantem~S.
  81 \qeditem
  82 \endlist
  83
  84 \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$.
  85
  86 \proof
  87 Mìjme nìjaký vrchol $v \in V$ takový, ¾e $f^{\Delta}(v) > 0$.
  88 Potom definujme mno¾inu $A := \{ u \in V : \exists$ nenasycená cesta z~$v$ do~$u \}$.
  89 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$.
  90
  91 \noindent 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 jedenkrát pøiètou a jedenkrát odeètou, platí:
  92  $$\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).$$
  93 %todo pøeformulovat:BEGIN
  94 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.
  95 \qed %todo pøeformulovat:END
  96 \s{Invariant V (Vý¹ka):} $\forall v \in V$ platí $h(v)\le 2n$.
  97
  98 \proof %todo pøeformulovat:BEGIN
  99 Víme, ¾e poèet hran v~cestì ze~$z$ do~$\forall v \in V$ je maximálnì $n-1$.
 100 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.
 101 \qed %todo pøeformulovat:END
 102
 103 \s{Lemma Z (poèet Zvednutí):} Poèet v¹ech zvednutí je maximálnì $2n^{2}$.
 104
 105 \proof
 106 Staèí si uvìdomit, ¾e ka¾dý vrchol mù¾eme zvednout maximálnì $2n$-krát a vrcholù je $n$.
 107 \qed
 108
 109 \s{Lemma S (naSycená pøevedení):} Poèet v¹ech nasycených pøevedení je maximálnì $NM$.
 110
 111 \proof
 112 Mìjme hranu $uv \in E$, kterou jsme právì nasytili. Tedy platí $h(v)<h(u)$ a zároveò $r(uv)=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 hranami $uv$ proto probìhla minimálnì dvì zvednutí vrcholu $u$. Algoritmus nikdy vý¹ku vrcholu nesni¾uje, a tedy poèet v¹ech nasycených pøevedení je skuteènì $NM$.
 113 \qed
 114
 115 \s{Lemma N (Nenasycená pøevedení):} Poèet v¹ech nenasycených pøevedení je $\O(N^2M)$.
 116
 117 \proof
 118 Dùkaz provedeme pomocí potenciálu --- nadefinujme si následující potenciál (funkci):
 119  $$ \psi = \sum_{\scriptstyle{v: f^{\Delta}(v) > 0} \atop \scriptstyle{v \ne z,s}} h(v). $$
 120 Nyní se podívejme, jak se ná¹ potenciál bìhem algoritmu vyvíjí a jaké má vlastnosti:
 121 \itemize\ibull
 122 \:Bìhem celého algoritmu je $ \psi \ge 0 $, nebo» je souètem nezáporných èlenù.
 123 \:Na poèátku je $ \psi = 0 $.
 124 \:Zvednutí vrcholu zvý¹í $\psi$ o $1$. 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$.
 125 \: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~$1$ 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$.
 126 \: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~$1$.
 127 \endlist
 128 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)$.
 129 \qed
 130
 131 \s{Implementace:}
 132 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. 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)$. %todo ? cotoje ?
 133 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 nejvý¹e $N-1$, porovnat vý¹ky a pøípadnì odebrat $uv$ z~seznamu $L(u)$ resp. pøidat do $L(v)$. Abysme 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)$.
 134
 135 \s{Vìta:} Goldbergùv algoritmus najde maximální tok v~èase $\O(N^2M)$.
 136
 137 \proof
 138 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)$.
 139 \qed %todo ? pro zmìnu vs. prozmenu ?
 140
 141 Dokázali jsme, ¾e algoritmus má èasovou slo¾itost $\O(N^2M)$ pro libovolnou posloupnost zvedání a pøevádìni. Nabízí se otázka, zda není mo¾né algoritmus 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í¾í.
 142
 143 \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)$.
 144
 145 \proof
 146 Viz. pøí¹tí pøedná¹ka.
 147 \bye