3 \prednaska{1}{Toky, øezy a Ford-Fulkersonùv algoritmus}{}
5 V~této kapitole nadefinujeme toky v~sítích, odvodíme základní vìty o~nich
6 a také Ford-Fulkersonùv algoritmus pro hledání maximálního toku. Také uká¾eme,
7 jak na~hledání maximálního toku pøevést problémy týkající se øezù, separátorù
8 a párování v~bipartitních grafech. Dal¹í tokové algoritmy budou následovat v~pøí¹tích kapitolách.
12 Intuitivní pohled: sí» je systém propojených potrubí, který pøepravuje tekutinu
13 ze~zdroje~$s$ (source) do~spotøebièe~$t$ (target), pøièem¾ tekutina
14 se nikde mimo tato dvì místa neztrácí ani nevzniká.
19 \:{\I Sí»} je uspoøádaná pìtice $(V,E,s,t,c)$, kde:
21 \:$(V,E)$ je orientovaný graf,
22 \:$s\in V$ {\I zdroj,}
23 \:$t\in V$ {\I spotøebiè} neboli {\I stok} a
24 \:$c: E\rightarrow {\bb R}^+$ funkce udávající {\I kapacity} jednotlivých hran.
26 \:{\I Ohodnocení} hran je libovolná funkce $f:\, E\rightarrow {\bb R}$. Pro ka¾dé ohodnocení $f$
28 $$ f^+(v) = \sum_{e=(\cdot,w)} f(e), \quad
29 f^-(v) = \sum_{e=(w,\cdot)} f(e), \quad
30 f^\Delta(v) = f^+(v) - f^-(v)
32 [co do~vrcholu pøiteèe, co odteèe a jaký je v~nìm pøebytek].
33 \:{\I Tok} je ohodnocení $f:\, E\rightarrow {\bb R}$, pro které platí:
35 \:$\forall e: 0 \le f(e) \le c(e)$, \quad {\I (dodr¾uje kapacity)}
36 \:$\forall v\ne s,t: f^\Delta(v)=0$. \quad {\I (Kirchhoffùv zákon)}
38 \:{\I Velikost toku:} $\vert f \vert = -f^\Delta(s)$.
39 \:{\I Øez (tokový):} mno¾ina vrcholù $C\subset V$ taková, ¾e $s\in C$, $t\not\in C$. Øez mù¾eme také
40 ztoto¾nit s~mno¾inami hran $C^- = E \cap (C \times \overline C)$ [tìm budeme øíkat hrany zleva doprava]
41 a $C^+ = E \cap (\overline C \times C)$ [hrany zprava doleva].
42 \:{\I Kapacita øezu:} $\vert C \vert = \sum_{e \in C^-} c(e)$ (bereme v~úvahu jen hrany zleva doprava).
44 $f^+(C)=\sum_{e\in C^+} f(e)$,
45 $f^-(C)=\sum_{e \in C^-} f(e)$,
46 $f^\Delta(C)=f^+(C)-f^-(C)$.
47 \:{\I Cirkulace} je tok nulové velikosti, èili $f$ takové, ¾e $f^\Delta(v)=0$ pro v¹echna~$v$.
50 %%%\figure{graf.eps}{Pøíklad orientovaného grafu ze zvoleným zdrojem a stokem.}{0.4\hsize}
52 Základním problémem, kterým se budeme zabývat, je hledání {\I maximálního toku} (tedy toku nejvìt¹í mo¾né
53 velikosti) a {\I minimálního øezu} (øezu nejmen¹í mo¾né kapacity).
57 \s{Vìtièka:} V~ka¾dé síti existuje maximální tok a minimální øez.
59 \proof Existence minimálního øezu je triviální, proto¾e øezù v~ka¾dé síti je koneènì mnoho;
60 pro toky v~sítích s~reálnými kapacitami to ov¹em není samozøejmost a je k~tomu potøeba trocha matematické
61 analýzy (v~prostoru v¹ech ohodnocení hran tvoøí toky kompaktní mno¾inu, velikost toku je lineární funkce,
62 a~tedy i spojitá, proèe¾ nabývá maxima). Pro racionální kapacity dostaneme tuto vìtièku jako dùsledek
63 analýzy Ford-Fulkersonova algoritmu.
66 \s{Pozorování:} Kdybychom velikost toku definovali podle spotøebièe, vy¹lo by toté¾. Platí toti¾:
67 $$f^\Delta(s) + f^\Delta(t) = \sum_v f^\Delta(v) = \sum_e f(e) - f(e) = 0$$
68 (první rovnost plyne z~Kirchoffova zákona -- v¹echna ostatní $f^\Delta(v)$ jsou nulová; druhá pak z~toho,
69 ¾e ka¾dá hrana pøispìje k~jednomu $f^+(v)$ a k~jednomu $f^-(v)$). Proto je $\vert f\vert = -f^\Delta(s) = f^\Delta(t).$
71 Stejnì tak mù¾eme velikost toku zmìøit na~libovolném øezu:
73 \s{Lemma:} Pro ka¾dý øez $C$ platí, ¾e $\vert f\vert = -f^\Delta(C) \le \vert C \vert$.
75 \proof První èást indukcí: ka¾dý øez mù¾eme získat postupným pøidáváním vrcholù do~triviálního øezu $\{s\}$
76 [èili pøesouváním vrcholù zprava doleva], a~to, jak uká¾e jednoduchý rozbor pøípadù, nezmìní $f^\Delta$.
77 Druhá èást: $-f^\Delta(C) = f^-(C) - f^+(C) \le f^-(C) \le \vert C \vert.$ \qed
79 Víme tedy, ¾e velikost ka¾dého toku lze omezit kapacitou libovolného øezu. Kdybychom na¹li tok a øez stejné
80 velikosti, mù¾eme si proto být jisti, ¾e tok je maximální a øez minimální. To není náhoda, platí toti¾
83 \s{Vìta (Ford, Fulkerson):} V~ka¾dé síti je velikost maximálního toku rovna velikosti minimálního øezu.
85 \proof Jednu nerovnost jsme dokázali v~pøedchozím lemmatu, druhá plyne z~duality lineárního
86 programování [max. tok a min. øez jsou navzájem duální úlohy], ale k~pìknému kombinatorickému
87 dùkazu pùjde opìt pou¾ít Ford-Fulkersonùv algoritmus.
90 \h{Ford-Fulkersonùv algoritmus}
92 Nejpøímoèaøej¹í zpùsob, jak bychom mohli hledat toky v~sítích, je zaèít s~nìjakým tokem (nulový je po~ruce v¾dy)
93 a postupnì ho zlep¹ovat tak, ¾e nalezneme nìjakou nenasycenou cestu a po¹leme po~ní \uv{co pùjde}.
94 To~bohu¾el nefunguje, ale mù¾eme tento postup trochu zobecnit a být ochotni pou¾ívat nejen hrany,
95 pro~které je $f(e) < c(e)$, ale také hrany, po~kterých nìco teèe v~protismìru a my mù¾eme tok
96 v~na¹em smìru simulovat odeètením od~toku v~protismìru. Trochu formálnìji:
101 \:{\I Rezerva} hrany $e=(v,w)$ pøi toku~$f$ se definuje jako $r(e) = (c(e) - f(e)) + f(e^\prime)$, kde $e^\prime=(w,v)$.
102 Pro úèely tohoto algoritmu budeme pøedpokládat, ¾e ke~ka¾dé hranì existuje hrana opaèná; pokud ne, dodefinujeme
103 si ji a dáme jí nulovou kapacitu.
104 \:{\I Zlep¹ující cesta} je orientovaná cesta, její¾ v¹echny hrany mají nenulovou rezervu.
110 \:$f \leftarrow \<nulový tok>$.
111 \:Dokud existuje zlep¹ující cesta $P$ z~$s$ do~$t$:
112 \::$m \leftarrow \min_{e\in P} r(e)$.
113 \::Zvìt¹íme tok $f$ podél~$P$ o~$m$ (ka¾dé hranì $e\in P$ zvìt¹íme $f(e)$, pøípadnì zmen¹íme $f(e^\prime)$, podle toho, co jde).
116 \s{Analýza:} Nejdøíve si rozmysleme, ¾e pro celoèíselné kapacity algoritmus v¾dy dobìhne: v~ka¾dém kroku
117 stoupne velikost toku o~$m \ge 1$, co¾ mù¾e nastat pouze koneènìkrát. Podobnì pro racionální kapacity:
118 pøenásobíme-li v¹echny kapacity jejich spoleèným jmenovatelem, dostaneme sí» s~celoèíselnými kapacitami,
119 na~které se bude algoritmus chovat identicky a jak ji¾ víme, skonèí. Pro~iracionální kapacity obecnì
120 dobìhnout nemusí, zkuste vymyslet protipøíklad.
122 Uva¾me nyní situaci po~zastavení algoritmu. Funkce~$f$ je urèitì tok, proto¾e jím byla po~celou dobu
123 bìhu algoritmu. Prozkoumejme teï mno¾inu $C$ vrcholù, do~nich¾ po~zastavení algoritmu vede zlep¹ující cesta ze~zdroje.
124 Jistì $s\in C$, $t\not\in C$, tak¾e tato mno¾ina je øez. Navíc pro ka¾dou hranu $e\in C^-$ musí
125 být $f(e)=c(e)$ a pro ka¾dou $e'\in C^+$ je $f(e')=0$, proto¾e jinak by rezerva hrany~$e$ nebyla
126 nulová. Tak¾e $f^-(C) = \vert C \vert$ a $f^+(C) = 0$, èili $\vert f\vert = \vert C \vert$.
128 Na¹li jsme tedy k~toku, který algoritmus vydal, øez stejné velikosti, a~proto, jak u¾ víme,
129 je tok maximální a øez minimální. Tím jsme také dokázali Ford-Fulkersonovu vìtu\foot{Dokonce
130 jsme ji dokázali i pro reálné kapacity, proto¾e mù¾eme algoritmus spustit rovnou na maximální tok místo
131 nulového a on se ihned zastaví a vydá certifikující øez.} a existenci maximálního toku. Navíc algoritmus nikdy
132 nevytváøí z~celých èísel necelá, èim¾ získáme:
134 \s{Dùsledek:} Sí» s~celoèíselnými kapacitami má maximální tok, který je celoèíselný.
136 \s{Èasová slo¾itost} F-F algoritmu mù¾e být pro obecné sítì a ne¹ikovnou volbu zlep¹ujících
137 cest obludná, ale jak dokázali Edmonds s~Karpem, pokud budeme hledat cesty prohledáváním
138 do~¹íøky (co¾ je asi nejpøímoèaøej¹í implementace), pobì¾í v~èase $\O(m^2n)$. Pokud budou
139 v¹echny kapacity jednotkové, snadno nahlédneme, ¾e staèí $\O(nm)$. Edmondsùv a Karpùv
140 odhad nebudeme dokazovat, místo toho si v~pøí¹tí kapitole pøedvedeme efektivnìj¹í algoritmus.
142 \h{Øezy, separátory a $k$-souvislost}
144 Teorie tokù nám rovnì¾ poslou¾í ke~zkoumání násobné souvislosti grafù.
146 \s{Definice:} Pro ka¾dý neorientovaný graf $G$ a libovolné jeho vrcholy $s,t$ zavedeme:
148 \:{\I $st$-øez} je mno¾ina hran $F$ taková, ¾e v~grafu $G-F$ jsou
149 vrcholy $s,t$ v~rùzných komponentách souvislosti.
150 \:{\I $st$-separátor} je mno¾ina vrcholù $W$ taková, ¾e $s,t\not\in W$ a v~grafu $G-W$
151 jsou vrcholy $s,t$ v~rùzných komponentách souvislosti.
152 \:{\I Øez} je mno¾ina hran, která je $xy$-øezem pro nìjakou dvojici vrcholù $x,y$.
153 \:{\I Separátor} je mno¾ina vrcholù, která je $xy$-separátorem pro nìjakou dvojici vrcholù $x,y$.
154 \:$G$ je {\I hranovì $k$-souvislý,} pokud $\vert V\vert > k$ a v¹echny øezy v~$G$
155 mají alespoò~$k$ hran.
156 \:$G$ je {\I vrcholovì $k$-souvislý,} pokud $\vert V\vert > k$ a v¹echny separátory v~$G$
157 mají alespoò~$k$ vrcholù.
160 V¹imnìte si, ¾e nesouvislý graf má øez i separátor nulové velikosti, tak¾e vrcholová i hranová 1-souvislost
161 splývají s~obyèejnou souvislostí pro v¹echny grafy o~alespoò dvou vrcholech. Hranovì 2-souvislé
162 jsou právì (netriviální) grafy bez {\I mostù,} vrcholovì 2-souvislé jsou ty bez {\I artikulací.}
164 Pro orientované grafy mù¾eme $st$-øezy a $st$-separátory definovat analogicky
165 (toti¾, ¾e po~odstranìní pøíslu¹né mno¾iny hran èi vrcholù neexistuje orientovaná
166 cesta z~$s$ do~$t$), globální øezy a separátory ani vícenásobná souvislost se obvykle
169 \s{Poznámka:} Minimální orientované $st$-øezy podle této definice a minimální tokové øezy
170 podle definice ze~zaèátku kapitoly splývají: ka¾dý tokový øez~$C$ odpovídá $st$-øezu stejné
171 velikosti tvoøenému hranami v~$C^-$; naopak pro~minimální $st$-øez musí být mno¾ina
172 vrcholù dosa¾itelných z~$s$ po~odebrání øezu z~grafu tokovým øezem, opìt stejné velikosti.
173 [Velikost mìøíme souètem kapacit hran.] Dává tedy rozumný smysl øíkat obojímu stejnì.
174 Podobnì se chovají i neorientované grafy, pokud do~\uv{tokového} øezu poèítáme
175 hrany v~obou smìrech.
177 Analogií tokù je pak existence nìjakého poètu disjunktních cest (vrcholovì nebo hranovì)
178 mezi vrcholy~$s$ a~$t$. Analogií F-F~vìty pak budou známé Mengerovy vìty:
180 \s{Vìta (Mengerova, lokální hranová orientovaná):}
181 Buï $G$ orientovaný graf a $s,t$ nìjaké jeho vrcholy. Pak je velikost minimálního
182 $st$-øezu rovna maximálnímu poètu hranovì disjunktních $st$-cest.\foot{orientovaných
185 \proof Z~grafu sestrojíme sí» tak, ¾e $s$~bude zdroj, $t$~spotøebiè a v¹em
186 hranám nastavíme kapacitu na~jednotku. Øezy v~této síti odpovídají øezùm v~pùvodním
187 grafu. Podobnì ka¾dý systém hranovì disjunktních $st$-cest odpovídá toku stejné
188 velikosti a naopak ke~ka¾dému celoèíselnému toku dovedeme najít systém disjunktních
189 cest (hladovì tok rozkládáme na~cesty a prùbì¾nì odstraòujeme cirkulace, které
190 objevíme). Pak pou¾ijeme F-F vìtu.
193 \s{Vìta (Mengerova, lokální vrcholová orientovaná):}
194 Buï $G$ orientovaný graf a $s,t$ nìjaké jeho vrcholy takové, ¾e $st\not\in E$.
195 Pak je velikost minimálního $st$-separátoru rovna maximálnímu poètu vrcholovì
196 disjunktních $st$-cest.\foot{Tím myslíme cesty disjunktní a¾ na~krajní vrcholy.}
198 \proof Podobnì jako v~dùkazu pøedchozí vìty zkonstruujeme vhodnou sí».
199 Tentokrát ov¹em rozdìlíme ka¾dý vrchol na~vrcholy $v^+$ a $v^-$, v¹echny hrany, které
200 pùvodnì vedly do~$v$, pøepojíme do~$v^+$, hrany vedoucí z~$v$ povedou z~$v^-$
201 a pøidáme novou hranu z~$v^+$ do~$v^-$. V¹echny hrany budou mít jednotkové kapacity.
202 Toky nyní odpovídají vrcholovì disjunktním cestám, øezy v~síti separátorùm.
205 \figure{vertex-split.eps}{Rozdìlení vrcholu}{\epsfxsize}
207 Podobnì dostaneme neorientované lokální vìty (neorientovanou hranu nahradíme
208 orientovanými v~obou smìrech) a z~nich pak i globální varianty popisující
209 $k$-souvislost grafù:
211 \s{Vìta (Mengerova, globální hranová neorientovaná):}
212 Neorientovaný graf~$G$ je hranovì $k$-souvislý právì tehdy, kdy¾ mezi ka¾dými
213 dvìma vrcholy existuje alespoò~$k$ hranovì disjunktních cest.
215 \s{Vìta (Mengerova, globální vrcholová neorientovaná):}
216 Neorientovaný graf~$G$ je vrcholovì $k$-souvislý právì tehdy, kdy¾ mezi ka¾dými dvìma
217 vrcholy existuje alespoò~$k$ vrcholovì disjunktních cest.
219 \h{Maximální párování v bipartitním grafu}
221 Jiným problémem, který lze snadno pøevést na~hledání maximálního toku, je nalezení
222 {\I maximálního párování} v~bipartitním grafu, tedy mno¾iny hran takové, ¾e ¾ádné
223 dvì hrany nemají spoleèný vrchol. Maximálním míníme vzhledem k~poètu hran,
224 nikoliv vzhledem k~inkluzi.
226 Z~bipartitního grafu $(A\cup B, E)$ sestrojíme sí» obsahující v¹echny pùvodní vrcholy
227 a navíc dva nové vrcholy $s$ a~$t$, dále pak v¹echny pùvodní hrany orientované z~$A$ do~$B$,
228 nové hrany z~$s$ do~v¹ech vrcholù partity~$A$ a ze~v¹ech vrcholù partity~$B$ do~$t$.
229 Kapacity v¹ech hran nastavíme na jednièky:
231 \fig{bipartitni.eps}{0.4\hsize}
233 Nyní si v¹imneme, ¾e párování v~pùvodním grafu odpovídají celoèíselným tokùm v~této síti
234 a ¾e velikost toku je rovna velikosti párování. Staèí tedy nalézt maximální celoèíselný
235 tok (tøeba F-F algoritmem) a do~párování umístit ty hrany, po~kterých nìco teèe.
237 Podobnì mù¾eme najít souvislost mezi øezy v~této síti a {\I vrcholovými pokrytími}
238 zadaného grafu -- to jsou mno¾iny vrcholù takové, ¾e se dotýkají ka¾dé hrany.
239 Tak z~F-F vìty získáme jinou standardní vìtu:
241 \s{Vìta (Königova):} V~ka¾dém bipartitním grafu je velikost maximálního párování
242 rovna velikosti minimálního vrcholového pokrytí.
245 Pokud je $W$ vrcholové pokrytí, musí hrany vedoucí mezi vrcholy této mno¾iny a zdrojem
246 a spotøebièem tvoøit stejnì velký øez, proto¾e ka¾dá $st$-cesta obsahuje alespoò
247 jednu hranu bipartitního grafu a ta je pokryta. Analogicky vezmeme-li libovolný
248 $st$-øez (ne~nutnì tokový, staèí hranový), mù¾eme ho bez zvìt¹ení upravit na~$st$-øez
249 pou¾ívající pouze hrany ze~$s$ a do~$t$, kterému pøímoèaøe odpovídá vrcholové pokrytí