2-toky/2-toky.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{2}{Toky v sítích}{(pøedná¹el T. Valla, zapsali J. Machálek a K. Vandas)}
   4
   5 \s{Motivaèní úlohy:}
   6 \itemize\ibull
   7 \:Mìjme orientovaný graf se speciálními vrcholy ®elivka a Kanál pøedstavující pra¾ské vodovody. V tomto grafu budou vrcholy vodovodními stanicemi a hrany trubkami mezi nimi. Kolik vody proteèe ze ®elivky do Kanálu?
   8 \:Mìjme orientovaný graf pøedstavující ¾eleznièní sí»; graf má význaèné vrcholy Moskva a Fronta, ka¾dá hrana grafu má kapacitu, kterou mù¾e uvézt. Kolik vojákù je schopna sí» pøevézt z~Moskvy a spotøebovat na Frontì?
   9 \endlist
  10
  11 \s{Definice:} {\I Sí»} je uspoøádaná ètveøice $(G,z,s,c)$, kde $G$ je
  12 orientovaný graf, $z$~a~$s$~jsou nìjaké dva jeho vrcholy ({\I zdroj} a {\I stok}) a $c$ je
  13 {\I kapacita hran,} kterou pøedstavuje funkce $c:E(G)\to{\bb
  14 R}_{0}^{+}$.
  15
  16 \figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{3in}
  17
  18 \par\noindent {\sl Intuice:} Toky v sítích pøedstavují rozvr¾ení, jakým suroviny sítí poteèou.
  19
  20 \s{Definice:} {\I Tok} je funkce $f:E(G)\to{\bb R}_{0}^{+}$ taková, ¾e platí:
  21 \numlist{\ndotted}
  22 \:Tok po~ka¾dé hranì je omezen její kapacitou: $0\le f(e)\le c(e)$.
  23 \:Kirchhoffùv zákon -- \uv{sí» tìsní}: $$\sum_{xu \in E}{f(xu)}=\sum_{ux \in E}{f(ux)}\quad\hbox{pro ka¾dé }u\in V(G) \setminus \{z,s\}.$$
  24 \endlist
  25
  26 \s{Poznámka:} Pokud bychom se chtìli v definici toku u bodu 2 vyhnout podmínkám pro $z$ a $s$, mù¾eme zdroj a stok vzájemnì propojit (pak jde o tzv. cirkulaci).
  27
  28 \s{Poznámka:} V angliètinì se obvykle zdroj znaèí \uv{$s$} a stok \uv{$t$} (jako source a~target).
  29
  30 \figure{tok.eps}{Pøíklad toku. Èísla pøedstavují toky po~hranách, v~závorkách jsou kapacity.}{4in}
  31
  32 \s{Definice:} {\I Velikost toku} $f$ je: $$\vert f\vert:=\sum_{zx \in E}{f(zx)}-\sum_{xz \in E}{f(xz)}.$$
  33
  34 \>Budeme tedy chtít najít v~zadané síti tok, jeho¾ velikost je maximální. Musí v¾dycky existovat?
  35
  36 \s{Vìta:} Pro ka¾dou sí» existuje maximální tok.
  37
  38 \par\noindent {\sl Idea dùkazu:} Doká¾e se pomocí metod matematické analýzy s~tím, ¾e mno¾ina tokù je kompaktní a funkce velikosti toku je spojitá (dokonce lineární).
  39
  40 Dobrá, maximální tok v¾dy existuje. Ale kdy¾ nám ho nìkdo uká¾e, umíme poznat,
  41 ¾e je skuteènì maximální? K~tomu se budou hodit øezy:
  42
  43 \par\noindent {\sl Intuice:} Øez v~grafu je mno¾ina hran oddìlující zdroj a stok.
  44
  45 \s{Definice:} {\I Øez} $R$ v síti $(G,z,s,c)$ je mno¾ina hran $R$ taková, ¾e
  46 neexistuje orientovaná cesta ze $z$~do $s$~v~grafu $(V(G),E(G)\setminus R)$.
  47
  48 \s{Definice:} {\I Kapacita øezu} $c(R)=\sum_{uv \in R}{c(uv)}$.
  49
  50 Nìkdy je lep¹í se na~øezy dívat takto:
  51
  52 \s{Definice:} Pro dvì disjunktní mno¾iny vrcholù $A,B$, kde $z\in A$ a $s\in B$ zavedeme
  53 {\I separátor} $S(A,B)$, co¾ bude mno¾ina hran vedoucích z~$A$ do~$B$. Pokud je $g$ funkce
  54 definovaná na~hranách (tøeba tok nebo kapacita), definujeme $g(A,B):=\sum_{uv \in E,u\in A,v\in B}{g(uv)}.$
  55
  56 \s{Pozorování:} Ka¾dý separátor je øezem (libovolná orientovaná cesta ze~$z$ do~$s$ musí
  57 nìkdy opustit mno¾inu~$A$, a to jde pouze po~hranì patøící do~separátoru). Opaènì to sice
  58 platit nemusí, ale platí, ¾e ke~ka¾dému øezu existuje separátor takový, ¾e souèet kapacit
  59 jeho hran je nejvý¹e kapacita daného øezu. Staèí si zvolit mno¾inu $A$ jako vrcholy dosa¾itelné
  60 ze~zdroje po~hranách nele¾icích v~øezu a do~$B$ dát v¹echny ostatní vrcholy. Separátor
  61 $S(A,B)$ pak bude tvoøen výhradnì hranami øezu (ne~nutnì v¹emi) a sám bude øezem.
  62
  63 \s{Definice:} Pro libovolnou mno¾inu vrcholù $A$ zavedeme její {\I doplnìk} $\overline A:=V(G)\setminus A$.
  64
  65 Nyní si v¹imneme, ¾e velikost toku mù¾eme mìøit pøes libovolný separátor: je to mno¾ství
  66 tekutiny, které teèe pøes separátor z~$A$ do~$B$ minus to, které se vrací zpátky
  67 (zatím jsme velikost mìøili u~zdroje, vlastnì na~triviálním separátoru $A=\{z\}$, $B=\overline A).$
  68
  69 \s{Lemma:} Nech» $A\subseteq V(G),z\in A,s\not\in A$ a $f$ je libovolný tok. Potom platí,
  70 ¾e: $$\vert f\vert=f(A,\overline A)-f(\overline A,A).$$
  71
  72 \proof
  73 provedeme pomocí Kirchhoffova zákona a definice velikosti toku:
  74 $$\hbox{Pro ka¾dý vrchol~$u\ne z,s$ platí:~~} \sum_{ux \in E}{f(ux)}-\sum_{xu \in E}{f(xu)}=0,$$
  75 $$\hbox{pro zdroj pak:~~} \sum_{zx \in E}{f(zx)}-\sum_{xz \in E}{f(xz)=\vert f\vert}.$$
  76 Rovnice seèteme:
  77 $$\sum_{u\in A}{\left(\sum_{ux \in E}{f(ux)}-\sum_{xu \in E}{f(xu)}\right)}=\vert f\vert.$$
  78 V¹imneme si, ¾e hrany, jeji¾ oba koncové vrcholy le¾í v~mno¾inì~$A$, pøispívají
  79 k~této sumì jednou kladnì a jednou zápornì, hrany, její¾ ani jeden vrchol nele¾í v~$A$,
  80 nepøispívají vùbec, a koneènì hrany vedoucí z~$A$ do~$B$, resp. opaènì pøispìjí jen jednou
  81 (kladnì, resp. zápornì). Tedy:
  82 $$f(A,\overline A)-f(\overline A,A)=\sum_{u\in A,v\not\in A}{f(uv)}-\sum_{u\not\in A,v\in A}{f(uv)}=\vert f \vert.$$
  83 \qed
  84
  85 \s{Dùsledek:} Pokud $f$ je tok, $R$ je øez, pak platí:  $\vert f \vert\le c(R)$.
  86
  87 \proof
  88 Doká¾eme pro separátory (u¾ víme, ¾e ke~ka¾dému øezu najdeme stejnì velký nebo men¹í separátor):
  89 $$\vert f \vert=f(A,\overline A)-f(\overline A,A)\le f(A,\overline A)\le c(A,\overline A)\le c(R).$$
  90 \qed
  91
  92 Nyní víme, ¾e velikost ka¾dého toku je shora omezena velikostí ka¾dého øezu. Kdybychom tedy
  93 k~na¹emu toku umìli najít stejnì velký øez, hned víme, ¾e tok je maximální a øez minimální.
  94 Pøekvapivì platí, ¾e se to povede v¾dy. K~tomu se nám budou hodit zlep¹ující cesty:
  95
  96 \s{Definice:} {\I Zlep¹ující cesta} budeme øíkat takové cestì mezi danými dvìma vrcholy,
  97 která pou¾ívá buïto hrany sítì (hrany orientované po~smìru cesty) nebo hrany k~nim opaèné (v~síti jsou
  98 tedy proti smìru cesty).
  99
 100 \figure{cesta.eps}{Pøíklad zlep¹ující cesty.}{3in}
 101
 102 \s{Definice:} {\I Zlep¹ující cesta} $P$ ze $z$ do $s$ je {\I nasycená}, pokud:
 103 $$\exists e \in P:\cases{
 104         f(e)=c(e) & \hbox{je-li $e$ orientovaná po smìru} \cr
 105         f(e)=0 & \hbox{je-li $e$ orientovaná proti smìru} \cr
 106 }$$
 107 \>Jinak je zlep¹ující cesta nenasycená.
 108
 109 \s{Definice:} {\I Tok je nasycený,} pokud je ka¾dá zlep¹ující cesta $P$ ze $z$ do $s$ nasycená.
 110
 111 \s{Vìta:} Tok $f$ je nasycený $\Leftrightarrow$ $f$ je maximální. Navíc pro ka¾dý maximální tok $f$ existuje øez $R$ takový, ¾e $\vert f \vert=c(R)$.
 112
 113 \proof
 114
 115 \>\uv{$\Leftarrow$} doká¾eme nepøímo -- uká¾eme, ¾e pokud nìjaký tok není nasycený, tak ho
 116 je¹tì lze zlep¹it, proèe¾ nemù¾e být maximální. Mìjme nìjaký nenasycený tok~$f$. Existuje tedy
 117 nenasycená zlep¹ující cesta $P$. Podél této cesty budeme tok vylep¹ovat.
 118 Zvolíme:
 119 $$
 120 \eqalign{
 121 \varepsilon_1&:=\min_{e\in P\hbox{\sevenrm~po smìru}}{\{c(e)-f(e)\}}, \cr
 122 \varepsilon_2&:=\min_{e\in P\hbox{\sevenrm~proti smìru}}{\{f(e)\}}, \cr
 123 \varepsilon&:=\min{\{\varepsilon_1,\varepsilon_2\}}. \cr
 124 }
 125 $$
 126 Jeliko¾ cesta byla nenasycená, musí být $\varepsilon>0$. Nyní z~toku~$f$ vytvoøíme
 127 tok~$f'$ takto:
 128 $$f'(e):=\cases{
 129         f(e)+\varepsilon & \hbox{je-li $e$ po smìru cesty,} \cr
 130         f(e)-\varepsilon & \hbox{je-li $e$ proti smìru,} \cr
 131         f(e) & \hbox{pokud $e\not\in P$.} \cr
 132 }
 133 $$
 134 \>Nyní je potøeba ovìøit, ¾e $f^{'}$ je skuteènì tok:
 135 $$0\le f^{'}(e)\le c(e)\dots\hbox{platí stále díky volbì }\varepsilon.$$
 136
 137 \>Platnost Kirchhoffova zákona ovìøíme rozborem pøípadù:
 138 \figure{kirch.eps}{Rozbor pøípadù.}{4in}
 139
 140 \>Funkce $f'$ je tedy tok. Jeho velikost se ov¹em oproti~$f$ zvý¹ila o~$\varepsilon$, tak¾e~$f$ nebyl maximální.
 141
 142 \>\uv{$\Rightarrow$}: Uvá¾íme mno¾inu vrcholù $A\subseteq V(G)$ definovanou tak, ¾e $v\in A$
 143 právì tehdy, kdy¾ existuje nenasycená cesta ze $z$ do $v$. V¹imnìme si, ¾e $z \in A$ a $s \not\in A$.
 144 Potom $S(A,\overline A)$ je øez, který je stejnì velký jako tok~$f$. Jak u¾ víme, pokud k~toku
 145 najdeme stejnì velký øez, je tok maximální.
 146 \qed
 147
 148 \figure{nenasyc.eps}{Rozdìlení $V(G)$ na mno¾inu $A$ a $\overline A$ v dùkazu hlavní vìty o tocích.}{2.5in}
 149
 150 \>To, co jsme o~tocích zjistili, mù¾eme shrnout do~následující \uv{minimaxové} vìty:
 151
 152 \s{Vìta (Hlavní vìta o tocích, Ford-Fulkerson):} Pro ka¾dou sí» platí: $$\max_{f\hbox{\sevenrm~tok}}{\vert f \vert=\min_{R\hbox{\sevenrm~øez}}{c(R)}}.$$
 153
 154 \proof
 155 Nerovnost \uv{$\le$} je ná¹ Dùsledek lemmatu o~tocích a øezech, rovnost
 156 platí proto, ¾e k~maximálnímu toku existuje podle pøedcházející vìty stejnì
 157 velký øez.
 158 \qed
 159
 160 \>Zlep¹ování tokù pomocí zlep¹ujících cest není jen pìkný dùkazový prostøedek,
 161 dá se pomocí nìj také formulovat elegantní algoritmus na~hledání maximálního toku:
 162
 163 \s{Algoritmus (hledání maximálního toku v síti, Ford-Fulkerson)}
 164
 165 \algo
 166 \:$f \leftarrow \hbox{libovolný tok}$, tøeba v¹ude nulový ($\forall e \in E: f(e) \leftarrow 0 $).
 167 \:Dokud $\exists$ zlep¹ující cesta $P$: vylep¹íme $f$ podél $P$ jako v~dùkazu vìty.
 168 \:Prohlásíme $f$ za~maximální tok.
 169 \endalgo
 170
 171 \h{Cvièení:}
 172 \itemize\ibull
 173 \:Je pro pøirozené kapacity F-F algoritmus koneèný? Ano -- v ka¾dém zlep¹ujícím
 174 kroku algoritmu se celkový tok zvìt¹í aspoò o jedna. Proto¾e máme horní odhad
 175 na velikost maximálního toku (napø. souèet kapacit v¹ech hran), máme i~horní odhad na dobu
 176 bìhu algoritmu.
 177 \:Je F-F algoritmus koneèný pro racionální kapacity hran? Ano -- v¹echny
 178 kapacity vynásobíme spoleèným jmenovatelem a pøevedeme na pøedchozí pøípad.
 179 Algoritmus se pøitom chová stejnì jako s~pùvodními kapacitami.
 180 \:A~pro reálné kapacity? Obecnì ne -- zkuste najít sí» s~nìkterými kapacitami
 181 iracionální, kde se algoritmus pøi ne¹ikovné volbì zlep¹ujících cest nikdy
 182 nezastaví a dokonce ani nekonverguje k~maximálnímu toku.
 183 \:Kolik krokù bude muset algoritmus na následující síti maximálnì udìlat, aby
 184 úspì¹nì dobìhl? ($2M$ krokù)
 185 \figure{2M.eps}{Pøíklad sítì. Kolik krokù musí maximálnì udìlat F-F algoritmus?}{2in}
 186 \:Pokud bychom v¾dy hledali {\I nejkrat¹í} zlep¹ující cestu, co¾ je snad
 187 nejpøímoèaøej¹í mo¾ná implementace (prohledávání do ¹íøky), algoritmus by
 188 se zastavil po~$\O(M^2N)$ krocích (tomu se øíká Edmondsùv-Karpùv algoritmus).
 189 To si nebudeme dokazovat a místo toho si na~pøí¹tí pøedná¹ce rovnou odvodíme
 190 efektivnìj¹í Dinicùv algoritmus.
 191 \endlist
 192
 193 \bye