4-goldberg/4-goldberg.tex

   1 \input lecnotes.tex\r
   2 \r
   3 \prednaska{4}{Goldgergùv algoritmus}{(zapsali R. Tupec, \r
   4 %J. Volec,\r
   5 J. Záloha)}\r
   6 \r
   7 \noindent\r
   8 Pøedstavíme si nový algoritmus pro hledání toku v síti, který se uká¾e stejnì dobrý jako\r
   9 {\I Dinicùv alogritmus} ($\O(mn^{2})$), a po nìkolika vylep¹eních bude i lep¹í.\r
  10 \r
  11 \s{Definice:} Funkce $f:E \rightarrow \bb{R}_{0}^{+}$ \r
  12 je {\I vlna} v síti ($V, E, z, s, c$), t.¾. $ \forall e \in E : f(e) \leq c(e) \wedge $ pro \r
  13 $ \forall v \ne z, v \ne s : f^{\Delta}(v) \geq 0 $.\r
  14 \r
  15 \s{Poznámka:} Funkce $f^{\Delta}(v)$ vrací pøebytek ve vrcholu \r
  16 $v$ : $$f^{\Delta}(v):=\sum_{(u,v) \in E}{f(u,v)} - \sum_{(v,u) \in E}{f(v,u)}$$\r
  17 Tok je vlna, kde $ f^{\Delta}(v) = 0 , \forall v \in V , v \ne z,s $.\r
  18 \r
  19 \noindent r(v,u)\r
  20 V algoritmu budeme provádìt dvì operace na vrcholech sítì. K tomu budeme potøebovat pøiøadit v¹em \r
  21 vrcholùm vý¹ky pomocí funkce $h : V \rightarrow \bb{N}$.\r
  22 \r
  23 \s{Operace:} pro $ (u,v) \in E$\r
  24 \r
  25 \algo\r
  26 \:{\I Pøevedení pøebytku} \r
  27 \r
  28 Pokud platí:\r
  29 \itemize\ibull\r
  30         \: $u : f^{\Delta}(v) > 0$\r
  31         \: $v : h(u) > h(v)$\r
  32         \: $r(u,v)>0$   \r
  33 \endlist\r
  34  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
  35 \r
  36 Øekneme, ¾e pøevedení je {\I nasycené}, pokud je po pøevodu rezerva na hranì $(u,v)$ nulová, tedy $r(u,v)=0$. \r
  37 Naopak pøevedení {\I nenasycené}, pokud po pøevodu $f^{\Delta}(v) = 0$. Pokud $r(u,v)=0 \wedge f^{\Delta}(v) = 0$\r
  38 budeme pøevedení pova¾ovat za {\I nasycené}.\r
  39 \r
  40 \:{\I Zvednutí vrcholu} $u$ \r
  41 \r
  42 Pokud v algoritmu narazíme na pøebytek, kterého se nelze pøevést, zvedneme vrchol $h(u):=h(u)+1$.  \r
  43 \endalgo\r
  44 \r
  45 \s{Algoritmus:} (Goldberg)\r
  46 \r
  47 \algo\r
  48 \:$h(*)\leftarrow 0, h(z)\leftarrow \bb{N}$.\r
  49 \:$f(*)\leftarrow 0, \forall u \in V, (z,u) \in E : f(u,v)\leftarrow c(z,u)$.\r
  50 \:Dokud $\exists u \in V, u \ne z, u \ne s, f^{\Delta}(u)>0$: \r
  51 \:Pokud $\exists (u,v) \in E, r(u,v)>0 \wedge h(u)>h(v)$, tak prevedeme pøebytek po (u,v).\r
  52 \:Jinak zvedneme $u$.\r
  53 \:Vrátíme tok $f$ jako výsledek.\r
  54 \endalgo\r
  55 \r
  56 \s{Poznámka:} Pokud v síti neexistují nìkteré zpìtné hrany, tak je tam pøidáme s nulovou kapacitou\r
  57 \r
  58 \noindent\r
  59 Následovat bude nìkolik lemmat a invariantù, jimi¾ se doká¾e správnost a èasová slo¾itost vý¹e popsaného\r
  60 agoritmu.\r
  61 \r
  62 \s{Invariant A:} Funkce $f:E \rightarrow \bb{R}$ vrácená algoritmem je vlna. Pro $\forall v \in V, h(v)$ neklesá a\r
  63 $h(z)=N, h(s)=0$.\r
  64 \r
  65 \proof\r
  66 Pro první èást invariantu si staèí rozmyslet, ¾e v~¾ádném kroku algoritmu nepøekroèíme kapacity hran a~nevytvoøíme\r
  67 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
  68 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
  69 \qed\r
  70 \r
  71 \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
  72 \r
  73 \proof\r
  74 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
  75 \qed \r
  76 \r
  77 \s{Lemma K (o korektnosti)} Kdy¾ se algorimus zastaví, vydá maxinální tok.\r
  78 \r
  79 \proof\r
  80 Vyjdìme z toho, ¾e $f$ je vlna a algorimus se mù¾e zastavit v tìchto pøípadech:\r
  81 \itemize\ibull\r
  82 \:ve vrcholech grafu nejsou ¾ádné pøebytky. Potom, ale $f$ je zároveò tok.\r
  83 \: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
  84 \endlist\r
  85 \qed\r
  86 \r
  87 \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
  88 \r
  89 \proof\r
  90 Mìjme nìjaký vrchol $v \in V(G)$ takový, ¾e  $f^{\Delta}(v) > 0$.\r
  91 Potom definujme mno¾inu $A := \{ u \in V(G) : \exists$ nenasycená cesta z $v$ do $u \}$.\r
  92 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
  93 \r
  94 \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
  95 $$\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
  96 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
  97 \qed\r
  98 \s{Invariant V (vý¹ka)} Pro $\forall v \in V$ platí $h(v)<=2N$.\r
  99 \r
 100 \proof\r
 101 Víme, ¾e poèet hran v cestì ze $z$ do $\forall v \in V$ je maximálnì $N-1$.\r
 102 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
 103 \qed\r
 104 \r
 105 \s{Lemma Z (poèet zvednutí)} Poèet v¹ech zvednutí je maximálnì $2N^{2}$.\r
 106 \r
 107 \proof\r
 108 Staèí si uvìdomit, ¾e ka¾dý vrchol zvednut maximálnì 2N-krát a vrcholù je N.\r
 109 \qed\r
 110 %\r
 111 %\s{Definice:} Nasycené pøevedení je pøevedení pøebytku z vrcholu hranou takové, ¾e tato hrana bude nasycena.\r
 112 %\r
 113 %\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
 114 \r
 115 \s{Lemma SY (sytá pøevedení)} Poìet v¹ech sytých pøevedení je maximálnì $NM$.\r
 116 \r
 117 \proof\r
 118 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
 119 \qed\r
 120 \r
 121 \r
 122 \r
 123 \end\r