-%%%%%%%%%%%%%%%%%%%%%%%\r
-% Zápisek prvého semináøe z grafových algoritmù - ze dne ? 7.6.2006 ?\r
-% Téma Toky v sítích a zejména Ford-Fulkersonùv algoritmus.\r
-% Zapsal Radovan ©esták - radovan.sestak@gmail.com\r
-%%%%%%%%%%%%%%%%%%%%%%\r
-\r
-\input ../sgr.tex\r
-\r
-\prednaska{1}{Toky v sítích a FF algoritmus}{zapsal Radovan ©esták}\r
-\r
-\h{Toky v sítích}\r
-\r
-V následujícím odstavci uká¾eme nìkolik tvrzení o sítích, které je\r
-mo¾né si pøedstavit jako sí» potrubí køí¾ící se v uzlech. Vrchol\r
-z kterého se kapalina ¹íøí nazveme zdroj a vrchol kde odtéká stok. Pro\r
-ostatní vrcholy platí, ¾e objem kapaliny pøitékající se rovná objemu\r
-kapaliny odtékající. Toto pravidlo, které pochází z teorie o elektrických obvodech,\r
-se zvykne nazývat Kirchhoffùv zákon. Hledání maximálního toku je duální úlohou k hledání \r
-minimálního øezu. Ford-Fulkersonùv(FF) algoritmus, který bude popsán ní¾e je základním \r
-algoritmem pro hledání tokù. Na úlohu hledání maximálního toku se dají pøevést mnohé\r
-grafové problémy a i proto existuje mnoho algoritmù a nìkteré z nich jsou pouze modifikace \r
-základního FF algoritmu. V dal¹í pøedná¹ce najdete Dinitzùv algoritmus pro tenhle problém.\r
-\r
-\r
-\s{Definice:}\r
-\r
-\itemize\ibull\r
-\:sí»: $N=(V,E,s,t,w)$ kde $V$ je mno¾ina vrcholù, $E\subseteq V\times V$,\r
-$s\in V$ je zdroj, $t\in V$ je stok, $w:\, E\rightarrow{R}^{+}$ jsou kapacity hran\r
-\:tok: $f:\, E\rightarrow{R}^{+}$kde $\forall e\in E\, f(e)\leq w(e)$ a\r
-$\forall v\in V,\, v\neq s,\, v\neq t\,\,\sum_{uv\in E}f(uv)=\sum_{vw\in E}f(vw)$\r
-\:velikost toku: $\|f\|=\sum_{sv\in E}f(sv)-\sum_{vs\in E}f(vs)$ kde $s$ je zdroj\r
-\:øez: $st$-øez je mno¾ina hran $C\subseteq E$ taková, ¾e v grafu $(V,\, E\setminus C)$ neexistuje\r
-cesta z s do t\r
-\:separátor: $st$-separátor je mno¾ina vrcholù $S\subseteq V$ taková, ¾e v grafu\r
-$(V\setminus S,\, E\cap(V\setminus S)\times(V\backslash S))$ neexistuje\r
-cesta z s do t\r
-\:velikost øezu: $\|c\|=\sum_{e\in c}w(e)$ je velikost øezu\r
-\endlist\r
-\r
-\figure{graf.eps}{Pøíklad orientovaného grafu ze zvoleným zdrojem a stokem.}{0.4\hsize}\r
-\r
-\s{Vìta(Ford-Fulkerson) o souvislosti tokù a øezù}\r
-Nech» $N=(V,E,s,t,w)$ je sí», $F$ je mno¾ina pøípustných tokù pro tuto sí» a $C$ je\r
-mno¾ina øezù oddìlující zdroj od stoku. Pak \r
-$$max_{f\in F}|f|=min_{c\in C}\|c\|$$. \r
-Vìta platí pro v¹echny výbìry zdrojù a stokù $\forall s,t\in V, s\neq t$ nech» $st-F$ je mno¾ina\r
-v¹ech tokù ze zdroje $s$ do stoku $t$ a $st-C$ je mno¾ina v¹ech øezù oddìlujících $s$ od $t$. Pak\r
-$$max_{f\in st-F}\|f\|=min_{c\in st-C}\|c\|$$\r
-pro graf $G=(V,E,w)$.\r
-\r
-\s{Dùkaz vìty:}\r
-\r
-\s{$max_{f}\|f\|\leq min_{c}\|c\|$:} Vìznìme libovolný øez oddìlující zdroj od stoku $c$ a uva¾me\r
-graf $G'=(V,E\setminus c)$, který vznikl odebráním hran nacházejících se v øezu. Buï $S$ mno¾ina \r
-vrcholù dosa¾itelných ze zdroje v $G'$.\r
-Pro libovolnej tok $f$ platí: \r
-\r
-$$\|f\| = \sum_{uv\in E, u\in S, v\notin S}f(uv) - \sum_{uv\in E, u\in S, v\notin S}f(vu)$$\r
-velikost toku je rovna rozdílu velikostí tokù pøes hrany opou¹tìjící $S$ a pøicházející do $S$.\r
-$$\|f\| = \sum_{u\in V}f(su) - \sum_{u\in V}f(us)$$\r
-proto¾e se tok zachovává ve v¹ech vrcholech partity $S$ kromì $s$ dostáváme\r
-$$= \sum_{v\in S}(\sum_{u\in V}f(uv)-\sum_{u\in V}f(vu))$$\r
-$f(uv)$ pro $u,v\in S$ jsme jednou pøièítali a jednou odèítali\r
-$$= \sum_{uv\in E, u\in S, v\notin S}f(uv) - \sum_{uv\in E, u\in S, v\notin S}f(vu)$$\r
-\r
-Teï si u¾ staèí jenom uvìdomit, ¾e \r
-$$\|f\| = \sum_{uv\in E, u\in S, v\notin S}f(uv)- \sum_{uv\in E, u\in S, v\notin S}f(vu) \leq \sum_{uv\in E, u\in S, v\notin S}f(uv)\r
-\leq \sum_{uv\in E, u\in S, v\notin S}w(uv) \leq \|c\|$$\r
-Poslední nerovnost je dùsledkem toho, ¾e øez obsahuje v¹echny hrany opou¹tìjící $S$.\r
-\r
-$max_{f}|f|\geq min_{c}|c|$: dùkaz plyne z korektnosti\r
-Ford-Fulkersonova algoritmu viz. algoritmus dále\r
-\r
-\s{Dùsledek:}Pro ka¾dou sí» s celoèíselnými kapacitami je její maximální tok celoèíselný.\r
-\r
-\h{Maximální párování v bipartitním grafu}\r
-Maximální párování v bipartitním grafu $(A\cup B,E)$ se dá najít\r
-pomocí maximálního toku v síti $(A\cup B\cup s\cup t,E',s,t,w)$ kde\r
-$w(e)=1$ a $E'=\{ uv\| u\in A, uv\in E\} \cup \{su\| u\in A\} \cup\{ut\| u\in B\}$ a\r
-obdobnì mù¾eme nalézt minimální vrcholové 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í» v které najdeme maximální tok.}{0.3\hsize}\r
-\r
-\s{Definice}\r
-\itemize\ibull\r
-\:neorientovaný graf G je vrcholovì k-souvislý $\Leftrightarrow$ G má alespoò\r
-k+1 vrcholù a neexistuje separátor s ménì ne¾ k vrcholy\r
-\:neorientovaný graf G je hranovì k-souvislý $\Leftrightarrow$ G má alespoò k+1 vrcholù\r
-a neexistuje øez s ménì ne¾ k hranami\r
-\:orientovaný graf je silnì souvislý $\Leftrightarrow$ existuje orientovaná cesta mezi\r
-v¹emi vrcholy v obou smìrech\r
-\:cirkulace je nulový tok t.j. $\forall v\in V, \sum f(uv)=\sum f(vu)$\r
-\endlist\r
-\r
-\s{Vìta:}(Menger) o souvislosti existencí disjunktních cest a souvislostí\r
-grafù\r
-\r
-buï $G$ neorientovaný graf, pak:\r
-\itemize\ibull\r
-\:$G$ je vrcholovì k-souvislý $\Leftrightarrow$$\forall v,w\in V\,\exists$\r
-k vrcholovì disjunktních cest z $v$ do $w$\r
-\:$G$ je hranovì k-souvislý $\Leftrightarrow$$\forall v,w\in V\,\exists$\r
-k hranovì disjunktních cest z $v$ do $w$\r
-\:kdy¾ $u$ a $v$ jsou nesousední vrcholy v $G$ pak maximální poèet vrcholovì disjunktních\r
-cest mezi $u$ a $v$ se rovná minimálnímu poètu vrcholù z $G-{u,v}$ kterých odebrání oddìlí\r
-$u$ od $v$ \r
-\:kdy¾ $u$ a $v$ jsou vrcholy v $G$ pak maximální poèet hranovì disjunktních\r
-cest mezi $u$ a $v$ se rovná minimálnímu poètu hran, kterých odebrání oddìlí $u$ od $v$\r
-\endlist\r
-buï $G$ orientovaný graf, pak:\r
-\itemize\ibull\r
-\:kdy¾ $u$ a $v$ jsou vrcholy $G$, $uv\notin E(G)$ pak maximální poèet vrcholovì disjunktních\r
-cest z $u$ do $v$ je rovný minimálnímu poètu vrcholù z $G-{u,v}$ kterých odebrání oddìlí $u$ od $v$\r
-\:kdy¾ $u$ a $v$ jsou vrcholy $G$ pak maximální poèet hranovì disjunktních cest z $u$ do $v$ je\r
-rovný minimálnímu poètu hran, kterých odebrání oddìlí $u$ od $v$\r
-\endlist\r
-\r
-Vrcholová i hranová souvislost grafu se dá zjistit pomocí maximálního\r
-toku. Pro hranovou souvislost pøímo zjistíme maximální tok pro ka¾dou\r
-dvojici vrcholù (volba zdroje a stoku). V pøípadì neorientovaného grafu vyrobíme orientovaný graf tak, ¾e ka¾dou\r
-neorientovanou hranu nahradíme orientovanými v obou smìrech. Pro vrcholovou souvislost\r
-navíc musíme ka¾dý vrchol nahradit dvìma novými a spojit je hranou\r
-v obou smìrech (pod-rozdìlení vrcholu). Kapacity hran volíme 1.\r
-Pro nalezení tìchto cest staèí v¾dy v síti odebírat postupnì cestu\r
-z $s$ do $t$. Odebrání jedné cesty sní¾í tok o jedna a tedy cest\r
-musíme nalézt $k$.\r
-\figure{vrchol.eps}{Vrchol který chceme pod-rozdìlit.}{0.1\hsize}\r
-\figure{podrozdeleni.eps}{Výsledek pod-rozdìlení vrcholu.}{0.15\hsize}\r
-\r
-\r
-\s{Ford-Fulkersonùv algoritmus}\r
-Algoritmus nepracuje pøímo s kapacitami a s toky pøes hrany, ale s rezervami\r
-tìchto hran. Funkce rezerv definujeme jako $r(uv)\equiv w(uv)-f(uv)+f(vu)$.\r
-Jestli $uv\notin E(G)$ pak $w(uv)=0$.\r
-Kdy¾ zmen¹ujeme rezervu hrany tak o stejnou hodnotu zvý¹íme hodnotu\r
-rezervy opaèné hrany. Dále pak FF cesta, je cesta pro kterou má ka¾dá hrana kladnou rezervu.\r
-\r
-\algo\r
-\:nastav rezervy pro nulový tok na v¹ech hranách (rezervy se rovnají kapacitám)\r
-\:while $\exists$FF cesta z $s$ do $t$\r
-\::buï $p$ FF cesta z $s$ do $t$\r
-\::zvìt¹i tok zmen¹ením rezerv, o $m=min_{uv\in p}r(uv)$ \r
-\:end while\r
-\:spoèti tok z rezerv\r
-\endalgo\r
-\r
-Pro dùkaz korektnosti algoritmu uva¾ mno¾inu $X=\{ v,\,\exists$FF\r
-cesta z $s$ do $v\}$ po dobìhnutí algoritmu. Proto¾e neexistuje FF cesta z $s$ do $t$, $t\notin X$.\r
-Pak mno¾iny $X$ a $V\setminus X$ urèují øez tvoøený hranami spojujícími\r
-vrcholy z rùzných mno¾in $c=\{uv: uv\in E, u\in X, v\in V\setminus X\}$. V¹echny hrany $uv\in c$\r
-mají nulovou rezervu, nebo» jinak by se dala prodlou¾it FF cesta do vrcholu z $V\setminus X$. Tak¾e velikost\r
-toku se rovná souètu kapacit hran z $X$ do $V\setminus X$ (tohle tvrzení jsme dokázali pøi dùkazu opaèné implikace\r
-FF vìty). Souèasnì tyhle hrany tvoøí $st$-øez, kterého kapacita je rovna velikosti toku. Na¹li jsme tedy øez, \r
-kterého velikost se rovná velikosti pøípustného toku a tím je dùkaz FF vìty ukonèen. \r
-\r
-Kdy¾ máme celoèíselné kapacity hran tak v ka¾dém kroku se tok zvìt¹í\r
-alespoò o jedna a maximální tok je z hora omezen, napøíklad souètem\r
-v¹ech kapacit hran. Pro racionální kapacity staèí vynásobit kapacity\r
-a dostaneme celoèíselné. Z toho plyne koneènost FF algoritmu pro hrany s racionálními kapacitami.\r
-Táto varianta FF algoritmu není obecnì koneèná pøi reálných kapacitách. Volíme-li ov¹em zlep¹ující cestu, která\r
-má maximální minimum pøes rezervy tak je FF algoritmus koneèný i pro reálné kapacity hran.\r
-\r
-Pro FF algoritmus s jednotkovými kapacitami a vyu¾itím BFS (procházení\r
-do ¹íøky) na hledání FF cest je èasová slo¾itost algoritmu $O(n.m)$.\r
-Edmunds s Karpem dokázali, ¾e pøi volbì nejkrat¹í cesty je èasová\r
-slo¾itost v obecném pøípadì $O(n.m^{2})$.\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