\input ../sgr.tex
-\prednaska{1}{Toky, øezy a Fordùv-Fulkersonùv algoritmus}{}
+\prednaska{1}{Toky, řezy a Fordův-Fulkersonův algoritmus}{}
-V~této kapitole nadefinujeme toky v~sítích, odvodíme základní vìty o~nich
-a také Fordùv-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í v~bipartitních grafech. Dal¹í tokové algoritmy budou následovat v~pøí¹tích kapitolách.
+V~této kapitole nadefinujeme toky v~sítích, odvodíme základní věty o~nich
+a také Fordův-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í v~bipartitních grafech. Další tokové algoritmy budou následovat v~příštích kapitolách.
-\h{Toky v sítích}
+\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á.
+Intuitivní pohled: síť je systém propojených potrubí, který přepravuje tekutinu
+ze~zdroje~$s$ (source) do~spotÅ\99ebiÄ\8de~$t$ (target), pÅ\99iÄ\8demž tekutina
+se nikde mimo tato dvě místa neztrácí ani nevzniká.
\ss{Definice:}
\itemize\ibull
-\:{\I Sí»} je uspoøádaná pìtice $(V,E,s,t,c)$, kde:
+\:{\I Síť} je uspořádaná pětice $(V,E,s,t,c)$, kde:
\itemize\ibull
- \:$(V,E)$ je orientovaný graf,
+ \:$(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í nezáporné {\I kapacity} hran.
+ \:$t\in V$ {\I spotřebič} neboli {\I stok} a
+ \:$c: E\rightarrow {\bb R}$ funkce udávající nezáporné {\I kapacity} hran.
\endlist
-\:{\I Ohodnocení} hran je libovolná funkce $f:\, E\rightarrow {\bb R}$. Pro ka¾dé ohodnocení $f$
- mù¾eme definovat:
+\:{\I Ohodnocení} hran je libovolná funkce $f:\, E\rightarrow {\bb R}$. Pro každé ohodnocení $f$
+ můžeme definovat:
$$ f^+(v) = \sum_{e=(\cdot,v)} f(e), \quad
f^-(v) = \sum_{e=(v,\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í:
+ [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 c(e)$, \quad {\I (dodr¾uje kapacity)}
- \:$\forall v\ne s,t: f^\Delta(v)=0$. \quad {\I (Kirchhoffùv zákon)}
+ \:$\forall e: 0 \le f(e) \le c(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]
+\:{\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:}
+\:{\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 tok nulové velikosti, èili $f$ takové, ¾e $f^\Delta(v)=0$ pro v¹echna~$v$.
+\:{\I Cirkulace} je tok nulové velikosti, čili $f$ takové, že $f^\Delta(v)=0$ pro všechna~$v$.
\endlist
-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).
+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).
\goodbreak
-\s{Vìtièka:} V~ka¾dé síti existuje maximální tok a minimální øez.
+\s{Větička:} V~každé síti existuje maximální tok a minimální řez.
-\proof 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 Fordova-Fulkersonova algoritmu.
+\proof 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 Fordova-Fulkersonova algoritmu.
\qed
-\s{Pozorování:} Kdybychom velikost toku definovali podle spotøebièe, vy¹lo by toté¾. Platí toti¾:
+\s{PozorovánÃ:} Kdybychom velikost toku definovali podle spotÅ\99ebiÄ\8de, vyÅ¡lo by totéž. Platà totiž:
$$f^\Delta(s) + f^\Delta(t) = \sum_v f^\Delta(v) = \sum_e f(e) - f(e) = 0$$
-(první rovnost plyne z~Kirchhoffova zákona -- v¹echna ostatní $f^\Delta(v)$ jsou nulová; druhá pak z~toho,
-¾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).$
+(první rovnost plyne z~Kirchhoffova zákona -- všechna ostatní $f^\Delta(v)$ jsou nulová; druhá pak z~toho,
+ž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).$
-Stejnì tak mù¾eme velikost toku zmìøit na~libovolném øezu:
+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{Lemma:} Pro každý Å\99ez $C$ platÃ, že $\vert f\vert = -f^\Delta(C) \le \vert C \vert$.
-\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\}$
-[èili 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
+\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\}$
+[čili 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
-Víme tedy, ¾e velikost ka¾dého toku lze omezit kapacitou libovolného øezu. Kdybychom na¹li tok a øez stejné
-velikosti, mù¾eme si proto být jisti, ¾e tok je maximální a øez minimální. To se nám opravdu povede, platí toti¾
-následující vìta:
+Víme tedy, že velikost každého toku lze omezit kapacitou libovolného řezu. Kdybychom našli tok a řez stejné
+velikosti, můžeme si proto být jisti, že tok je maximálnà a Å\99ez minimálnÃ. To se nám opravdu povede, platà totiž
+následující věta:
-\s{Vìta (Ford, Fulkerson):} V~ka¾dé síti je velikost maximálního toku rovna velikosti minimálního øezu.
+\s{Věta (Ford, Fulkerson):} V~každé síti je velikost maximálního toku rovna velikosti minimálního řezu.
-\proof 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ùv-Fulkersonùv algoritmus.
+\proof 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ův-Fulkersonův algoritmus.
\qed
-\h{Fordùv-Fulkersonùv algoritmus}
+\h{Fordův-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:
+NejpÅ\99ÃmoÄ\8daÅ\99ejÅ¡Ã způsob, jak bychom mohli hledat toky v~sÃtÃch, je zaÄ\8dÃt s~nÄ\9bjaký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Ä\9bco teÄ\8de v~protismÄ\9bru a my můžeme tok
+v~našem směru simulovat odečtením od~toku v~protisměru. Trochu formálněji:
\ss{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ì existuje hrana opaèná; pokud ne, dodefinujeme
- si ji a dáme jí nulovou kapacitu.
-\:{\I Zlep¹ující cesta} je orientovaná cesta, její¾ v¹echny hrany mají nenulovou rezervu.
+\:{\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ě existuje hrana opačná; pokud ne, dodefinujeme
+ si ji a dáme jí nulovou kapacitu.
+\:{\I Zlepšující cesta} je orientovaná cesta, jejíž všechny hrany mají nenulovou rezervu.
\endlist
\ss{Algoritmus:}
\algo
-\:$f \leftarrow \<nulový tok>$.
-\:Dokud existuje zlep¹ující cesta $P$ z~$s$ do~$t$:
+\:$f \leftarrow \<nulový tok>$.
+\:Dokud existuje zlepšující cesta $P$ z~$s$ do~$t$:
\::$\varepsilon \leftarrow \min_{e\in P} r(e)$.
-\::Zvìt¹íme tok $f$ podél~$P$ o~$\varepsilon$ (ka¾dé hranì $e\in P$ zvìt¹íme $f(e)$, pøípadnì zmen¹íme $f(e^\prime)$, podle toho, co jde).
+\::Zvětšíme tok $f$ podél~$P$ o~$\varepsilon$ (každé hraně $e\in P$ zvětšíme $f(e)$, případně zmenšíme $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~$\varepsilon \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.
+\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~$\varepsilon \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$.
+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, a~proto, jak u¾ víme,
-je tok maximální a øez minimální. Tím jsme také dokázali Fordovu-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á, èím¾ získáme:
+Našli jsme tedy k~toku, který algoritmus vydal, řez stejné velikosti, a~proto, jak už víme,
+je tok maximální a řez minimální. Tím jsme také dokázali Fordovu-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á, čímž získáme:
-\s{Dùsledek:} Sí» s~celoèíselnými kapacitami má maximální tok, který je celoèíselný.
+\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.
+\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{Øezy, separátory a $k$-souvislost}
+\h{Řezy, separátory a $k$-souvislost}
-Teorie tokù nám rovnì¾ poslou¾í ke~zkoumání násobné souvislosti grafù.
+Teorie toků nám rovněž poslouží ke~zkoumání násobné souvislosti grafů.
-\s{Definice:} Pro ka¾dý neorientovaný graf $G$ a libovolné jeho vrcholy $s,t$ zavedeme:
+\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ù.
+\:{\I $st$-Å\99ez} 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 nulové velikosti, 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
+Všimněte si, že nesouvislý graf má řez i separátor nulové velikosti, 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Å\99enému hranami v~$C^-$; naopak pro~minimálnà $st$-Å\99ez 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$}
-\proof 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.
+\proof 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{Věta (Mengerova, lokální vrcholová orientovaná):}
+BuÄ\8f $G$ orientovaný graf a $s,t$ nÄ\9bjaké 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.}
-\proof 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.
+\proof 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{vertex-split.eps}{Rozdìlení vrcholu}{\epsfxsize}
+\figure{vertex-split.eps}{Rozdělení vrcholu}{\epsfxsize}
-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ù:
+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í 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.
+\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.
-\h{Maximální párování v bipartitním grafu}
+\h{Maximální párování v bipartitním grafu}
-Jiným problémem, 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, tedy mno¾iny hran takové, ¾e ¾ádné
-dvì hrany nemají spoleèný vrchol. Maximálním míníme vzhledem k~poètu hran,
+Jiným problémem, 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, tedy množiny hran takové, že žádné
+dvě hrany nemají společný vrchol. Maximálním míníme vzhledem k~počtu hran,
nikoliv vzhledem k~inkluzi.
-Z~bipartitního grafu $(A\cup B, E)$ sestrojíme sí» obsahující v¹echny pùvodní vrcholy
-a navíc dva nové vrcholy $s$ a~$t$, dále pak 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:
+Z~bipartitního grafu $(A\cup B, E)$ sestrojíme síť obsahující všechny původní vrcholy
+a navíc dva nové vrcholy $s$ a~$t$, dále pak 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:
\fig{bipartitni.eps}{0.4\hsize}
-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
-a ¾e velikost toku je rovna velikosti párování. Staèí tedy nalézt maximální celoèíselný
-tok (tøeba F-F algoritmem) a do~párování umístit ty hrany, po~kterých nìco teèe.
+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
+a že velikost toku je rovna velikosti párování. Stačí tedy nalézt maximální celočíselný
+tok (třeba F-F algoritmem) a do~párování umístit ty 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 jinou standardní vìtu:
+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 jinou standardní větu:
-\s{Vìta (Königova):} V~ka¾dém bipartitním grafu je velikost maximálního párování
-rovna velikosti minimálního vrcholového pokrytí.
+\s{Věta (Königova):} V~každém bipartitním grafu je velikost maximálního párování
+rovna velikosti minimálního vrcholového pokrytí.
\proof
-Pokud je $W$ vrcholové pokrytí, musí hrany vedoucí mezi vrcholy této mno¾iny a zdrojem
-a spotøebièem tvoøit stejnì velký øez, proto¾e ka¾dá $st$-cesta obsahuje alespoò
-jednu hranu bipartitního grafu a ta je pokryta. Analogicky vezmeme-li libovolný
-$st$-øez (ne~nutnì tokový, staèí hranový), mù¾eme ho bez zvìt¹ení upravit na~$st$-øez
-pou¾ívající pouze hrany ze~$s$ a do~$t$, kterému pøímoèaøe odpovídá vrcholové pokrytí
-stejné velikosti.
+Pokud je $W$ vrcholové pokrytÃ, musà hrany vedoucà mezi vrcholy této množiny a zdrojem
+a spotřebičem tvořit stejně velký řez, protože každá $st$-cesta obsahuje alespoň
+jednu hranu bipartitního grafu a ta je pokryta. Analogicky vezmeme-li libovolný
+$st$-řez (ne~nutně tokový, stačí hranový), můžeme ho bez zvětšení upravit na~$st$-řez
+používající pouze hrany ze~$s$ a do~$t$, kterému přímočaře odpovídá vrcholové pokrytí
+stejné velikosti.
\qed
-Nìkteré algoritmy na~hledání maximálního párování vyu¾ívají také volné støídavé cesty:
+Některé algoritmy na~hledání maximálního párování využívají také volné střídavé cesty:
-\s{Definice:} {\I (Volná) støídavá cesta} v~grafu $G$ s~párováním~$M$ je cesta, která
-zaèíná i konèí nespárovaným vrcholem a støídají se na~ní hrany le¾ící v~$M$ s~hranami
-mimo párování.
+\s{Definice:} {\I (Volná) střídavá cesta} v~grafu $G$ s~párováním~$M$ je cesta, která
+začíná i končí nespárovaným vrcholem a střídají se na~ní hrany ležící v~$M$ s~hranami
+mimo párování.
-V¹imnìte si, ¾e pro bipartitní grafy odpovídají zlep¹ující cesty v~pøíslu¹né síti
-právì volným støídavým cestám a zlep¹ení toku podél cesty odpovídá pøexorováním
-párování volnou støídavou cestou. Fordùv-Fulkersonùv algoritmus tedy lze velice
-snadno formulovat i v~øeèi støídavých cest.
+Všimněte si, že pro bipartitní grafy odpovídají zlepšující cesty v~příslušné síti
+právě volným střídavým cestám a zlepšení toku podél cesty odpovídá přexorováním
+párování volnou střídavou cestou. Fordův-Fulkersonův algoritmus tedy lze velice
+snadno formulovat i v~řeči střídavých cest.
\bye
projects / ga.git / blobdiff