2-toky/2-toky.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{2}{Toky v sítích}{}
   4
   5 \h{Motivaèní úlohy}
   6
   7 Pøedstavme si, ¾e~by v~budovì fakulty na~Malé Stranì existoval èajovod, který
   8 by rozvádìl èaj do~ka¾dé uèebny. Znázornìme si to orientovaným grafem, v~nìm¾
   9 jeden významný vrchol pøedstavuje èajovar a~druhý uèebnu, ve~které sedíme.
  10 Hrany mezi vrcholy pak pøedstavují vìtvící se trubky, které mají èaj rozvádìt.
  11 Jak dopravit co nejvíce èaje do~dané uèebny?
  12
  13 \figure{toky01.eps}{Èajovod}{2in}
  14
  15 Jiným pøíkladem mù¾e být poèítaèová sí» na~pøenos dat, která se sestává z~pøenosových linek
  16 spojených pomocí routerù. Data se sice obvykle pøená¹ejí po~paketech, ale to
  17 mù¾eme pøi dne¹ních rychlostech pøenosu zanedbat a pova¾ovat data za spojitá.
  18 Jak pøená¹et data mezi dvìma poèítaèi v~síti co nejrychleji?
  19
  20 \h{Toky v~sítích}
  21
  22 \s{Definice:} {\I Sí»} je uspoøádaná pìtice $(V,E,z,s,c)$, pro ní¾ platí:
  23 \itemize\ibull
  24 \:$(V,E)$ je orientovaný graf.
  25 \:$c:E\to{\bb R}_{0}^{+}$ je {\I kapacita} hran.
  26 \:$z,s \in V$ jsou dva vrcholy grafu, kterým øíkáme {\I zdroj} a~{\I stok} (spotøebiè).
  27 \:Graf je symetrický, tedy $\forall u,v \in V: uv \in E \Leftrightarrow vu \in E$\foot{%
  28 Nebude-li hrozit nedorozumìní, budeme hranu z~vrcholu~$u$ do vrcholu~$v$
  29 znaèit $uv$ namísto formálnìj¹ího, ale ménì pøehledného $(u,v)$. Podobnì pro neorientovaný
  30 pí¹eme $uv$ namísto $\{u,v\}$.}
  31 (tuto podmínku si~mù¾eme zvolit bez~újmy na~obecnosti, nebo» v¾dy mù¾eme
  32 do~grafu pøidat hranu, která v~nìm je¹tì nebyla, a~dát jí nulovou kapacitu).
  33
  34 \endlist
  35
  36 \s{Definice:} {\I Tok} je funkce $f:E \to {\bb R}_{0}^{+}$ taková, ¾e~platí:
  37 \numlist{\ndotted}
  38 \:Tok po~ka¾dé hranì je omezen její kapacitou: $\forall e \in E : f(e)\le c(e)$.
  39 \:{\I Kirchhoffùv zákon:}
  40 $$\forall v \in V \setminus \{z,s\}: \sum_{u: uv \in E}{f(uv)}=\sum_{u: vu \in E}{f(vu)}.$$
  41 Neboli pro~ka¾dý vrchol kromì zdroje a~stoku platí, ¾e~to, co do~nìj pøitéká,
  42 je stejnì velké jako to, co z~nìj odtéká (\uv{sí» tìsní}).
  43 \endlist
  44
  45 \figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{2.5in}
  46
  47 %% \figure{tok.eps}{Pøíklad toku. Èísla pøedstavují toky po~hranách, v~závorkách jsou kapacity.}{4in}
  48
  49 \s{Definice:} Pro libovolnou funkci $f:E \to {\bb R}$ se nám bude hodit následující znaèení:
  50 \itemize\ibull
  51 \:$f^+(v) =  \sum_{u: uv \in E}{f(uv)}$ (celkový {\I pøítok} do vrcholu)
  52 \:$f^-(v) =  \sum_{u: vu \in E}{f(vu)}$ (celkový {\I odtok} z~vrcholu)
  53 \:$f^\Delta(v) = f^+(v) - f^-(v)$ ({\I pøebytek} ve~vrcholu)
  54 \endlist
  55
  56 \>(Kirchhoffùv zákon pak øíká prostì to, ¾e $f^\Delta(v)=0$ pro v¹echna $v\ne z,s$.)
  57
  58 \s{Pozorování:} Nìjaký tok v¾dy existuje. V libovolné síti mù¾eme v¾dy zvolit
  59 konstantnì nulovou funkci (po~¾ádné hranì nic nepoteèe). To je korektní tok,
  60 ale sotva u¾iteèný. Budeme chtít najít tok, který pøepraví co nejvíce tekutiny
  61 ze~zdroje do~spotøebièe.
  62
  63 \s{Definice:} {\I Velikost toku} $f$ budeme znaèit $\vert f\vert$ a polo¾íme ji
  64 rovnu souètu velikostí toku na hranách vedoucích do spotøebièe minus souèet
  65 velikostí tokù na~hranách ze~spotøebièe ven. V~na¹í terminologii je to tedy
  66 pøebytek ve~spotøebièi: $\vert f\vert:=f^\Delta(s).$
  67
  68 \s{Pozorování:} Jeliko¾ sí» tìsní, mìlo by být jedno, zda velikost toku mìøíme
  69 u~spotøebièe nebo u~zdroje. Vskutku, krátkým výpoètem ovìøíme, ¾e tomu tak je:
  70 $$
  71 f^\Delta(z) - f^\Delta(s) = \sum_v f^\Delta(v) = 0.
  72 $$
  73 První rovnost platí proto, ¾e podle Kirchhoffova zákona jsou zdroj a spotøebiè jediné
  74 dva vrcholy, jejich¾ pøebytek mù¾e být nenulový. Druhou rovnost získáme tak, ¾e si
  75 uvìdomíme, ¾e tok na ka¾dé hranì pøispìje do celkové sumy jednou s~kladným znaménkem
  76 a jednou se záporným. Zjistili jsme tedy, ¾e pøebytek zdroje a spotøebièe se li¹í
  77 pouze znaménkem.
  78 \qed
  79
  80 \s{Poznámka:} Rádi bychom nalezli v~zadané síti tok, jeho¾ velikost je maximální.
  81 Máme ale zaruèeno, ¾e maximum bude existovat? V¹ech mo¾ných tokù je nekoneènì mnoho
  82 a v~nekoneèné mno¾inì se mù¾e snadno stát, ¾e aèkoliv existuje supremum, není maximem
  83 (pøíklad: $\{1-1/n \mid n\in{\bb N}^+\}$).
  84 Odpovìï nám poskytne matematická analýza: mno¾ina v¹ech tokù je kompaktní podmno¾inou
  85 prostoru ${\bb R}^{\vert E\vert}$, velikost toku je spojitá (dokonce lineární) funkce
  86 z~této mno¾iny do~$\bb R$, tak¾e musí nabývat minima i maxima.
  87
  88 Nám ale bude staèít studovat sítì s~racionálními kapacitami, kde existence maximálního
  89 toku bude zjevná u¾ z~toho, ze sestrojíme algoritmus, který takový tok najde.
  90
  91 \s{První pokus:} Hledejme cestu $P$ ze~$z$ do~$s$ takovou, ¾e~$\forall e \in
  92 P: f(e) < c(e)$ (po~v¹ech jejích hranách teèe ostøe ménì, ne¾ jim dovolují
  93 jejich kapacity). Pak zjevnì mù¾eme tok upravit tak, aby se~jeho velikost
  94 zvìt¹ila. Zvolme $$\varepsilon := \min_{e \in P} \left(c(e) - f(e)\right).$$ Nový tok $f'$
  95 pak definujme jako $f'(e):=f(e) + \varepsilon$. Kapacity nepøekroèíme ($\varepsilon$
  96 je nejvìt¹í mo¾ná hodnota, abychom tok zvìt¹ili, ale nepøekroèili kapacitu ani
  97 jedné z~hran cesty $P$) a~Kirchhoffovy zákony zùstanou neporu¹eny, nebo» zdroj
  98 a~stok neomezují a~ka¾dému jinému vrcholu na~cestì $P$ se~pøítok $f^+(v)$
  99 i~odtok $f^-(v)$ zvìt¹í pøesnì o~$\varepsilon$.
 100
 101 Opakujme tento proces tak dlouho, dokud existují zlep¹ující cesty. A¾ se algoritmus
 102 zastaví (co¾ by obecnì nemusel, ale nás je¹tì chvíli trápit nemusí), získáme maximální tok?
 103 Pøekvapivì nemusíme. Napø. na~obrázku je vidìt, ¾e~kdy¾ najdeme nejdøíve cestu
 104 pøes hranu s~kapacitou 1 (na obrázku tuènì) a~u¾ hodnotu toku na~této hranì
 105 nesní¾íme, tak dosáhneme velikost toku nejvý¹e 19. Ale maximální tok této sítì
 106 má velikost 20.
 107
 108 \figure{toky02.eps}{Èísla pøedstavují kapacity jednotlivých hran.}{1.5in}
 109
 110 Zde by ov¹em situaci zachránilo, kdybychom poslali tok velikosti 1 proti smìru
 111 prostøední hrany -- to mù¾eme udìlat tøeba odeètením jednièky od toku po smìru
 112 hrany. Roz¹íøíme tedy ná¹ algoritmus tak, aby umìl posílat tok i proti smìru
 113 hran. O~kolik mù¾eme tok hranou zlep¹it (a» u¾ pøiètením po~smìru nebo odeètením
 114 proti smìru) nám bude øíkat její {\I rezerva:}
 115
 116 \s{Definice:} {\I Rezerva hrany} $uv$ je $r(uv):=c(uv) - f(uv) + f(vu).$
 117
 118 \smallskip
 119 Algoritmus bude vypadat následovnì. Postupnì doká¾eme, ¾e je koneèný a ¾e v~ka¾dé
 120 síti najde maximální tok.
 121
 122 \s{Algoritmus (Fordùv-Fulkersonùv)}
 123
 124 \algo
 125 \:$f \leftarrow$ libovolný tok, napø. v¹ude nulový.
 126 \:Dokud $\exists P$ cesta ze $z$ do $s$ taková, ¾e~$\forall e \in P: r(e) > 0$, opakujeme:
 127 \::$\varepsilon \leftarrow \min \{r(e) \mid e \in P\}$.
 128 \::Pro v¹echny hrany $uv \in P$:
 129 \:::$\delta \leftarrow \min \{f(vu),\varepsilon\}$
 130 \:::$f(vu) \leftarrow f(vu) - \delta$
 131 \:::$f(uv) \leftarrow f(uv) + \varepsilon - \delta$
 132 \:Prohlásíme $f$ za~maximální tok.
 133 \endalgo
 134
 135 \s{Koneènost:} Zastaví se~Fordùv-Fulkersonùv algoritmus?
 136
 137 \itemize\ibull
 138
 139 \:Pro~celoèíselné kapacity se~v~ka¾dém kroku zvìt¹í velikost toku alespoò o~1.
 140 Algoritmus se~tedy zastaví po~nejvíce tolika krocích, kolik je nìjaká horní
 141 závora pro~velikost maximálního toku -- napø. souèet kapacit v¹ech hran
 142 vedoucích do~stoku (tedy $c^+(s)$).
 143
 144 \:Pro~racionální kapacity vyu¾ijeme jednoduchý trik. Nech» $M$ je nejmen¹í
 145 spoleèný násobek jmenovatelù v¹ech kapacit. Spustíme-li algoritmus na sí»
 146 s~kapacitami $c'(e) = c(e)\cdot M$, bude se rozhodovat stejnì jako v~pùvodní
 147 síti, proto¾e bude stále platit $f'(e) = f(e)\cdot M$. Nová sí» je pøitom
 148 celoèíselná, tak¾e se algoritmus jistì zastaví.
 149
 150 \:Na~síti s~iracionálními kapacitami se~algoritmus chová mnohdy divoce, nemusí
 151 se~zastavit, ba ani konvergovat ke~správnému výsledku. (Zkuste vymyslet pøíklad
 152 takové sítì.)
 153
 154 \endlist
 155
 156 \s{Maximalita:} Kdy¾ se algoritmus zastaví, je tok~$f$ maximální? K~tomu se
 157 bude hodit zavést øezy.
 158
 159 \s{Definice:} Pro libovolné dvì mno¾iny vrcholù $A$ a~$B$ budeme znaèit $E(A,B)$
 160 mno¾inu hran vedoucích z~$A$ do~$B$, tedy $E(A,B) = E\cap (A\times B)$.
 161 Je-li dále $f$ nìjaká funkce pøiøazující hranám èísla, oznaèíme:
 162
 163 \itemize\ibull
 164 \:$f(A,B) = \sum_{e\in E(A,B)} f(e)$ (prùtok z~$A$ do~$B$)
 165 \:$f^\Delta(A,B) = f(A,B) - f(B,A)$ (èistý prùtok z~$A$ do~$B$)
 166 \endlist
 167
 168 \s{Definice:} {\I Øez} je uspoøádaná dvojice mno¾in vrcholù ($A,B$) taková, ¾e
 169 $A$ a $B$ jsou disjunktní, pokrývají v¹echny vrcholy, $A$ obsahuje zdroj a $B$
 170 obsahuje stok. Neboli $A \cap B = \emptyset$, $A \cup B = V$, $z \in A$, $s \in B$.
 171 Mno¾inì~$A$ budeme øíkat {\I levá mno¾ina,} mno¾inì~$B$ {\I pravá.}
 172
 173 \>{\I Kapacitu øezu} definujeme jako souèet kapacit hran zleva doprava, tedy $c(A,B)$.
 174
 175 \s{Poznámka:} Øezy se~dají definovat více zpùsoby. Jiná obvyklá definice øezu øíká,
 176 ¾e øez je mno¾ina hran grafu, po~jejím¾ odebrání se~graf rozpadne na~více
 177 komponent. Tuto vlastnost mají i na¹e øezy, ale opaènì to nemusí platit.
 178
 179 \s{Lemma:} Pro ka¾dý øez $(A,B)$ a ka¾dý tok~$f$ platí, ¾e $f^\Delta(A,B)
 180 = \vert f\vert$. (Jinými slovy velikost toku mù¾eme mìøit na libovolném øezu,
 181 nejen na triviálních øezech kolem zdroje nebo kolem spotøebièe.)
 182
 183 \proof
 184 Opìt ¹ikovným seètením pøebytkù vrcholù:
 185 $$
 186 f^\Delta(A,B) = \sum_{v\in B} f^\Delta(v) = f^\Delta(s).
 187 $$
 188 První rovnost získáme poèítáním pøes hrany: ka¾dá hrana vedoucí z~vrcholu v~$B$
 189 do~jiného vrcholu v~$B$ pøispìje jednou kladnì a jednou zápornì; hrany le¾ící
 190 celé mimo~$B$ nepøispìjí vùbec; hrany s~jedním koncem v~$B$ a druhým mimo pøispìjí
 191 jednou, pøièem¾ znaménko se bude li¹it podle toho, který konec je v~$B$. Druhá
 192 rovnost je snadná: v¹echny vrcholy v~$B$ mimo spotøebièe mají podle Kirchhoffova
 193 zákona nulový pøebytek.
 194 \qed
 195
 196 \s{Dùsledek:} Pro ka¾dý tok~$f$ a ka¾dý øez $(A,B)$ platí $\vert f \vert \le c(A,B)$.
 197 (Velikost ka¾dého toku je shora omezena kapacitou ka¾dého øezu.)
 198
 199 \proof
 200 $f^\Delta(A,B) = f(A,B) - f(B,A) \le f(A,B) \le c(A,B)$.
 201 \qed
 202
 203 \s{Dùsledek:} Pokud $\vert f\vert = c(A,B)$, pak je tok~$f$ maximální a øez~$(A,B)$
 204 minimální. Jinými slovy pokud najdeme dvojici tok a stejnì velký øez, mù¾eme øez pou¾ít
 205 jako certifikát maximality toku. Následující vìta nám zaruèí, ¾e je to mo¾né v¾dy:
 206
 207 \s{Vìta:} Pokud se~Fordùv-Fulkersonùv algoritmus zastaví, tak vydá maximální tok.
 208
 209 \proof
 210 Nech» se~Fordùv-Fulkersonùv algoritmus zastaví. Definujme mno¾inu vrcholù $A
 211 := \{v \in V \mid \hbox{existuje cesta ze~$z$ do~$v$ jdoucí po~hranách s~$r
 212 > 0$}\}$ a~$B := V \setminus A$.
 213
 214 Dvojice $(A,B)$ je øez, nebo» $z \in A$ (ze~$z$ do~$z$ existuje cesta délky 0)
 215 a~$s \in B$ (kdyby $s \not\in B$, tak by musela existovat cesta ze~$z$ do~$s$
 216 s~kladnou rezervou, tudí¾ by algoritmus neskonèil, nýbr¾ tuto cestu vzal
 217 a~stávající tok vylep¹il).
 218
 219 Dále víme, ¾e~v¹echny hrany øezu mají nulovou rezervu, èili $\forall uv \in
 220 E(A,B) : r(uv) = 0$ (kdyby mìla hrana $uv$ rezervu nenulovou, tedy kladnou,
 221 tak by vrchol $v$ patøil do~$A$). Proto po~v¹ech hranách øezu vedoucích z~$A$
 222 do~$B$ teèe tolik, kolik jsou kapacity tìchto hran, a~po~hranách vedoucích
 223 z~$B$ do~$A$ neteèe nic, tedy $f(uv) = c(uv)$ a $f(vu) = 0$. Máme øez $(A,B)$
 224 takový, ¾e~$f^\Delta(A,B) = c(A,B)$. To znamená, ¾e~jsme na¹li maximální tok
 225 a~minimální øez. \qed
 226
 227 Dokázali jsme tedy následující:
 228
 229 \s{Vìta:} Pro~sí» s~racionálními kapacitami se~Fordùv-Fulkersonùv algoritmus
 230 zastaví a~vydá maximální tok a~minimální øez.
 231
 232 \s{Vìta:} Sí» s~celoèíselnými kapacitami má aspoò jeden z~maximálních tokù
 233 celoèíselný a~Fordùv-Fulkersonùv algoritmus takový tok najde.
 234
 235 \proof
 236 Kdy¾ dostane Fordùv-Fulkersonùv algoritmus celoèíselnou sí», tak najde maximální tok a~ten bude zase celoèíselný (algoritmus nikde nedìlí).
 237 \qed
 238
 239 To, ¾e~umíme najít celoèíselné øe¹ení není úplnì samozøejmé. (U~jiných problémù takové ¹tìstí mít nebudeme.) Uka¾me si rovnou jednu aplikaci, která právì celoèíselný tok vyu¾ije.
 240
 241 \h{Hledání nejvìt¹ího párování v~bipartitních grafech}
 242
 243 \s{Definice:} Mno¾ina hran $F \subseteq E$ se~nazývá {\I párování}, jestli¾e
 244 ¾ádné dvì hrany této mno¾iny nemají spoleèný ani jeden vrchol. Neboli $\forall
 245 e,f \in F : e \cap f = \emptyset$. {\I Velikostí} párování myslíme poèet jeho
 246 hran.
 247
 248 Chceme-li v~daném bipartitním grafu $(V,E)$ nalézt nejmen¹í párování,
 249 pøetvoøíme jej nejprve na sí» $(V',E',c,z,s)$ takto:
 250
 251 \itemize\ibull
 252 \:Nalezneme partity grafu, budeme jim øíkat {\I levá} a {\I pravá.}
 253 \:Pøidáme zdroj~$z$ a vedeme z~nìj hrany do v¹ech vrcholù levé partity.
 254 \:Pøidáme spotøebiè~$s$ a vedeme do nìj hrany ze~v¹ech vrcholù pravé partity.
 255 \:Hrany zadaného grafu zorientujeme zleva doprava.
 256 \:V¹em hranám nastavíme jednotkovou kapacitu.
 257 \endlist
 258
 259 \figure{toky04.eps}{Hledání nejvìt¹ího párování v~bipartitním grafu.}{2in}
 260
 261 \>Nyní v~této síti najdeme maximální celoèíselný tok. Jeliko¾ v¹echny hrany
 262 mají kapacitu~1, musí po ka¾dé hranì téci buï~0 nebo~1. Do~výsledného párování
 263 dáme právì ty hrany pùvodního grafu, po~kterých teèe~1.
 264
 265 Dostaneme opravdu párování? Kdybychom nedostali, znamenalo by to, ¾e nìjaké
 266 dvì hrany mají spoleèný vrchol. Ov¹em kdyby se setkaly ve~vrcholu v~pravé
 267 partitì, pøitekly by do tohoto vrcholu alespoò 2 jednotky toku a ty by nemìly
 268 kam odtéci. Analogicky pokud by se setkaly nalevo, musely by z~vrcholu odtéci
 269 alespoò 2 jednotky, ale ty se tam nemají kudy dostat.
 270
 271 Zbývá nahlédnout, ¾e párování je nejvìt¹í mo¾né. K~tomu si staèí v¹imnout,
 272 ¾e z~toku vytvoøíme párování o~tolika hranách, kolik je velikost toku, a naopak
 273 z~ka¾dého párování umíme vytvoøit celoèíselný tok odpovídající velikosti.
 274 Jinými slovy nalezli jsme bijekci mezi mno¾inou v¹ech celoèíselných tokù
 275 a mno¾inou v¹ech párování a tato bijekce zachovává velikost. Nejvìt¹í
 276 tok tedy musí odpovídat nejvìt¹ímu párování.
 277
 278 Snadno tak získáme následující vìtu:
 279
 280 \s{Vìta:} Nejvìt¹í párování v~bipartitním grafu lze nalézt v~èase $\O(mn)$.
 281
 282 \proof
 283 Pøedvedená konstrukce vytvoøí z~grafu sí» o~$n'=n+2$ vrcholech a~$m'=m+2n$
 284 hranách a spotøebuje na to èas $\O(m'+n')$. Pak nalezneme maximální celoèíselný
 285 tok Fordovým-Fulkersonovým algoritmem, co¾ trvá $\O(m'n')$. Nakonec tok v~lineárním
 286 èase pøelo¾íme na~párování. V¹e dohromady trvá $\O(m'n') = \O(mn)$.
 287 \qed
 288
 289 \bye