-\input ../sgr.tex\r
-\r
-\prednaska{1}{Toky, øezy a Ford-Fulkersonùv algoritmus}{zapsal Radovan ©esták}\r
-\r
-V~této kapitole nadefinujeme toky v~sítích, øezy a související pojmy a uká¾eme\r
-Ford-Fulkersonùv algoritmus na nalezení maximálního toku. Dal¹í algoritmy budou\r
-následovat v~pøí¹tích kapitolách.\r
-\r
-\todo{Tady (nebo nìkde jinde poblí¾) by mìly být zavedeny základní znaèky.}\r
-\r
-\todo{Co je $V$, $E$, $m$, $n$ \dots}\r
-\r
-\h{Toky v sítích}\r
-\r
-Intuitivní pohled: sí» je systém propojených potrubí, který pøepravuje tekutinu\r
-ze~zdroje~$s$ (source) do~spotøebièe~$t$ (target), pøièem¾ tekutina\r
-se nikde mimo tato dvì místa neztrácí ani nevzniká.\r
-\r
-\s{Definice:}\r
-\r
-\itemize\ibull\r
-\:{\I Sí»} je uspoøádaná pìtice $(V,E,s,t,c)$, kde:\r
- \itemize\ibull\r
- \:$(V,E)$ je orientovaný graf,\r
- \:$s\in V$ {\I zdroj,}\r
- \:$t\in V$ {\I stok,} a\r
- \:$c: E\rightarrow {\bb R}^+$ funkce udávající {\I kapacity} jednotlivých hran.\r
- \endlist\r
-\:{\I Ohodnocení} hran je libovolná funkce $f:\, E\rightarrow {\bb R}$. Pro ka¾dé ohodnocení $f$\r
- mù¾eme definovat:\r
- $$ f^+(v) = \sum_{e=(\cdot,w)} f(e), \quad\r
- f^-(v) = \sum_{e=(w,\cdot)} f(e), \quad\r
- f^\Delta(v) = f^+(v) - f^-(v)\r
- $$\r
- [intuitivnì: co do~vrcholu pøiteèe, co odteèe a jaký je v~nìm pøebytek].\r
-\:{\I Tok} je ohodnocení $f:\, E\rightarrow {\bb R}$, pro které platí:\r
- \itemize\ibull\r
- \:$\forall e: 0 \le f(e) \le w(e)$, \quad {\I (dodr¾uje kapacity)}\r
- \:$\forall v\ne s,t: f^\Delta(v)=0$. \quad {\I (Kirchhoffùv zákon)}\r
- \endlist\r
-\:{\I Velikost toku:} $\vert f \vert = -f^\Delta(s)$.\r
-\:{\I Øez (tokový):} mno¾ina vrcholù $C\subset V$ taková, ¾e $s\in C$, $t\not\in C$. Øez mù¾eme také\r
- ztoto¾nit s~mno¾inami hran $E \cap (C \times \overline C)$ [tìm budeme øíkat hrany zleva doprava a budeme\r
- je znaèit $C^-$] a $E \cap (\overline C \times C)$ [hrany zprava doleva, tedy $C^+$].\r
-\:{\I Kapacita øezu:} $\vert C \vert = \sum_{e \in C^-} c(e)$ (bereme v~úvahu jen hrany zleva doprava).\r
-\:{\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
-\:{\I Cirkulace} je nulový tok, èili $\forall v: f^\Delta(v)=0$.\r
-\endlist\r
-\r
-\figure{graf.eps}{Pøíklad orientovaného grafu ze zvoleným zdrojem a stokem.}{0.4\hsize}\r
-\r
-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
-velikosti) a {\I minimálního øezu} (øezu nejmen¹í mo¾né kapacity).\r
-\r
-\s{Vìtièka:} V~ka¾dé síti existuje maximální tok a minimální øez.\r
-\r
-\s{Dùkaz:} Existence minimálního øezu je triviální, proto¾e øezù v~ka¾dé síti je koneènì mnoho;\r
-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
-analýzy (v~prostoru v¹ech ohodnocení hran tvoøí toky kompaktní mno¾inu, velikost toku je lineární funkce,\r
-a~tedy i spojitá, proèe¾ nabývá maxima). Pro racionální kapacity dostaneme tuto vìtièku jako dùsledek\r
-analýzy Ford-Fulkersonova algoritmu.\r
-\r
-\s{Pozorování:} Kdybychom velikost toku definovali podle spotøebièe, vy¹lo by toté¾:\r
-$$\eqalign{\r
-\sum_v f^\Delta(v) &= f^\Delta(s) + f^\Delta(t) \hbox{~~~(podle Kirchhoffova zákona), ale také:} \cr\r
-\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
-}$$\r
-tak¾e $\vert f\vert = -f^\Delta(s) = f^\Delta(t).$\r
-\r
-Stejnì tak mù¾eme velikost toku zmìøit na~libovolném øezu:\r
-\r
-\s{Lemma:} Pro ka¾dý øez $C$ platí, ¾e $\vert f\vert = -f^\Delta(C) \le \vert C \vert$.\r
-\r
-\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
-[tedy pøesouváním vrcholu zprava doleva], a~to, jak uká¾e jednoduchý rozbor pøípadù, nezmìní $f^\Delta$.\r
-Druhá èást: $-f^\Delta(C) = f^-(C) - f^+(C) \le f^-(c) \le \vert C \vert.$ \qed\r
-\r
-Velikost ka¾dého toku mù¾eme tedy omezit kapacitou libovolného øezu. Kdybychom na¹li tok a øez stejné\r
-velikosti, mù¾eme si tedy být jisti, ¾e tok je maximální a øez minimální. To není náhoda, platí toti¾\r
-následující vìta:\r
-\r
-\s{Vìta (Ford, Fulkerson):} V~ka¾dé síti je velikost maximálního toku rovna velikosti minimálního øezu.\r
-\r
-\s{Dùkaz:} Jednu nerovnost jsme dokázali v~pøedchozím lemmatu, druhá plyne z~duality lineárního\r
-programování [max. tok a min. øez jsou navzájem duální úlohy], ale k~pìknému kombinatorickému\r
-dùkazu pùjde opìt pou¾ít Ford-Fulkersonùv algoritmus.\r
-\r
-\h{Ford-Fulkersonùv algoritmus}\r
-\r
-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
-a postupnì ho zlep¹ovat tak, ¾e nalezneme nìjakou nenasycenou cestu a po¹leme po~ní \uv{co pùjde}.\r
-To~bohu¾el nefunguje, ale mù¾eme tento postup trochu zobecnit a být ochotni pou¾ívat nejen hrany,\r
-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
-v~na¹em smìru simulovat odeètením od~toku v~protismìru. Trochu formálnìji:\r
-\r
-\s{Definice:}\r
-\r
-\itemize\ibull\r
-\:{\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
- Pro úèely tohoto algoritmu budeme pøedpokládat, ¾e ke~ka¾dé hranì hrana opaèná existuje; pokud ne, dodefinujeme\r
- si ji s~nulovou kapacitou.\r
-\:{\I Zlep¹ující cesta} je orientovaná cesta taková, ¾e v¹echny její hrany mají nenulovou rezervu.\r
-\endlist\r
-\r
-\s{Algoritmus:}\r
-\r
-\algo\r
-\:$f \leftarrow 0$\r
-\:while $\exists$ zlep¹ující cesta $P$ z~$s$ do~$t$\r
-\::$m=\min_{e\in P} r(P)$\r
-\::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
-\endalgo\r
-\r
-\s{Analýza:} Nejdøíve si rozmysleme, ¾e pro celoèíselné kapacity algoritmus v¾dy dobìhne: v~ka¾dém kroku\r
-stoupne velikost toku o~$m \ge 1$, co¾ mù¾e nastat pouze koneènìkrát. Podobnì pro racionální kapacity:\r
-pøenásobíme-li v¹echny kapacity jejich spoleèným jmenovatelem, dostaneme sí» s~celoèíselnými kapacitami,\r
-na~které se bude algoritmus chovat identicky a jak ji¾ víme, skonèí. Pro~iracionální kapacity obecnì\r
-dobìhnout nemusí, zkuste vymyslet protipøíklad.\r
-\r
-Uva¾me nyní situaci po~zastavení algoritmu. Funkce~$f$ je urèitì tok, proto¾e jím byla po~celou dobu\r
-bìhu algoritmu. Prozkoumejme teï mno¾inu $C$ vrcholù, do~nich¾ po~zastavení algoritmu vede zlep¹ující cesta ze~zdroje.\r
-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
-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
-nulová. Tak¾e $f^-(C) = \vert C \vert$ a $f^+(C) = 0$, èili $\vert f\vert = \vert C \vert$.\r
-\r
-Na¹li jsme tedy k~toku, který algoritmus vydal, øez stejné velikosti, tak¾e jak u¾ víme,\r
-tok je maximání a øez minimální. Tím jsme také dokázali Ford-Fulkersonovu vìtu (dokonce\r
-i pro obecné reálné kapacity, proto¾e mù¾eme algoritmus spustit na maximální tok místo nulového\r
-a on se ihned zastaví a vydá certifikující øez). Navíc algoritmus nikdy nevytváøí z~celých\r
-èísel necelá, èim¾ získáme:\r
-\r
-\s{Dùsledek:} Sí» s~celoèíselnými kapacitami má maximální tok, který je celoèíselný.\r
-\r
-\s{Èasová slo¾itost} F-F algoritmu mù¾e být pro obecné sítì a ne¹ikovnou volbu zlep¹ujících\r
-cest obludná, ale jak dokázali Edmonds s~Karpem, pokud budeme hledat cesty prohledáváním\r
-do~¹íøky (co¾ je asi nejpøímoèaøej¹í implementace), pobì¾í v~èase $O(m^2n)$. Pokud budou\r
-v¹echny kapacity jednotkové, snadno nahlédneme, ¾e staèí $O(nm)$.\r
-\r
-\h{Maximální párování v bipartitním grafu}\r
-\r
-Jedním z~problémù, které lze snadno pøevést na~hledání maximálního toku, je nalezení\r
-maximálního {\I párování} v~bipartitním grafu (to je mno¾ina hran taková, ¾e ¾ádné\r
-dvì nemají spoleèný vrchol).\r
-\r
-Bipartitní graf $(A\cup B, E)$ pøevedeme na sí» obsahující v¹echny pùvodní vrcholy\r
-plus dva nové vrcholy $s$ a~$t$, v¹echny pùvodní hrany orientované z~$A$ do~$B$,\r
-nové hrany z~$s$ do~v¹ech vrcholù partity~$A$ a ze~v¹ech vrcholù partity~$B$ do~$t$.\r
-Kapacity v¹ech hran nastavíme na jednièky.\r
-\r
-Nyní si v¹imneme, ¾e ke~ka¾dému párování existuje celoèíselný tok stejné velikosti a naopak.\r
-Tak¾e najdeme maximální celoèíselný tok (tøeba F-F algoritmem) a do~párování umístíme\r
-právì hrany, po~kterých nìco teèe.\r
-\r
-Podobnì mù¾eme najít souvislost mezi øezy v~této síti a {\I vrcholovými pokrytími}\r
-zadaného grafu -- to jsou mno¾iny vrcholù takové, ¾e se dotýkají ka¾dé hrany.\r
-Tak z~F-F vìty získáme:\r
-\r
-\s{Vìta (König):} V~ka¾dém bipartitním grafu je velikost maximálního párování\r
-rovna velikosti minimálního vrcholového pokrytí.\r
-\r
-\figure{bip-graf.eps}{Bipartitní graf pro který hledáme maximální párování.}{0.2\hsize}\r
-\figure{bip-tok.eps}{Sí», ve~které najdeme maximální tok.}{0.3\hsize}\r
-\r
-\h{Øezy, separátory a $k$-souvislost}\r
-\r
-\s{Definice:} Pro ka¾dý neorientovaný graf $G$ a libovolné jeho vrcholy $s,t$ zavedeme:\r
-\itemize\ibull\r
-\:{\I $st$-øez} je mno¾ina hran $F$ taková, ¾e v~grafu $G-F$ budou\r
- vrcholy $s,t$ v~rùzných komponentách souvislosti.\r
-\:{\I $st$-separátor} je mno¾ina vrcholù $W$ taková, ¾e $s,t\not\in W$ a v~grafu $G-W$\r
- budou vrcholy $s,t$ v~rùzných komponentách souvislosti.\r
-\:{\I Øez} je mno¾ina hran, která je $xy$-øezem pro nìjakou dvojici vrcholù $x,y$.\r
-\:{\I Separátor} je mno¾ina vrcholù, která je $xy$-separátorem pro nìjakou dvojici vrcholù $x,y$.\r
-\:$G$ je {\I hranovì $k$-souvislý,} pokud $\vert V\vert > k$ a v¹echny øezy v~$G$\r
- mají více ne¾~$k$ hran.\r
-\:$G$ je {\I vrcholovì $k$-souvislý,} pokud $\vert V\vert > k$ a v¹echny separátory v~$G$\r
-\endlist\r
-\r
-V¹imnìte si, ¾e nesouvislý graf má øez i separátor velikosti~0, tak¾e vrcholová i hranová 1-souvislost\r
-splývají s~obyèejnou souvislostí pro v¹echny grafy o~alespoò dvou vrcholech. Hranovì 2-souvislé\r
-jsou právì (netriviální) grafy bez {\I mostù,} vrcholovì 2-souvislé jsou ty bez {\I artikulací.}\r
-\r
-Pro orientované grafy mù¾eme $st$-øezy a $st$-separátory definovat analogicky\r
-(toti¾, ¾e po~odstranìní pøíslu¹né mno¾iny hran èi vrcholù nemá existovat orientovaná\r
-cesta z~$s$ do~$t$), globální øezy a separátory ani vícenásobná souvislost se obvykle\r
-nedefinují.\r
-\r
-\s{Pozorování:} Minimální orientované $st$-øezy podle této definice a minimální tokové øezy\r
-podle definice ze~zaèátku kapitoly splývají: ka¾dý tokový øez~$C$ odpovídá $st$-øezu stejné\r
-velikosti tvoøenému hranami v~$C^-$; naopak pro~minimální $st$-øez musí být mno¾ina\r
-vrcholù dosa¾itelných z~$s$ po~odebrání øezu z~grafu tokovým øezem, opìt stejné velikosti.\r
-[Velikost mìøíme souètem kapacit hran.] Dává tedy rozumný smysl øíkat obojímu stejnì.\r
-Podobnì se chovají i neorientované grafy, pokud do~\uv{tokového} øezu poèítáme\r
-hrany v~obou smìrech.\r
-\r
-Analogií tokù je pak existence nìjakého poètu disjunktních cest (vrcholovì nebo hranovì)\r
-mezi vrcholy~$s$ a~$t$. Analogií F-F~vìty pak budou známé Mengerovy vìty:\r
-\r
-\s{Vìta (Mengerova, lokální hranová orientovaná):}\r
-Buï $G$ orientovaný graf a $s,t$ nìjaké jeho vrcholy. Pak je velikost minimálního\r
-$st$-øezu rovna maximálnímu poètu hranovì disjunktních $st$-cest.\foot{orientovaných\r
-cest z~$s$ do~$t$}\r
-\r
-\s{Dùkaz:} TODO\r
-\r
-\s{Vìta (Mengerova, lokální vrcholová orientovaná):}\r
-Buï $G$ orientovaný graf a $s,t$ nìjaké jeho vrcholy takové, ¾e $st\not\in E$.\r
-Pak je velikost minimálního $st$-separátoru rovna maximálnímu poètu vrcholovì\r
-disjunktních $st$-cest.\foot{Tím myslíme cesty disjunktní a¾ na~krajní vrcholy.}\r
-\r
-\s{Dùkaz:} TODO\r
-\r
-\figure{vrchol.eps}{Vrchol který chceme podrozdìlit.}{0.1\hsize}\r
-\figure{podrozdeleni.eps}{Výsledek podrozdìlení vrcholu.}{0.15\hsize}\r
-\r
-Podobnì dostaneme neorientované lokální vìty a z~nich pak i globální varianty\r
-popisující $k$-souvislost grafù:\r
-\r
-\s{Vìta (Mengerova, globální hranová neorientovaná):}\r
-Neorientovaný graf~$G$ je hranovì $k$-souvislý právì tehdy, kdy¾ mezi ka¾dými\r
-dvìma vrcholy existuje alespoò~$k$ hranovì disjunktních cest.\r
-\r
-\s{Vìta (Mengerova, globální vrcholová neorientovaná):}\r
-Neorientovaný graf~$G$ je vrcholovì $k$-souvislý právì tehdy, kdy¾ mezi ka¾dými dvìma\r
-vrcholy existuje alespoò~$k$ vrcholovì disjunktních cest.\r
-\r
-\bye\r
+\input ../sgr.tex
+
+\prednaska{1}{Toky, øezy a Ford-Fulkersonùv algoritmus}{zapsal Radovan ©esták}
+
+V~této kapitole nadefinujeme toky v~sítích, odvodíme základní vìty o~nich
+a Ford-Fulkersonùv algoritmus pro hledání maximálního toku. Také uká¾eme,
+jak na~hledání maximálního toku pøevést problémy týkající se øezù, separátorù
+a párování. Dal¹í algoritmy budou následovat v~pøí¹tích kapitolách.
+
+\todo{Tady (nebo nìkde poblí¾) by mìly být zavedeny základní znaèky.}
+
+\todo{Co je $V$, $E$, $m$, $n$, komplementy, multihrany, WLOG souvislost \dots}
+
+\h{Toky v sítích}
+
+Intuitivní pohled: sí» je systém propojených potrubí, který pøepravuje tekutinu
+ze~zdroje~$s$ (source) do~spotøebièe~$t$ (target), pøièem¾ tekutina
+se nikde mimo tato dvì místa neztrácí ani nevzniká.
+
+\s{Definice:}
+
+\itemize\ibull
+\:{\I Sí»} je uspoøádaná pìtice $(V,E,s,t,c)$, kde:
+ \itemize\ibull
+ \:$(V,E)$ je orientovaný graf,
+ \:$s\in V$ {\I zdroj,}
+ \:$t\in V$ {\I spotøebiè} neboli {\I stok} a
+ \:$c: E\rightarrow {\bb R}^+$ funkce udávající {\I kapacity} jednotlivých hran.
+ \endlist
+\:{\I Ohodnocení} hran je libovolná funkce $f:\, E\rightarrow {\bb R}$. Pro ka¾dé ohodnocení $f$
+ mù¾eme definovat:
+ $$ f^+(v) = \sum_{e=(\cdot,w)} f(e), \quad
+ f^-(v) = \sum_{e=(w,\cdot)} f(e), \quad
+ f^\Delta(v) = f^+(v) - f^-(v)
+ $$
+ [co do~vrcholu pøiteèe, co odteèe a jaký je v~nìm pøebytek].
+\:{\I Tok} je ohodnocení $f:\, E\rightarrow {\bb R}$, pro které platí:
+ \itemize\ibull
+ \:$\forall e: 0 \le f(e) \le w(e)$, \quad {\I (dodr¾uje kapacity)}
+ \:$\forall v\ne s,t: f^\Delta(v)=0$. \quad {\I (Kirchhoffùv zákon)}
+ \endlist
+\:{\I Velikost toku:} $\vert f \vert = -f^\Delta(s)$.
+\:{\I Øez (tokový):} mno¾ina vrcholù $C\subset V$ taková, ¾e $s\in C$, $t\not\in C$. Øez mù¾eme také
+ ztoto¾nit s~mno¾inami hran $C^- = E \cap (C \times \overline C)$ [tìm budeme øíkat hrany zleva doprava]
+ a $C^+ = E \cap (\overline C \times C)$ [hrany zprava doleva].
+\:{\I Kapacita øezu:} $\vert C \vert = \sum_{e \in C^-} c(e)$ (bereme v~úvahu jen hrany zleva doprava).
+\:{\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)$.
+\:{\I Cirkulace} je nulový tok, èili $\forall v: f^\Delta(v)=0$.
+\endlist
+
+%%%\figure{graf.eps}{Pøíklad orientovaného grafu ze zvoleným zdrojem a stokem.}{0.4\hsize}
+
+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é
+velikosti) a {\I minimálního øezu} (øezu nejmen¹í mo¾né kapacity).
+
+\s{Vìtièka:} V~ka¾dé síti existuje maximální tok a minimální øez.
+
+\s{Dùkaz:} Existence minimálního øezu je triviální, proto¾e øezù v~ka¾dé síti je koneènì mnoho;
+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é
+analýzy (v~prostoru v¹ech ohodnocení hran tvoøí toky kompaktní mno¾inu, velikost toku je lineární funkce
+a~tedy i spojitá, proèe¾ nabývá maxima). Pro racionální kapacity dostaneme tuto vìtièku jako dùsledek
+analýzy Ford-Fulkersonova algoritmu.
+\qed
+
+\s{Pozorování:} Kdybychom velikost toku definovali podle spotøebièe, vy¹lo by toté¾:
+$$\eqalign{
+\sum_v f^\Delta(v) &= f^\Delta(s) + f^\Delta(t) \hbox{~~~(podle Kirchhoffova zákona jsou v¹echna ostatní $f^\Delta(v)=0$), ale také:} \cr
+\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)$),}
+}$$
+tak¾e $\vert f\vert = -f^\Delta(s) = f^\Delta(t).$
+
+Stejnì tak mù¾eme velikost toku zmìøit na~libovolném øezu:
+
+\s{Lemma:} Pro ka¾dý øez $C$ platí, ¾e $\vert f\vert = -f^\Delta(C) \le \vert C \vert$.
+
+\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\}$
+[tedy pøesouváním vrcholù zprava doleva], a~to, jak uká¾e jednoduchý rozbor pøípadù, nezmìní $f^\Delta$.
+Druhá èást: $-f^\Delta(C) = f^-(C) - f^+(C) \le f^-(C) \le \vert C \vert.$ \qed
+
+Velikost ka¾dého toku mù¾eme tedy omezit kapacitou libovolného øezu. Kdybychom na¹li tok a øez stejné
+velikosti, mù¾eme si tedy být jisti, ¾e tok je maximální a øez minimální. To není náhoda, platí toti¾
+následující:
+
+\s{Vìta (Ford, Fulkerson):} V~ka¾dé síti je velikost maximálního toku rovna velikosti minimálního øezu.
+
+\s{Dùkaz:} Jednu nerovnost jsme dokázali v~pøedchozím lemmatu, druhá plyne z~duality lineárního
+programování [max. tok a min. øez jsou navzájem duální úlohy], ale k~pìknému kombinatorickému
+dùkazu pùjde opìt pou¾ít Ford-Fulkersonùv algoritmus.
+
+\h{Ford-Fulkersonùv algoritmus}
+
+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)
+a postupnì ho zlep¹ovat tak, ¾e nalezneme nìjakou nenasycenou cestu a po¹leme po~ní \uv{co pùjde}.
+To~bohu¾el nefunguje, ale mù¾eme tento postup trochu zobecnit a být ochotni pou¾ívat nejen hrany,
+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
+v~na¹em smìru simulovat odeètením od~toku v~protismìru. Trochu formálnìji:
+
+\s{Definice:}
+
+\itemize\ibull
+\:{\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)$.
+ Pro úèely tohoto algoritmu budeme pøedpokládat, ¾e ke~ka¾dé hranì hrana opaèná existuje; pokud ne, dodefinujeme
+ si ji s~nulovou kapacitou.
+\:{\I Zlep¹ující cesta} je orientovaná cesta taková, ¾e v¹echny její hrany mají nenulovou rezervu.
+\endlist
+
+\s{Algoritmus:}
+
+\algo
+\:$f \leftarrow \<nulový tok>$
+\:while $\exists$ zlep¹ující cesta $P$ z~$s$ do~$t$
+\::$m \leftarrow \min_{e\in P} r(e)$
+\::zvìt¹i tok $f$ podél~$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).
+\endalgo
+
+\s{Analýza:} Nejdøíve si rozmysleme, ¾e pro celoèíselné kapacity algoritmus v¾dy dobìhne: v~ka¾dém kroku
+stoupne velikost toku o~$m \ge 1$, co¾ mù¾e nastat pouze koneènìkrát. Podobnì pro racionální kapacity:
+pøenásobíme-li v¹echny kapacity jejich spoleèným jmenovatelem, dostaneme sí» s~celoèíselnými kapacitami,
+na~které se bude algoritmus chovat identicky a jak ji¾ víme, skonèí. Pro~iracionální kapacity obecnì
+dobìhnout nemusí, zkuste vymyslet protipøíklad.
+
+Uva¾me nyní situaci po~zastavení algoritmu. Funkce~$f$ je urèitì tok, proto¾e jím byla po~celou dobu
+bìhu algoritmu. Prozkoumejme teï mno¾inu $C$ vrcholù, do~nich¾ po~zastavení algoritmu vede zlep¹ující cesta ze~zdroje.
+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í
+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
+nulová. Tak¾e $f^-(C) = \vert C \vert$ a $f^+(C) = 0$, èili $\vert f\vert = \vert C \vert$.
+
+Na¹li jsme tedy k~toku, který algoritmus vydal, øez stejné velikosti, tak¾e, jak u¾ víme,
+tok je maximální a øez minimální. Tím jsme také dokázali Ford-Fulkersonovu vìtu\foot{Dokonce
+jsme ji dokázali i pro reálné kapacity, proto¾e mù¾eme algoritmus spustit rovnou na maximální tok místo
+nulového a on se ihned zastaví a vydá certifikující øez.} a existenci maximálního toku. Navíc algoritmus nikdy
+nevytváøí z~celých èísel necelá, èim¾ získáme:
+
+\s{Dùsledek:} Sí» s~celoèíselnými kapacitami má maximální tok, který je celoèíselný.
+
+\s{Èasová slo¾itost} F-F algoritmu mù¾e být pro obecné sítì a ne¹ikovnou volbu zlep¹ujících
+cest obludná, ale jak dokázali Edmonds s~Karpem, pokud budeme hledat cesty prohledáváním
+do~¹íøky (co¾ je asi nejpøímoèaøej¹í implementace), pobì¾í v~èase $\O(m^2n)$. Pokud budou
+v¹echny kapacity jednotkové, snadno nahlédneme, ¾e staèí $\O(nm)$. Edmondsùv a Karpùv
+odhad nebudeme dokazovat, místo toho si v~pøí¹tí kapitole pøedvedeme efektivnìj¹í algoritmus.
+
+\h{Maximální párování v bipartitním grafu}
+
+Jedním z~problémù, které lze snadno pøevést na~hledání maximálního toku, je nalezení
+{\I maximálního párování} v~bipartitním grafu\foot{Párování je mno¾ina hran taková, ¾e ¾ádné
+dvì nemají spoleèný vrchol. Maximálním míníme vzhledem k~poètu hran, nikoliv vzhledem k~inkluzi.}.
+
+Bipartitní graf $(A\cup B, E)$ pøevedeme na sí» obsahující v¹echny pùvodní vrcholy
+a navíc dva nové vrcholy $s$ a~$t$, dále v¹echny pùvodní hrany orientované z~$A$ do~$B$,
+nové hrany z~$s$ do~v¹ech vrcholù partity~$A$ a ze~v¹ech vrcholù partity~$B$ do~$t$.
+Kapacity v¹ech hran nastavíme na jednièky:
+
+\figure{bipartitni.eps}{Bipartitní graf a z~nìj odvozená sí» (v¹echny kapacity jsou jednièky).}{0.4\hsize}
+
+Nyní si v¹imneme, ¾e ke~ka¾dému párování existuje celoèíselný tok stejné velikosti a naopak.
+Tak¾e najdeme maximální celoèíselný tok (tøeba F-F algoritmem) a do~párování umístíme
+právì hrany, po~kterých nìco teèe.
+
+Podobnì mù¾eme najít souvislost mezi øezy v~této síti a {\I vrcholovými pokrytími}
+zadaného grafu -- to jsou mno¾iny vrcholù takové, ¾e se dotýkají ka¾dé hrany.
+Tak z~F-F vìty získáme:
+
+\s{Vìta (König):} V~ka¾dém bipartitním grafu je velikost maximálního párování
+rovna velikosti minimálního vrcholového pokrytí.
+
+\h{Øezy, separátory a $k$-souvislost}
+
+\s{Definice:} Pro ka¾dý neorientovaný graf $G$ a libovolné jeho vrcholy $s,t$ zavedeme:
+\itemize\ibull
+\:{\I $st$-øez} je mno¾ina hran $F$ taková, ¾e v~grafu $G-F$ jsou
+ vrcholy $s,t$ v~rùzných komponentách souvislosti.
+\:{\I $st$-separátor} je mno¾ina vrcholù $W$ taková, ¾e $s,t\not\in W$ a v~grafu $G-W$
+ jsou vrcholy $s,t$ v~rùzných komponentách souvislosti.
+\:{\I Øez} je mno¾ina hran, která je $xy$-øezem pro nìjakou dvojici vrcholù $x,y$.
+\:{\I Separátor} je mno¾ina vrcholù, která je $xy$-separátorem pro nìjakou dvojici vrcholù $x,y$.
+\:$G$ je {\I hranovì $k$-souvislý,} pokud $\vert V\vert > k$ a v¹echny øezy v~$G$
+ mají alespoò~$k$ hran.
+\:$G$ je {\I vrcholovì $k$-souvislý,} pokud $\vert V\vert > k$ a v¹echny separátory v~$G$
+ mají alespoò~$k$ vrcholù.
+\endlist
+
+V¹imnìte si, ¾e nesouvislý graf má øez i separátor velikosti~0, tak¾e vrcholová i hranová 1-souvislost
+splývají s~obyèejnou souvislostí pro v¹echny grafy o~alespoò dvou vrcholech. Hranovì 2-souvislé
+jsou právì (netriviální) grafy bez {\I mostù,} vrcholovì 2-souvislé jsou ty bez {\I artikulací.}
+
+Pro orientované grafy mù¾eme $st$-øezy a $st$-separátory definovat analogicky
+(toti¾, ¾e po~odstranìní pøíslu¹né mno¾iny hran èi vrcholù neexistuje orientovaná
+cesta z~$s$ do~$t$), globální øezy a separátory ani vícenásobná souvislost se obvykle
+nedefinují.
+
+\s{Poznámka:} Minimální orientované $st$-øezy podle této definice a minimální tokové øezy
+podle definice ze~zaèátku kapitoly splývají: ka¾dý tokový øez~$C$ odpovídá $st$-øezu stejné
+velikosti tvoøenému hranami v~$C^-$; naopak pro~minimální $st$-øez musí být mno¾ina
+vrcholù dosa¾itelných z~$s$ po~odebrání øezu z~grafu tokovým øezem, opìt stejné velikosti.
+[Velikost mìøíme souètem kapacit hran.] Dává tedy rozumný smysl øíkat obojímu stejnì.
+Podobnì se chovají i neorientované grafy, pokud do~\uv{tokového} øezu poèítáme
+hrany v~obou smìrech.
+
+Analogií tokù je pak existence nìjakého poètu disjunktních cest (vrcholovì nebo hranovì)
+mezi vrcholy~$s$ a~$t$. Analogií F-F~vìty pak budou známé Mengerovy vìty:
+
+\s{Vìta (Mengerova, lokální hranová orientovaná):}
+Buï $G$ orientovaný graf a $s,t$ nìjaké jeho vrcholy. Pak je velikost minimálního
+$st$-øezu rovna maximálnímu poètu hranovì disjunktních $st$-cest.\foot{orientovaných
+cest z~$s$ do~$t$}
+
+\s{Dùkaz:} Z~grafu sestrojíme sí» tak, ¾e $s$~bude zdroj, $t$~spotøebiè a v¹em
+hranám nastavíme kapacitu na~jednotku. Øezy v~této síti odpovídají øezùm v~pùvodním
+grafu. Podobnì ka¾dý systém hranovì disjunktních $st$-cest odpovídá toku stejné
+velikosti a naopak ke~ka¾dému celoèíselnému toku dovedeme najít systém disjunktních
+cest (hladovì tok rozkládáme na~cesty a prùbì¾nì odstraòujeme cirkulace, které
+objevíme). Pak pou¾ijeme F-F vìtu.
+\qed
+
+\s{Vìta (Mengerova, lokální vrcholová orientovaná):}
+Buï $G$ orientovaný graf a $s,t$ nìjaké jeho vrcholy takové, ¾e $st\not\in E$.
+Pak je velikost minimálního $st$-separátoru rovna maximálnímu poètu vrcholovì
+disjunktních $st$-cest.\foot{Tím myslíme cesty disjunktní a¾ na~krajní vrcholy.}
+
+\s{Dùkaz:} Podobnì jako v~dùkazu pøedchozí vìty zkonstruujeme vhodnou sí».
+Tentokrát ov¹em rozdìlíme ka¾dý vrchol na~vrcholy $v^+$ a $v^-$, v¹echny hrany, které
+pùvodnì vedly do~$v$, pøepojíme do~$v^+$, hrany vedoucí z~$v$ povedou z~$v^-$
+a pøidáme novou hranu z~$v^+$ do~$v^-$. V¹echny hrany budou mít jednotkové kapacity.
+Toky nyní odpovídají vrcholovì disjunktním cestám, øezy v~síti separátorùm.
+\qed
+
+%\figure{vrchol.eps}{Vrchol který chceme podrozdìlit.}{0.1\hsize}
+%\figure{podrozdeleni.eps}{Výsledek podrozdìlení vrcholu.}{0.15\hsize}
+
+Podobnì dostaneme neorientované lokální vìty (neorientovanou hranu nahradíme
+orientovanými v~obou smìrech) a z~nich pak i globální varianty popisující
+$k$-souvislost grafù:
+
+\s{Vìta (Mengerova, globální hranová neorientovaná):}
+Neorientovaný graf~$G$ je hranovì $k$-souvislý právì tehdy, kdy¾ mezi ka¾dými
+dvìma vrcholy existuje alespoò~$k$ hranovì disjunktních cest.
+
+\s{Vìta (Mengerova, globální vrcholová neorientovaná):}
+Neorientovaný graf~$G$ je vrcholovì $k$-souvislý právì tehdy, kdy¾ mezi ka¾dými dvìma
+vrcholy existuje alespoò~$k$ vrcholovì disjunktních cest.
+
+\bye
projects / ga.git / blobdiff