\prednaska{1}{Toky, øezy a Ford-Fulkersonùv algoritmus}{zapsal Radovan ©esták}
-V~této kapitole nadefinujeme toky v~sítích, øezy a související pojmy a uká¾eme
-Ford-Fulkersonùv algoritmus na nalezení maximálního toku. Dal¹í 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 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 jinde poblí¾) by mìly být zavedeny základní znaèky.}
+\todo{Tady (nebo nìkde poblí¾) by mìly být zavedeny základní znaèky.}
-\todo{Co je $V$, $E$, $m$, $n$ \dots}
+\todo{Co je $V$, $E$, $m$, $n$, komplementy, multihrany, WLOG souvislost \dots}
\h{Toky v sítích}
\itemize\ibull
\:$(V,E)$ je orientovaný graf,
\:$s\in V$ {\I zdroj,}
- \:$t\in V$ {\I stok,} a
+ \:$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$
f^-(v) = \sum_{e=(w,\cdot)} f(e), \quad
f^\Delta(v) = f^+(v) - f^-(v)
$$
- [intuitivnì: co do~vrcholu pøiteèe, co odteèe a jaký je v~nìm pøebytek].
+ [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)}
\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 $E \cap (C \times \overline C)$ [tìm budeme øíkat hrany zleva doprava a budeme
- je znaèit $C^-$] a $E \cap (\overline C \times C)$ [hrany zprava doleva, tedy $C^+$].
+ 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 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}
+%%%\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{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,
+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), ale také:} \cr
+\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).$
\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 vrcholu 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
+[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í vìta:
+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.
\h{Ford-Fulkersonùv algoritmus}
-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)
+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
\s{Algoritmus:}
\algo
-\:$f \leftarrow 0$
+\:$f \leftarrow \<nulový tok>$
\:while $\exists$ zlep¹ující cesta $P$ z~$s$ do~$t$
-\::$m=\min_{e\in P} r(P)$
-\::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)
+\::$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
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ání a øez minimální. Tím jsme také dokázali Ford-Fulkersonovu vìtu (dokonce
-i pro obecné reálné kapacity, proto¾e mù¾eme algoritmus spustit na maximální tok místo nulového
-a on se ihned zastaví a vydá certifikující øez). Navíc algoritmus nikdy nevytváøí z~celých
-èísel necelá, èim¾ získáme:
+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)$.
+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í
-maximálního {\I párování} v~bipartitním grafu (to je mno¾ina hran taková, ¾e ¾ádné
-dvì nemají spoleèný vrchol).
+{\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
-plus dva nové vrcholy $s$ a~$t$, v¹echny pùvodní hrany orientované z~$A$ do~$B$,
+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.
+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
\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í.
-\figure{bip-graf.eps}{Bipartitní graf pro který hledáme maximální párování.}{0.2\hsize}
-\figure{bip-tok.eps}{Sí», ve~které najdeme maximální tok.}{0.3\hsize}
-
\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$ budou
+\:{\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$
- budou vrcholy $s,t$ v~rùzných komponentách souvislosti.
+ 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í více ne¾~$k$ hran.
+ 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
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ù nemá existovat orientovaná
+(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{Pozorování:} Minimální orientované $st$-øezy podle této definice a minimální tokové øezy
+\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.
$st$-øezu rovna maximálnímu poètu hranovì disjunktních $st$-cest.\foot{orientovaných
cest z~$s$ do~$t$}
-\s{Dùkaz:} TODO
+\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:} TODO
+\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}
+%\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 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
projects / ga.git / blobdiff