3 \prednaska{1}{Toky, øezy a Ford-Fulkersonùv algoritmus}{zapsal Radovan ©esták}
\r
5 V~této kapitole nadefinujeme toky v~sítích, øezy a související pojmy a uká¾eme
\r
6 Ford-Fulkersonùv algoritmus na nalezení maximálního toku. Dal¹í algoritmy budou
\r
7 následovat v~pøí¹tích kapitolách.
\r
9 \todo{Tady (nebo nìkde jinde poblí¾) by mìly být zavedeny základní znaèky.}
\r
11 \todo{Co je $V$, $E$, $m$, $n$ \dots}
\r
15 Intuitivní pohled: sí» je systém propojených potrubí, který pøepravuje tekutinu
\r
16 ze~zdroje~$s$ (source) do~spotøebièe~$t$ (target), pøièem¾ tekutina
\r
17 se nikde mimo tato dvì místa neztrácí ani nevzniká.
\r
22 \:{\I Sí»} je uspoøádaná pìtice $(V,E,s,t,c)$, kde:
\r
24 \:$(V,E)$ je orientovaný graf,
\r
25 \:$s\in V$ {\I zdroj,}
\r
26 \:$t\in V$ {\I stok,} a
\r
27 \:$c: E\rightarrow {\bb R}^+$ funkce udávající {\I kapacity} jednotlivých hran.
\r
29 \:{\I Ohodnocení} hran je libovolná funkce $f:\, E\rightarrow {\bb R}$. Pro ka¾dé ohodnocení $f$
\r
31 $$ f^+(v) = \sum_{e=(\cdot,w)} f(e), \quad
\r
32 f^-(v) = \sum_{e=(w,\cdot)} f(e), \quad
\r
33 f^\Delta(v) = f^+(v) - f^-(v)
\r
35 [intuitivnì: co do~vrcholu pøiteèe, co odteèe a jaký je v~nìm pøebytek].
\r
36 \:{\I Tok} je ohodnocení $f:\, E\rightarrow {\bb R}$, pro které platí:
\r
38 \:$\forall e: 0 \le f(e) \le w(e)$, \quad {\I (dodr¾uje kapacity)}
\r
39 \:$\forall v\ne s,t: f^\Delta(v)=0$. \quad {\I (Kirchhoffùv zákon)}
\r
41 \:{\I Velikost toku:} $\vert f \vert = -f^\Delta(s)$.
\r
42 \:{\I Øez (tokový):} mno¾ina vrcholù $C\subset V$ taková, ¾e $s\in C$, $t\not\in C$. Øez mù¾eme také
\r
43 ztoto¾nit s~mno¾inami hran $E \cap (C \times \overline C)$ [tìm budeme øíkat hrany zleva doprava a budeme
\r
44 je znaèit $C^-$] a $E \cap (\overline C \times C)$ [hrany zprava doleva, tedy $C^+$].
\r
45 \:{\I Kapacita øezu:} $\vert C \vert = \sum_{e \in C^-} c(e)$ (bereme v~úvahu jen hrany zleva doprava).
\r
46 \:{\I Tok pøes øez:} $f^-(C)=\sum_{e \in C^-} f(e)$, $f^+(C)=\sum_{e\in C^+} f(e)$, $f^\Delta(C)=f^+(C)-f^-(C)$.
\r
47 \:{\I Cirkulace} je nulový tok, èili $\forall v: f^\Delta(v)=0$.
\r
50 \figure{graf.eps}{Pøíklad orientovaného grafu ze zvoleným zdrojem a stokem.}{0.4\hsize}
\r
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é
\r
53 velikosti) a {\I minimálního øezu} (øezu nejmen¹í mo¾né kapacity).
\r
55 \s{Vìtièka:} V~ka¾dé síti existuje maximální tok a minimální øez.
\r
57 \s{Dùkaz:} Existence minimálního øezu je triviální, proto¾e øezù v~ka¾dé síti je koneènì mnoho;
\r
58 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é
\r
59 analýzy (v~prostoru v¹ech ohodnocení hran tvoøí toky kompaktní mno¾inu, velikost toku je lineární funkce,
\r
60 a~tedy i spojitá, proèe¾ nabývá maxima). Pro racionální kapacity dostaneme tuto vìtièku jako dùsledek
\r
61 analýzy Ford-Fulkersonova algoritmu.
\r
63 \s{Pozorování:} Kdybychom velikost toku definovali podle spotøebièe, vy¹lo by toté¾:
\r
65 \sum_v f^\Delta(v) &= f^\Delta(s) + f^\Delta(t) \hbox{~~~(podle Kirchhoffova zákona), ale také:} \cr
\r
66 \sum_v f^\Delta(v) &= \sum_e f(e) - f(e) = 0 \hbox{~~~(ka¾dá hrana pøispìje k~jednomu $f^+(v)$ a k~jednomu $f^-(v)$),}
\r
68 tak¾e $\vert f\vert = -f^\Delta(s) = f^\Delta(t).$
\r
70 Stejnì tak mù¾eme velikost toku zmìøit na~libovolném øezu:
\r
72 \s{Lemma:} Pro ka¾dý øez $C$ platí, ¾e $\vert f\vert = -f^\Delta(C) \le \vert C \vert$.
\r
74 \s{Dùkaz:} První èást indukcí: ka¾dý øez mù¾eme získat postupným pøidáváním vrcholù do~triviálního øezu $\{s\}$
\r
75 [tedy pøesouváním vrcholu zprava doleva], a~to, jak uká¾e jednoduchý rozbor pøípadù, nezmìní $f^\Delta$.
\r
76 Druhá èást: $-f^\Delta(C) = f^-(C) - f^+(C) \le f^-(c) \le \vert C \vert.$ \qed
\r
78 Velikost ka¾dého toku mù¾eme tedy omezit kapacitou libovolného øezu. Kdybychom na¹li tok a øez stejné
\r
79 velikosti, mù¾eme si tedy být jisti, ¾e tok je maximální a øez minimální. To není náhoda, platí toti¾
\r
82 \s{Vìta (Ford, Fulkerson):} V~ka¾dé síti je velikost maximálního toku rovna velikosti minimálního øezu.
\r
84 \s{Dùkaz:} Jednu nerovnost jsme dokázali v~pøedchozím lemmatu, druhá plyne z~duality lineárního
\r
85 programování [max. tok a min. øez jsou navzájem duální úlohy], ale k~pìknému kombinatorickému
\r
86 dùkazu pùjde opìt pou¾ít Ford-Fulkersonùv algoritmus.
\r
88 \h{Ford-Fulkersonùv algoritmus}
\r
90 Nejpøímoèaøej¹í zpùsob, jak hledat toky v~sítích, je zaèít s~nìjakým tokem (nulový je po~ruce v¾dy)
\r
91 a postupnì ho zlep¹ovat tak, ¾e nalezneme nìjakou nenasycenou cestu a po¹leme po~ní \uv{co pùjde}.
\r
92 To~bohu¾el nefunguje, ale mù¾eme tento postup trochu zobecnit a být ochotni pou¾ívat nejen hrany,
\r
93 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
\r
94 v~na¹em smìru simulovat odeètením od~toku v~protismìru. Trochu formálnìji:
\r
99 \:{\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)$.
\r
100 Pro úèely tohoto algoritmu budeme pøedpokládat, ¾e ke~ka¾dé hranì hrana opaèná existuje; pokud ne, dodefinujeme
\r
101 si ji s~nulovou kapacitou.
\r
102 \:{\I Zlep¹ující cesta} je orientovaná cesta taková, ¾e v¹echny její hrany mají nenulovou rezervu.
\r
109 \:while $\exists$ zlep¹ující cesta $P$ z~$s$ do~$t$
\r
110 \::$m=\min_{e\in P} r(P)$
\r
111 \::zvìt¹i tok $f$ podle~$P$ o~$m$ (ka¾dé hranì $e\in P$ zvìt¹i $f(e)$, pøípadnì zmen¹i $f(e^\prime)$, podle toho, co jde)
\r
114 \s{Analýza:} Nejdøíve si rozmysleme, ¾e pro celoèíselné kapacity algoritmus v¾dy dobìhne: v~ka¾dém kroku
\r
115 stoupne velikost toku o~$m \ge 1$, co¾ mù¾e nastat pouze koneènìkrát. Podobnì pro racionální kapacity:
\r
116 pøenásobíme-li v¹echny kapacity jejich spoleèným jmenovatelem, dostaneme sí» s~celoèíselnými kapacitami,
\r
117 na~které se bude algoritmus chovat identicky a jak ji¾ víme, skonèí. Pro~iracionální kapacity obecnì
\r
118 dobìhnout nemusí, zkuste vymyslet protipøíklad.
\r
120 Uva¾me nyní situaci po~zastavení algoritmu. Funkce~$f$ je urèitì tok, proto¾e jím byla po~celou dobu
\r
121 bìhu algoritmu. Prozkoumejme teï mno¾inu $C$ vrcholù, do~nich¾ po~zastavení algoritmu vede zlep¹ující cesta ze~zdroje.
\r
122 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í
\r
123 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
\r
124 nulová. Tak¾e $f^-(C) = \vert C \vert$ a $f^+(C) = 0$, èili $\vert f\vert = \vert C \vert$.
\r
126 Na¹li jsme tedy k~toku, který algoritmus vydal, øez stejné velikosti, tak¾e jak u¾ víme,
\r
127 tok je maximání a øez minimální. Tím jsme také dokázali Ford-Fulkersonovu vìtu (dokonce
\r
128 i pro obecné reálné kapacity, proto¾e mù¾eme algoritmus spustit na maximální tok místo nulového
\r
129 a on se ihned zastaví a vydá certifikující øez). Navíc algoritmus nikdy nevytváøí z~celých
\r
130 èísel necelá, èim¾ získáme:
\r
132 \s{Dùsledek:} Sí» s~celoèíselnými kapacitami má maximální tok, který je celoèíselný.
\r
134 \s{Èasová slo¾itost} F-F algoritmu mù¾e být pro obecné sítì a ne¹ikovnou volbu zlep¹ujících
\r
135 cest obludná, ale jak dokázali Edmonds s~Karpem, pokud budeme hledat cesty prohledáváním
\r
136 do~¹íøky (co¾ je asi nejpøímoèaøej¹í implementace), pobì¾í v~èase $O(m^2n)$. Pokud budou
\r
137 v¹echny kapacity jednotkové, snadno nahlédneme, ¾e staèí $O(nm)$.
\r
139 \h{Maximální párování v bipartitním grafu}
\r
141 Jedním z~problémù, které lze snadno pøevést na~hledání maximálního toku, je nalezení
\r
142 maximálního {\I párování} v~bipartitním grafu (to je mno¾ina hran taková, ¾e ¾ádné
\r
143 dvì nemají spoleèný vrchol).
\r
145 Bipartitní graf $(A\cup B, E)$ pøevedeme na sí» obsahující v¹echny pùvodní vrcholy
\r
146 plus dva nové vrcholy $s$ a~$t$, v¹echny pùvodní hrany orientované z~$A$ do~$B$,
\r
147 nové hrany z~$s$ do~v¹ech vrcholù partity~$A$ a ze~v¹ech vrcholù partity~$B$ do~$t$.
\r
148 Kapacity v¹ech hran nastavíme na jednièky.
\r
150 Nyní si v¹imneme, ¾e ke~ka¾dému párování existuje celoèíselný tok stejné velikosti a naopak.
\r
151 Tak¾e najdeme maximální celoèíselný tok (tøeba F-F algoritmem) a do~párování umístíme
\r
152 právì hrany, po~kterých nìco teèe.
\r
154 Podobnì mù¾eme najít souvislost mezi øezy v~této síti a {\I vrcholovými pokrytími}
\r
155 zadaného grafu -- to jsou mno¾iny vrcholù takové, ¾e se dotýkají ka¾dé hrany.
\r
156 Tak z~F-F vìty získáme:
\r
158 \s{Vìta (König):} V~ka¾dém bipartitním grafu je velikost maximálního párování
\r
159 rovna velikosti minimálního vrcholového pokrytí.
\r
161 \figure{bip-graf.eps}{Bipartitní graf pro který hledáme maximální párování.}{0.2\hsize}
\r
162 \figure{bip-tok.eps}{Sí», ve~které najdeme maximální tok.}{0.3\hsize}
\r
164 \h{Øezy, separátory a $k$-souvislost}
\r
166 \s{Definice:} Pro ka¾dý neorientovaný graf $G$ a libovolné jeho vrcholy $s,t$ zavedeme:
\r
168 \:{\I $st$-øez} je mno¾ina hran $F$ taková, ¾e v~grafu $G-F$ budou
\r
169 vrcholy $s,t$ v~rùzných komponentách souvislosti.
\r
170 \:{\I $st$-separátor} je mno¾ina vrcholù $W$ taková, ¾e $s,t\not\in W$ a v~grafu $G-W$
\r
171 budou vrcholy $s,t$ v~rùzných komponentách souvislosti.
\r
172 \:{\I Øez} je mno¾ina hran, která je $xy$-øezem pro nìjakou dvojici vrcholù $x,y$.
\r
173 \:{\I Separátor} je mno¾ina vrcholù, která je $xy$-separátorem pro nìjakou dvojici vrcholù $x,y$.
\r
174 \:$G$ je {\I hranovì $k$-souvislý,} pokud $\vert V\vert > k$ a v¹echny øezy v~$G$
\r
175 mají více ne¾~$k$ hran.
\r
176 \:$G$ je {\I vrcholovì $k$-souvislý,} pokud $\vert V\vert > k$ a v¹echny separátory v~$G$
\r
179 V¹imnìte si, ¾e nesouvislý graf má øez i separátor velikosti~0, tak¾e vrcholová i hranová 1-souvislost
\r
180 splývají s~obyèejnou souvislostí pro v¹echny grafy o~alespoò dvou vrcholech. Hranovì 2-souvislé
\r
181 jsou právì (netriviální) grafy bez {\I mostù,} vrcholovì 2-souvislé jsou ty bez {\I artikulací.}
\r
183 Pro orientované grafy mù¾eme $st$-øezy a $st$-separátory definovat analogicky
\r
184 (toti¾, ¾e po~odstranìní pøíslu¹né mno¾iny hran èi vrcholù nemá existovat orientovaná
\r
185 cesta z~$s$ do~$t$), globální øezy a separátory ani vícenásobná souvislost se obvykle
\r
188 \s{Pozorování:} Minimální orientované $st$-øezy podle této definice a minimální tokové øezy
\r
189 podle definice ze~zaèátku kapitoly splývají: ka¾dý tokový øez~$C$ odpovídá $st$-øezu stejné
\r
190 velikosti tvoøenému hranami v~$C^-$; naopak pro~minimální $st$-øez musí být mno¾ina
\r
191 vrcholù dosa¾itelných z~$s$ po~odebrání øezu z~grafu tokovým øezem, opìt stejné velikosti.
\r
192 [Velikost mìøíme souètem kapacit hran.] Dává tedy rozumný smysl øíkat obojímu stejnì.
\r
193 Podobnì se chovají i neorientované grafy, pokud do~\uv{tokového} øezu poèítáme
\r
194 hrany v~obou smìrech.
\r
196 Analogií tokù je pak existence nìjakého poètu disjunktních cest (vrcholovì nebo hranovì)
\r
197 mezi vrcholy~$s$ a~$t$. Analogií F-F~vìty pak budou známé Mengerovy vìty:
\r
199 \s{Vìta (Mengerova, lokální hranová orientovaná):}
\r
200 Buï $G$ orientovaný graf a $s,t$ nìjaké jeho vrcholy. Pak je velikost minimálního
\r
201 $st$-øezu rovna maximálnímu poètu hranovì disjunktních $st$-cest.\foot{orientovaných
\r
206 \s{Vìta (Mengerova, lokální vrcholová orientovaná):}
\r
207 Buï $G$ orientovaný graf a $s,t$ nìjaké jeho vrcholy takové, ¾e $st\not\in E$.
\r
208 Pak je velikost minimálního $st$-separátoru rovna maximálnímu poètu vrcholovì
\r
209 disjunktních $st$-cest.\foot{Tím myslíme cesty disjunktní a¾ na~krajní vrcholy.}
\r
213 \figure{vrchol.eps}{Vrchol který chceme podrozdìlit.}{0.1\hsize}
\r
214 \figure{podrozdeleni.eps}{Výsledek podrozdìlení vrcholu.}{0.15\hsize}
\r
216 Podobnì dostaneme neorientované lokální vìty a z~nich pak i globální varianty
\r
217 popisující $k$-souvislost grafù:
\r
219 \s{Vìta (Mengerova, globální hranová neorientovaná):}
\r
220 Neorientovaný graf~$G$ je hranovì $k$-souvislý právì tehdy, kdy¾ mezi ka¾dými
\r
221 dvìma vrcholy existuje alespoò~$k$ hranovì disjunktních cest.
\r
223 \s{Vìta (Mengerova, globální vrcholová neorientovaná):}
\r
224 Neorientovaný graf~$G$ je vrcholovì $k$-souvislý právì tehdy, kdy¾ mezi ka¾dými dvìma
\r
225 vrcholy existuje alespoò~$k$ vrcholovì disjunktních cest.
\r
projects / ga.git / blob