\h{Motivaèní úlohy:}
\itemize\ibull
\:Mìjme orientovaný graf se speciálními vrcholy ®elivka a Kanál pøedstavující pra¾ské vodovody. V tomto grafu budou vrcholy vodovodními stanicemi a hrany trubkami mezi nimi. Kolik vody proteèe ze ®elivky do Kanálu?
-\:Mìjme orientovaný graf pøedstavující ¾eleznièní sí»; graf má význaèné vrcholy Moskva a Fronta, ka¾dá hrana grafu má kapacitu, kterou mù¾e uvézt. Kolik vojákù je schopna sí» pøevézt z Moskvy a spotøebovat na Frontì?
+\:Mìjme orientovaný graf pøedstavující ¾eleznièní sí»; graf má význaèné vrcholy Moskva a Fronta, ka¾dá hrana grafu má kapacitu, kterou mù¾e uvézt. Kolik vojákù je schopna sí» pøevézt z~Moskvy a spotøebovat na Frontì?
\endlist
\s{Definice:} {\I Sí»} je uspoøádaná ètveøice $(G,z,s,c)$, kde $G$ je orientovaný graf, $z$~a~$s$~jsou jeho vrcholy ({\I zdroj} a {\I stok}) a $c$ je kapacita sítì, kterou pøedstavuje funkce $c:\break E(G)\to{\bb R}_{0}^{+}$.
\par\noindent {\sl Intuice:} Toky v sítích pøedstavují rozvr¾ení, jakým suroviny sítí poteèou.
-\s{Definice:} {\I Tok} je funkce $f:E(G)\to\bb R$ taková, ¾e platí:
+\s{Definice:} {\I Tok} je funkce $f:E(G)\to{\bb R}_{0}^{+}$ taková, ¾e platí:
\numlist{\ndotted}
\:Tok ka¾dé hrany je omezen její kapacitou: $0\le f(e)\le c(e)$.
\:Kirchhoffùv zákon -- \uv{sí» tìsní}: $$\sum_{xu \in E}{f(xu)}=\sum_{ux \in E}{f(ux)}\quad\hbox{pro ka¾dé }u\in V(G) \setminus \{z,s\}.$$
\s{Poznámka:} Pokud bychom se chtìli v definici toku u bodu 2 vyhnout podmínkám pro $z$ a $s$, mù¾eme zdroj a stok vzájemnì propojit (pak jde o tzv. cirkulaci).
-\s{Poznámka:} V angliètinì se obvykle zdroj znaèí \uv{$s$} a stok \uv{$t$} (zkratky source a~target).
+\s{Poznámka:} V angliètinì se obvykle zdroj znaèí \uv{$s$} a stok \uv{$t$} (jako source a~target).
\figure{tok.eps}{Pøíklad toku. Èísla pøedstavují ohodnocení funkcí toku a kapacity.}{4in}
-\s{Definice:} {\I Velikost toku} $f$ je: $$w(f)=\sum_{zx \in E}{f(zx)}-\sum_{xz \in E}{f(xz)}.$$
+\s{Definice:} {\I Velikost toku} $f$ je: $$w(f):=\sum_{zx \in E}{f(zx)}-\sum_{xz \in E}{f(xz)}.$$
\s{Vìta:} Pro ka¾dou sí» existuje maximální tok.
-\par\noindent {\sl Idea dùkazu:} Doká¾e se pomocí metod matematické analýzy s tím, ¾e mno¾ina tokù je kompaktní a funkce velikosti toku je spojitá (dokonce lineární).
+\par\noindent {\sl Idea dùkazu:} Doká¾e se pomocí metod matematické analýzy s~tím, ¾e mno¾ina tokù je kompaktní a funkce velikosti toku je spojitá (dokonce lineární).
-\par\noindent {\sl Intuice:} Øez v grafu je mno¾ina hran oddìlující zdroj a stok.
+\par\noindent {\sl Intuice:} Øez v~grafu je mno¾ina hran oddìlující zdroj a stok.
-\s{Definice:} {\I Øez} $R$ v síti $(G,z,s,c)$ je mno¾ina hran $R$ taková, ¾e neexistuje cesta ze $z$ do $s$ v grafu $(V(G),E(G)\setminus R)$.
+\s{Definice:} {\I Øez} $R$ v síti $(G,z,s,c)$ je mno¾ina hran $R$ taková, ¾e neexistuje cesta ze $z$~do $s$~v~grafu $(V(G),E(G)\setminus R)$.
\s{Definice:} {\I Kapacita øezu} $c(R)=\sum_{uv \in R}{c(uv)}$.
-\s{Vìta (Hlavní vìta o tocích, Ford-Fulkerson):} Mìjme $S$ sí». Platí: $$\max_{f\hbox{ tok}}{w(f)=\min_{R\hbox{ øez}}{c(R)}}.$$
+\s{Vìta (Hlavní vìta o tocích, Ford-Fulkerson):} Mìjme sí» $S$. Platí: $$\max_{f\hbox{ tok}}{w(f)=\min_{R\hbox{ øez}}{c(R)}}.$$
\proof
Dùkaz provedeme pomocí dokázání dvou neostrých nerovností.
-\>Pomocné znaèení: Jako $S(A,B)$ ({\I separátor}) znaèíme orientované hrany $uv$, $u\in A$, $v\in B$. $f(A,B)=\sum_{uv \in E,u\in A,v\in B}{f(uv)}.$
+\>Pomocné znaèení: Jako {\I separátor} $S(A,B)$ znaèíme orientované hrany $uv$, $u\in A$, $v\in B$. $f(A,B)=\sum_{uv \in E,u\in A,v\in B}{f(uv)}.$
{\narrower
\par\noindent {\sl Intuice:} Uvá¾íme-li mno¾inu kapacit v¹ech øezù, je zdola omezená mno¾inou hodnot tokù.
\figure{cesta.eps}{Pøíklad zplep¹ující cesty.}{3in}
-\s{Definice:} {\I Zlep¹ující cesta} $P$ ze $z$ do $s$ je {\I nasycená}, pokud
+\s{Definice:} {\I Zlep¹ující cesta} $P$ ze $z$ do $s$ je {\I nasycená}, pokud:
$$\exists\ e \in P\left\{{f(e)=c(e)\dots \hbox{orientovaná po smìru}}\atop{f(e)=0\dots \hbox{orientovaná proti smìru}}\right.$$
\>Jinak je zlep¹ující cesta nenasycená.
\>\uv{$\Leftarrow$} sporem: Mìjme tok $f$ maximální a nenasycený. Existuje tedy nenasycená zlep¹ující cesta $P$. Tuto cestu $P$ budeme vylep¹ovat.
\>Zvolíme:
-$$\varepsilon_1=\min_{e\in P,\hbox{ po smìru}}{\{c(e)-f(e)\}},$$
-$$\varepsilon_2=\min_{e\in P,\hbox{ proti smìru}}{\{f(e)\}},$$
-$$\varepsilon=\min{\{\varepsilon_1,\varepsilon_2\}}>0.$$
+$$\varepsilon_1:=\min_{e\in P,\hbox{ po smìru}}{\{c(e)-f(e)\}},$$
+$$\varepsilon_2:=\min_{e\in P,\hbox{ proti smìru}}{\{f(e)\}},$$
+$$\varepsilon:=\min{\{\varepsilon_1,\varepsilon_2\}}>0.$$
\>Poslední ostrá nerovnost vyplývá z definice nenasycené cesty. Nyní vylep¹íme tok $f$ o $\varepsilon$: $f\to f^{'}$:
$$f^{'}(e)=\left\{{\displaystyle f(e)+\varepsilon \dots e\in P\hbox{ po smìru}\hfill}\atop{{\displaystyle f(e)-\varepsilon \dots e\in P\hbox{ proti smìru}\hfill}\atop{\displaystyle f(e) \dots e\not\in P\hfill}}\right.$$
\>Nyní je potøeba ovìøit, ¾e $f^{'}$ je skuteènì tok:
$$0\le f^{'}(e)\le c(e)\dots\hbox{platí stále díky volbì }\varepsilon.$$
-\>Platnost Kirchhoffova zákonu ovìøíme rozborem pøípadù:
+\>Platnost Kirchhoffova zákona ovìøíme rozborem pøípadù:
\figure{kirch.eps}{Rozbor pøípadù.}{4in}
\>$f^{'}$ je tedy tok, ov¹em potom platí:
\qed
}
-Poslední vìta spolu s dùsledkem lemmatu dokazuje i hlavní vìtu o tocích. Pro ka¾dou sí» máme maximální tok a k nìmu øez stejné kapacity.
+\>Poslední vìta spolu s dùsledkem lemmatu dokazuje i hlavní vìtu o tocích. Pro ka¾dou sí» máme maximální tok a k nìmu øez stejné kapacity.
\qed
\figure{nenasyc.eps}{Rozdìlení $V(G)$ na mno¾inu $A$ a $V\setminus A$ v dùkazu hlavní vìty o tocích.}{2.5in}
-\s{Algoritmus:} (Fordùv-Fulkersonùv algoritmus hledání maximálního toku)
+\s{Algoritmus (hledání maximálního toku v síti, Ford-Fulkerson)}
\algo
-\:pøiøad $f$ nulový tok ($f(e) := 0$ pro v¹echny $e \in E$).
-\:while $\exists$ zlep¹ující cesta $P$, vylep¹i $f$ podél $P$ jako v dùkazu hlavní vìty.
+\:Pøiøad $f$ nulový tok ($\forall e \in E: f(e) \leftarrow 0 $).
+\:Dokud $\exists$ zlep¹ující cesta $P$: vylep¹i $f$ podél $P$ jako v~dùkazu hlavní vìty.
\:$f$ je maximální.
\endalgo
\h{Cvièení:}
\itemize\ibull
-\:Je pro pøirozené kapacity F-F algoritmus koneèný? Ano -- v ka¾dém zlep¹ujícím kroku algoritmu se celkový tok zvìt¹í aspoò o 1. Proto¾e máme horní odhad na maximální tok (napø. souèet kapacit v¹ech hran), máme i~horní odhad na dobu bìhu algoritmu.
+\:Je pro pøirozené kapacity F-F algoritmus koneèný? Ano -- v ka¾dém zlep¹ujícím kroku algoritmu se celkový tok zvìt¹í aspoò o jedna. Proto¾e máme horní odhad na maximální tok (napø. souèet kapacit v¹ech hran), máme i~horní odhad na dobu bìhu algoritmu.
\:Je F-F algoritmus koneèný pro racionální kapacity hran? Ano -- v¹echny kapacity vynásobíme spoleèným jmenovatelem a pøevedeme na pøedchozí pøípad (pro obecné kapacity ov¹em takto definovaný F-F algoritmus nemusí být koneèný).
\:Kolik krokù bude muset algoritmus na následující síti maximálnì udìlat, aby úspì¹nì dobìhl? ($2M$ krokù)
\endlist
projects / ads2.git / blobdiff