1-toky/1-toky.tex

   1 %%%%%%%%%%%%%%%%%%%%%%%\r
   2 % Zápisek prvého semináøe z grafových algoritmù - ze dne ? 7.6.2006 ?\r
   3 % Téma Toky v sítích a zejména Ford-Fulkersonùv algoritmus.\r
   4 % Zapsal Radovan ©esták - radovan.sestak@gmail.com\r
   5 %%%%%%%%%%%%%%%%%%%%%%\r
   6 \r
   7 \input ../sgr.tex\r
   8 \r
   9 \prednaska{1}{Toky v sítích a FF algoritmus}{zapsal Radovan ©esták}\r
  10 \r
  11 \h{Toky v sítích}\r
  12 \r
  13 V následujícím odstavci uká¾eme nìkolik tvrzení o sítích, které je\r
  14 mo¾né si pøedstavit jako sí» potrubí køí¾ící se v uzlech. Vrchol\r
  15 z kterého se kapalina ¹íøí nazveme zdroj a vrchol kde odtéká stok. Pro\r
  16 ostatní vrcholy platí, ¾e objem kapaliny pøitékající se rovná objemu\r
  17 kapaliny odtékající. Toto pravidlo, které pochází z teorie o elektrických obvodech,\r
  18 se zvykne nazývat Kirchhoffùv zákon. Hledání maximálního toku je duální úlohou k hledání \r
  19 minimálního øezu. Ford-Fulkersonùv(FF) algoritmus, který bude popsán ní¾e je základním \r
  20 algoritmem pro hledání tokù. Na úlohu hledání maximálního toku se dají pøevést mnohé\r
  21 grafové problémy a i proto existuje mnoho algoritmù a nìkteré z nich jsou pouze modifikace \r
  22 základního FF algoritmu. V dal¹í pøedná¹ce najdete Dinitzùv algoritmus pro tenhle problém.\r
  23 \r
  24 \r
  25 \s{Definice:}\r
  26 \r
  27 \itemize\ibull\r
  28 \:sí»: $N=(V,E,s,t,w)$ kde $V$ je mno¾ina vrcholù, $E\subseteq V\times V$,\r
  29 $s\in V$ je zdroj, $t\in V$ je stok, $w:\, E\rightarrow{R}^{+}$ jsou kapacity hran\r
  30 \:tok: $f:\, E\rightarrow{R}^{+}$kde $\forall e\in E\, f(e)\leq w(e)$ a\r
  31 $\forall v\in V,\, v\neq s,\, v\neq t\,\,\sum_{uv\in E}f(uv)=\sum_{vw\in E}f(vw)$\r
  32 \:velikost toku: $\|f\|=\sum_{sv\in E}f(sv)-\sum_{vs\in E}f(vs)$ kde $s$ je zdroj\r
  33 \:øez: $st$-øez je mno¾ina hran $C\subseteq E$ taková, ¾e v grafu $(V,\, E\setminus C)$ neexistuje\r
  34 cesta z s do t\r
  35 \:separátor: $st$-separátor je mno¾ina vrcholù $S\subseteq V$ taková, ¾e v grafu\r
  36 $(V\setminus S,\, E\cap(V\setminus S)\times(V\backslash S))$ neexistuje\r
  37 cesta z s do t\r
  38 \:velikost øezu: $\|c\|=\sum_{e\in c}w(e)$ je velikost øezu\r
  39 \endlist\r
  40 \r
  41 \figure{graf.eps}{Pøíklad orientovaného grafu ze zvoleným zdrojem a stokem.}{0.4\hsize}\r
  42 \r
  43 \s{Vìta(Ford-Fulkerson) o souvislosti tokù a øezù}\r
  44 Nech» $N=(V,E,s,t,w)$ je sí», $F$ je mno¾ina pøípustných tokù pro tuto sí» a $C$ je\r
  45 mno¾ina øezù oddìlující zdroj od stoku. Pak \r
  46 $$max_{f\in F}|f|=min_{c\in C}\|c\|$$. \r
  47 Vìta platí pro v¹echny výbìry zdrojù a stokù $\forall s,t\in V, s\neq t$ nech» $st-F$ je mno¾ina\r
  48 v¹ech tokù ze zdroje $s$ do stoku $t$ a $st-C$ je mno¾ina v¹ech øezù oddìlujících $s$ od $t$. Pak\r
  49 $$max_{f\in st-F}\|f\|=min_{c\in st-C}\|c\|$$\r
  50 pro graf $G=(V,E,w)$.\r
  51 \r
  52 \s{Dùkaz vìty:}\r
  53 \r
  54 \s{$max_{f}\|f\|\leq min_{c}\|c\|$:} Vìznìme libovolný øez oddìlující zdroj od stoku $c$ a uva¾me\r
  55 graf $G'=(V,E\setminus c)$, který vznikl odebráním hran nacházejících se v øezu. Buï $S$ mno¾ina \r
  56 vrcholù dosa¾itelných ze zdroje v $G'$.\r
  57 Pro libovolnej tok  $f$ platí: \r
  58 \r
  59 $$\|f\| =  \sum_{uv\in E, u\in S, v\notin S}f(uv) - \sum_{uv\in E, u\in S, v\notin S}f(vu)$$\r
  60 velikost toku je rovna rozdílu velikostí tokù pøes hrany opou¹tìjící $S$ a pøicházející do $S$.\r
  61 $$\|f\| = \sum_{u\in V}f(su) - \sum_{u\in V}f(us)$$\r
  62 proto¾e se tok zachovává ve v¹ech vrcholech partity $S$ kromì $s$ dostáváme\r
  63 $$= \sum_{v\in S}(\sum_{u\in V}f(uv)-\sum_{u\in V}f(vu))$$\r
  64 $f(uv)$ pro $u,v\in S$ jsme jednou pøièítali a jednou odèítali\r
  65 $$= \sum_{uv\in E, u\in S, v\notin S}f(uv) - \sum_{uv\in E, u\in S, v\notin S}f(vu)$$\r
  66 \r
  67 Teï si u¾ staèí jenom uvìdomit, ¾e \r
  68 $$\|f\| = \sum_{uv\in E, u\in S, v\notin S}f(uv)- \sum_{uv\in E, u\in S, v\notin S}f(vu) \leq \sum_{uv\in E, u\in S, v\notin S}f(uv)\r
  69 \leq \sum_{uv\in E, u\in S, v\notin S}w(uv) \leq \|c\|$$\r
  70 Poslední nerovnost je dùsledkem toho, ¾e øez obsahuje v¹echny hrany opou¹tìjící $S$.\r
  71 \r
  72 $max_{f}|f|\geq min_{c}|c|$: dùkaz plyne z korektnosti\r
  73 Ford-Fulkersonova algoritmu viz. algoritmus dále\r
  74 \r
  75 \s{Dùsledek:}Pro ka¾dou sí» s celoèíselnými kapacitami je její maximální tok celoèíselný.\r
  76 \r
  77 \h{Maximální párování v bipartitním grafu}\r
  78 Maximální párování v bipartitním grafu $(A\cup B,E)$ se dá najít\r
  79 pomocí maximálního toku v síti $(A\cup B\cup s\cup t,E',s,t,w)$ kde\r
  80 $w(e)=1$ a $E'=\{ uv\| u\in A, uv\in E\} \cup \{su\| u\in A\} \cup\{ut\| u\in B\}$ a\r
  81 obdobnì mù¾eme nalézt minimální vrcholové pokrytí.\r
  82 \r
  83 \figure{bip-graf.eps}{Bipartitní graf pro který hledáme maximální párování.}{0.2\hsize}\r
  84 \figure{bip-tok.eps}{Sí» v které najdeme maximální tok.}{0.3\hsize}\r
  85 \r
  86 \s{Definice}\r
  87 \itemize\ibull\r
  88 \:neorientovaný graf G je vrcholovì k-souvislý $\Leftrightarrow$ G má alespoò\r
  89 k+1 vrcholù a neexistuje separátor s ménì ne¾ k vrcholy\r
  90 \:neorientovaný graf G je hranovì k-souvislý $\Leftrightarrow$ G má alespoò k+1 vrcholù\r
  91 a neexistuje øez s ménì ne¾ k hranami\r
  92 \:orientovaný graf je silnì souvislý $\Leftrightarrow$ existuje orientovaná cesta mezi\r
  93 v¹emi vrcholy v obou smìrech\r
  94 \:cirkulace je nulový tok t.j.  $\forall v\in V, \sum f(uv)=\sum f(vu)$\r
  95 \endlist\r
  96 \r
  97 \s{Vìta:}(Menger) o souvislosti existencí disjunktních cest a souvislostí\r
  98 grafù\r
  99 \r
 100 buï $G$ neorientovaný graf, pak:\r
 101 \itemize\ibull\r
 102 \:$G$ je vrcholovì k-souvislý $\Leftrightarrow$$\forall v,w\in V\,\exists$\r
 103 k vrcholovì disjunktních cest z $v$ do $w$\r
 104 \:$G$ je hranovì k-souvislý $\Leftrightarrow$$\forall v,w\in V\,\exists$\r
 105 k hranovì disjunktních cest z $v$ do $w$\r
 106 \:kdy¾ $u$ a $v$ jsou nesousední vrcholy v $G$ pak maximální poèet vrcholovì disjunktních\r
 107 cest mezi $u$ a $v$ se rovná minimálnímu poètu vrcholù z $G-{u,v}$ kterých odebrání oddìlí\r
 108 $u$ od $v$ \r
 109 \:kdy¾ $u$ a $v$ jsou vrcholy v $G$ pak maximální poèet hranovì disjunktních\r
 110 cest mezi $u$ a $v$ se rovná minimálnímu poètu hran, kterých odebrání oddìlí $u$ od $v$\r
 111 \endlist\r
 112 buï $G$ orientovaný graf, pak:\r
 113 \itemize\ibull\r
 114 \:kdy¾ $u$ a $v$ jsou vrcholy $G$, $uv\notin E(G)$ pak maximální poèet vrcholovì disjunktních\r
 115 cest z $u$ do $v$ je rovný minimálnímu poètu vrcholù z $G-{u,v}$ kterých odebrání oddìlí $u$ od $v$\r
 116 \:kdy¾ $u$ a $v$ jsou vrcholy $G$ pak maximální poèet hranovì disjunktních cest z $u$ do $v$ je\r
 117 rovný minimálnímu poètu hran, kterých odebrání oddìlí $u$ od $v$\r
 118 \endlist\r
 119 \r
 120 Vrcholová i hranová souvislost grafu se dá zjistit pomocí maximálního\r
 121 toku. Pro hranovou souvislost pøímo zjistíme maximální tok pro ka¾dou\r
 122 dvojici vrcholù (volba zdroje a stoku). V pøípadì neorientovaného grafu vyrobíme orientovaný graf tak, ¾e ka¾dou\r
 123 neorientovanou hranu nahradíme orientovanými v obou smìrech. Pro vrcholovou souvislost\r
 124 navíc musíme ka¾dý vrchol nahradit dvìma novými a spojit je hranou\r
 125 v obou smìrech (pod-rozdìlení vrcholu). Kapacity hran volíme 1.\r
 126 Pro nalezení tìchto cest staèí v¾dy v síti odebírat postupnì cestu\r
 127 z $s$ do $t$. Odebrání jedné cesty sní¾í tok o jedna a tedy cest\r
 128 musíme nalézt $k$.\r
 129 \figure{vrchol.eps}{Vrchol který chceme pod-rozdìlit.}{0.1\hsize}\r
 130 \figure{podrozdeleni.eps}{Výsledek pod-rozdìlení vrcholu.}{0.15\hsize}\r
 131 \r
 132 \r
 133 \s{Ford-Fulkersonùv algoritmus}\r
 134 Algoritmus nepracuje pøímo s kapacitami a s toky pøes hrany, ale s rezervami\r
 135 tìchto hran. Funkce rezerv definujeme jako $r(uv)\equiv w(uv)-f(uv)+f(vu)$.\r
 136 Jestli $uv\notin E(G)$ pak $w(uv)=0$.\r
 137 Kdy¾ zmen¹ujeme rezervu hrany tak o stejnou hodnotu zvý¹íme hodnotu\r
 138 rezervy opaèné hrany. Dále pak FF cesta, je cesta pro kterou má ka¾dá hrana kladnou rezervu.\r
 139 \r
 140 \algo\r
 141 \:nastav rezervy pro nulový tok na v¹ech hranách (rezervy se rovnají kapacitám)\r
 142 \:while $\exists$FF cesta z $s$ do $t$\r
 143 \::buï $p$ FF cesta z $s$ do $t$\r
 144 \::zvìt¹i tok zmen¹ením rezerv, o $m=min_{uv\in p}r(uv)$ \r
 145 \:end while\r
 146 \:spoèti tok z rezerv\r
 147 \endalgo\r
 148 \r
 149 Pro dùkaz korektnosti algoritmu uva¾ mno¾inu $X=\{ v,\,\exists$FF\r
 150 cesta z $s$ do $v\}$ po dobìhnutí algoritmu. Proto¾e neexistuje FF cesta z $s$ do $t$, $t\notin X$.\r
 151 Pak mno¾iny $X$ a $V\setminus X$ urèují øez tvoøený hranami spojujícími\r
 152 vrcholy z rùzných mno¾in $c=\{uv: uv\in E, u\in X, v\in V\setminus X\}$. V¹echny hrany $uv\in c$\r
 153 mají nulovou rezervu, nebo» jinak by se dala prodlou¾it FF cesta do vrcholu z $V\setminus X$. Tak¾e velikost\r
 154 toku se rovná souètu kapacit hran z $X$ do $V\setminus X$ (tohle tvrzení jsme dokázali pøi dùkazu opaèné implikace\r
 155 FF vìty). Souèasnì tyhle hrany tvoøí $st$-øez, kterého kapacita je rovna velikosti toku. Na¹li jsme tedy øez, \r
 156 kterého velikost se rovná velikosti pøípustného toku a tím je dùkaz FF vìty ukonèen. \r
 157 \r
 158 Kdy¾ máme celoèíselné kapacity hran tak v ka¾dém kroku se tok zvìt¹í\r
 159 alespoò o jedna a maximální tok je z hora omezen, napøíklad souètem\r
 160 v¹ech kapacit hran. Pro racionální kapacity staèí vynásobit kapacity\r
 161 a dostaneme celoèíselné.  Z toho plyne koneènost FF algoritmu pro hrany s racionálními kapacitami.\r
 162 Táto varianta FF algoritmu není obecnì koneèná pøi reálných kapacitách. Volíme-li ov¹em zlep¹ující cestu, která\r
 163 má maximální minimum pøes rezervy tak je FF algoritmus koneèný i pro reálné kapacity hran.\r
 164 \r
 165 Pro FF algoritmus s jednotkovými kapacitami a vyu¾itím BFS (procházení\r
 166 do ¹íøky) na hledání FF cest je èasová slo¾itost algoritmu $O(n.m)$.\r
 167 Edmunds s Karpem dokázali, ¾e pøi volbì nejkrat¹í cesty je èasová\r
 168 slo¾itost v obecném pøípadì $O(n.m^{2})$.\r
 169 \r
 170 \bye\r