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