\input lecnotes.tex
-\prednaska{2}{Toky v sítích}{(pøedná¹el T. Valla, zapsali J. Machálek a K. Vandas)}
+\prednaska{2}{Toky v sítích}{}
-\s{Motivaèní úlohy:}
+\h{Motivaèní úlohy}
+
+Pøedstavme si, ¾e~by v~budovì fakulty na~Malé Stranì existoval èajovod, který
+by rozvádìl èaj do~ka¾dé uèebny. Znázornìme si to orientovaným grafem, v~nìm¾
+jeden významný vrchol pøedstavuje èajovar a~druhý uèebnu, ve~které sedíme.
+Hrany mezi vrcholy pak pøedstavují vìtvící se trubky, které mají èaj rozvádìt.
+Jak dopravit co nejvíce èaje do~dané uèebny?
+
+\figure{toky01.eps}{Èajovod}{2in}
+
+Jiným pøíkladem mù¾e být poèítaèová sí» na~pøenos dat, která se sestává z~pøenosových linek
+spojených pomocí routerù. Data se sice obvykle pøená¹ejí po~paketech, ale to
+mù¾eme pøi dne¹ních rychlostech pøenosu zanedbat a pova¾ovat data za spojitá.
+Jak pøená¹et data mezi dvìma poèítaèi v~síti co nejrychleji?
+
+\h{Toky v~sítích}
+
+\s{Definice:} {\I Sí»} je uspoøádaná pìtice $(V,E,z,s,c)$, pro ní¾ platí:
\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ì?
+\:$(V,E)$ je orientovaný graf.
+\:$c:E\to{\bb R}_{0}^{+}$ je funkce pøiøazující hranám jejich {\I kapacity.}
+\:$z,s \in V$ jsou dva vrcholy grafu, kterým øíkáme {\I zdroj} a~{\I stok} (spotøebiè).
+\:Graf je symetrický, tedy $\forall u,v \in V: uv \in E \Leftrightarrow vu \in E$\foot{%
+Nebude-li hrozit nedorozumìní, budeme hranu z~vrcholu~$u$ do vrcholu~$v$
+znaèit $uv$ namísto formálnìj¹ího, ale ménì pøehledného $(u,v)$. Podobnì u~neorientovaných
+hran pí¹eme $uv$ namísto $\{u,v\}$.}
+(tuto podmínku si~mù¾eme zvolit bez~újmy na~obecnosti, nebo» v¾dy mù¾eme
+do~grafu pøidat hranu, která v~nìm je¹tì nebyla, a~dát jí nulovou kapacitu).
+
+\endlist
+
+\s{Definice:} {\I Tok} je funkce $f:E \to {\bb R}_{0}^{+}$ taková, ¾e~platí:
+\numlist{\ndotted}
+\:Tok po~ka¾dé hranì je omezen její kapacitou: $\forall e \in E : f(e)\le c(e)$.
+\:{\I Kirchhoffùv zákon:}
+$$\forall v \in V \setminus \{z,s\}: \sum_{u: uv \in E}{f(uv)}=\sum_{u: vu \in E}{f(vu)}.$$
+Neboli pro~ka¾dý vrchol kromì zdroje a~stoku platí, ¾e~to, co do~nìj pøitéká,
+je stejnì velké jako to, co z~nìj odtéká (\uv{sí» tìsní}).
\endlist
-\s{Definice:} {\I Sí»} je uspoøádaná ètveøice $(G,z,s,c)$, kde $G$ je
-orientovaný graf, $z$~a~$s$~jsou nìjaké dva jeho vrcholy ({\I zdroj} a {\I stok}) a $c$ je
-{\I kapacita hran,} kterou pøedstavuje funkce $c:E(G)\to{\bb
-R}_{0}^{+}$.
+\figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{2.5in}
-\figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{3in}
+%% \figure{tok.eps}{Pøíklad toku. Èísla pøedstavují toky po~hranách, v~závorkách jsou kapacity.}{4in}
-\par\noindent {\sl Intuice:} Toky v sítích pøedstavují rozvr¾ení, jakým suroviny sítí poteèou.
+Sumy podobné tìm v~Kirchhoffovì zákonì budeme psát èasto, zavedeme si pro nì tedy
+¹ikovné znaèení:
-\s{Definice:} {\I Tok} je funkce $f:E(G)\to{\bb R}_{0}^{+}$ taková, ¾e platí:
-\numlist{\ndotted}
-\:Tok po~ka¾dé hranì 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{Definice:} Pro libovolnou funkci $f:E \to {\bb R}$ definujeme:
+\itemize\ibull
+\:$f^+(v) := \sum_{u: uv \in E}{f(uv)}$ (celkový {\I pøítok} do vrcholu)
+\:$f^-(v) := \sum_{u: vu \in E}{f(vu)}$ (celkový {\I odtok} z~vrcholu)
+\:$f^\Delta(v) := f^+(v) - f^-(v)$ ({\I pøebytek} ve~vrcholu)
\endlist
-\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).
+\>(Kirchhoffùv zákon pak øíká prostì to, ¾e $f^\Delta(v)=0$ pro v¹echna $v\ne z,s$.)
-\s{Poznámka:} V angliètinì se obvykle zdroj znaèí \uv{$s$} a stok \uv{$t$} (jako source a~target).
+\s{Pozorování:} V~ka¾dé síti nìjaký tok existuje: tøeba funkce, která je v¹ude
+nulová (po~¾ádné hranì nic neteèe). To je korektní tok, ale sotva u¾iteèný. Budeme
+chtít najít tok, který pøepraví co nejvíce tekutiny ze~zdroje do~spotøebièe.
-\figure{tok.eps}{Pøíklad toku. Èísla pøedstavují toky po~hranách, v~závorkách jsou kapacity.}{4in}
+\s{Definice:} {\I Velikost toku} $f$ budeme znaèit $\vert f\vert$ a polo¾íme ji
+rovnu souètu velikostí toku na hranách vedoucích do spotøebièe minus souèet
+velikostí tokù na~hranách ze~spotøebièe ven. V~na¹í terminologii je to tedy
+pøebytek ve~spotøebièi: $\vert f\vert:=f^\Delta(s).$
-\s{Definice:} {\I Velikost toku} $f$ je: $$\vert f\vert:=\sum_{zx \in E}{f(zx)}-\sum_{xz \in E}{f(xz)}.$$
+\s{Pozorování:} Jeliko¾ sí» tìsní, mìlo by být jedno, zda velikost toku mìøíme
+u~spotøebièe nebo u~zdroje. Vskutku, krátkým výpoètem ovìøíme, ¾e tomu tak je:
+$$
+f^\Delta(z) + f^\Delta(s) = \sum_v f^\Delta(v) = 0.
+$$
+První rovnost platí proto, ¾e podle Kirchhoffova zákona jsou zdroj a spotøebiè jediné
+dva vrcholy, jejich¾ pøebytek mù¾e být nenulový. Druhou rovnost získáme tak, ¾e si
+uvìdomíme, ¾e tok na ka¾dé hranì pøispìje do celkové sumy jednou s~kladným znaménkem
+a jednou se záporným. Zjistili jsme tedy, ¾e pøebytek zdroje a spotøebièe se li¹í
+pouze znaménkem.
+\qed
-\>Budeme tedy chtít najít v~zadané síti tok, jeho¾ velikost je maximální. Musí v¾dycky existovat?
+\s{Poznámka:} Rádi bychom nalezli v~zadané síti tok, jeho¾ velikost je maximální.
+Máme ale zaruèeno, ¾e maximum bude existovat? V¹ech mo¾ných tokù je nekoneènì mnoho
+a v~nekoneèné mno¾inì se mù¾e snadno stát, ¾e aèkoliv existuje supremum, není maximem
+(pøíklad: $\{1-1/n \mid n\in{\bb N}^+\}$).
+Odpovìï nám poskytne matematická analýza: mno¾ina v¹ech tokù je kompaktní podmno¾inou
+prostoru ${\bb R}^{\vert E\vert}$, velikost toku je spojitá (dokonce lineární) funkce
+z~této mno¾iny do~$\bb R$, tak¾e musí nabývat minima i maxima.
+
+Nám ale bude staèít studovat sítì s~racionálními kapacitami, kde existence maximálního
+toku bude zjevná u¾ z~toho, ze sestrojíme algoritmus, který takový tok najde.
+
+\s{První pokus:} Hledejme cestu $P$ ze~$z$ do~$s$ takovou, ¾e~$\forall e \in
+P: f(e) < c(e)$ (po~v¹ech jejích hranách teèe ostøe ménì, ne¾ jim dovolují
+jejich kapacity). Pak zjevnì mù¾eme tok upravit tak, aby se~jeho velikost
+zvìt¹ila. Zvolme
+$$\varepsilon := \min_{e \in P} \left(c(e) - f(e)\right).$$
+Po ka¾dé hranì zvý¹íme prùtok o~$\varepsilon$, èili definujeme nový tok~$f'$ takto:
+$$
+f'(e) := \cases{
+ f(e) + \varepsilon &\hbox{pro $e\in P$} \cr
+ f(e) &\hbox{pro $e\not\in P$} \cr
+ }
+$$
+To je opìt korektní tok: kapacity nepøekroèíme ($\varepsilon$~jsme zvolili
+nejvy¹¹í mo¾né, aby se to je¹tì nestalo) a~Kirchhoffovy zákony zùstanou
+neporu¹eny, nebo» zdroj a~stok neomezují a~ka¾dému jinému vrcholu na~cestì $P$
+se~pøítok $f^+(v)$ i~odtok $f^-(v)$ zvìt¹í pøesnì o~$\varepsilon$.
+
+Opakujme tento proces tak dlouho, dokud existují cesty, po nich¾ mù¾eme tok
+zlep¹ovat. A¾ se algoritmus zastaví (co¾ by obecnì nemusel, ale to nás je¹tì chvíli
+trápit nemusí), získáme maximální tok?
+Pøekvapivì ne v¾dy. Uva¾ujme napøíklad síti nakreslenou pod tímto odstavcem.
+Najdeme-li nejdøíve cestu pøes svislou hranu (na obrázku tuènì, zlep¹ujeme o~1),
+potom jednu cestu po horní dvojici hran (zlep¹ujeme o~9) a jednu po spodní
+dvojici (zlep¹ujeme také o~9), dostaneme tok o~velikosti 19 a ¾ádná dal¹í cesta
+ho u¾ nemù¾e zlep¹it. Ov¹em maximální tok v~této síti má evidentnì velikost~20.
+
+\figure{toky02.eps}{Èísla pøedstavují kapacity jednotlivých hran.}{1.5in}
+
+Zde by ov¹em situaci zachránilo, kdybychom poslali tok velikosti 1 proti smìru
+prostøední hrany -- to mù¾eme udìlat tøeba odeètením jednièky od toku po smìru
+hrany. Roz¹íøíme tedy ná¹ algoritmus tak, aby umìl posílat tok i proti smìru
+hran. O~kolik mù¾eme tok hranou zlep¹it (a» u¾ pøiètením po~smìru nebo odeètením
+proti smìru) nám bude øíkat její {\I rezerva:}
+
+\s{Definice:} {\I Rezerva hrany} $uv$ je $r(uv):=c(uv) - f(uv) + f(vu).$
+
+\s{Definice:} Hranì budeme øíkat {\I nasycená,} pokud má nulovou rezervu.
+Nenasycená cesta je taková, její¾ v¹echny hrany mají nenulovou rezervu.
+
+\smallskip
+Budeme tedy opakovanì hledat nenasycené cesty a tok po~nich zlep¹ovat.
+Postupnì doká¾eme, ¾e tento postup je koneèný a v~ka¾dé síti najde maximální tok.
+
+\algo{FordFulkerson}
+\:$f \leftarrow$ libovolný tok, napø. v¹ude nulový.
+\:Dokud existuje nenasycená cesta~$P$ ze $z$ do $s$, opakujeme:
+\::$\varepsilon \leftarrow \min \{r(e) \mid e \in P\}$.
+\::Pro v¹echny hrany $uv \in P$:
+\:::$\delta \leftarrow \min \{f(vu),\varepsilon\}$
+\:::$f(vu) \leftarrow f(vu) - \delta$
+\:::$f(uv) \leftarrow f(uv) + \varepsilon - \delta$
+\:Prohlásíme $f$ za~maximální tok.
+\endalgo
-\s{Vìta:} Pro ka¾dou sí» existuje maximální tok.
+\s{Koneènost:} Zastaví se~Fordùv-Fulkersonùv algoritmus?
-\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í).
+\itemize\ibull
-Dobrá, maximální tok v¾dy existuje. Ale kdy¾ nám ho nìkdo uká¾e, umíme poznat,
-¾e je skuteènì maximální? K~tomu se budou hodit øezy:
+\:Pro~celoèíselné kapacity se~v~ka¾dém kroku zvìt¹í velikost toku alespoò o~1.
+Algoritmus se~tedy zastaví po~nejvíce tolika krocích, kolik je nìjaká horní
+mez pro~velikost maximálního toku -- napø. souèet kapacit v¹ech hran
+vedoucích do~stoku (tedy $c^+(s)$).
-\par\noindent {\sl Intuice:} Øez v~grafu je mno¾ina hran oddìlující zdroj a stok.
+\:Pro~racionální kapacity vyu¾ijeme jednoduchý trik. Nech» $M$ je nejmen¹í
+spoleèný násobek jmenovatelù v¹ech kapacit. Spustíme-li algoritmus na sí»
+s~kapacitami $c'(e) = c(e)\cdot M$, bude se rozhodovat stejnì jako v~pùvodní
+síti, proto¾e bude stále platit $f'(e) = f(e)\cdot M$. Nová sí» je pøitom
+celoèíselná, tak¾e se algoritmus jistì zastaví.
-\s{Definice:} {\I Øez} $R$ v síti $(G,z,s,c)$ je mno¾ina hran $R$ taková, ¾e
-neexistuje orientovaná cesta ze $z$~do $s$~v~grafu $(V(G),E(G)\setminus R)$.
+\:Na~síti s~iracionálními kapacitami se~algoritmus chová mnohdy divoce, nemusí
+se~zastavit, ba ani konvergovat ke~správnému výsledku. (Zkuste vymyslet pøíklad
+takové sítì.)
-\s{Definice:} {\I Kapacita øezu} $c(R)=\sum_{uv \in R}{c(uv)}$.
+\endlist
-Nìkdy je lep¹í se na~øezy dívat takto:
+\s{Maximalita:} Kdy¾ se algoritmus zastaví, je tok~$f$ maximální? K~tomu se
+bude hodit zavést øezy.
-\s{Definice:} Pro rozklad mno¾iny vrcholù na dvì disjunktní mno¾iny $A,B$, kde $z\in A$ a $s\in B$ zavedeme
-{\I separátor} $S(A,B)$, co¾ bude mno¾ina hran vedoucích z~$A$ do~$B$. Pokud je $g$ funkce
-definovaná na~hranách (tøeba tok nebo kapacita), definujeme $g(A,B):=\sum_{uv \in E,u\in A,v\in B}{g(uv)}.$
+\s{Definice:} Pro libovolné dvì mno¾iny vrcholù $A$ a~$B$ budeme znaèit $E(A,B)$
+mno¾inu hran vedoucích z~$A$ do~$B$, tedy $E(A,B) = E\cap (A\times B)$.
+Je-li dále $f$ nìjaká funkce pøiøazující hranám èísla, oznaèíme:
-\s{Pozorování:} Ka¾dý separátor je øezem (libovolná orientovaná cesta ze~$z$ do~$s$ musí
-nìkdy opustit mno¾inu~$A$, a to jde pouze po~hranì patøící do~separátoru). Opaènì to sice
-platit nemusí, ale platí, ¾e ke~ka¾dému øezu existuje separátor takový, ¾e souèet kapacit
-jeho hran je nejvý¹e kapacita daného øezu. Staèí si zvolit mno¾inu $A$ jako vrcholy dosa¾itelné
-ze~zdroje po~hranách nele¾icích v~øezu a do~$B$ dát v¹echny ostatní vrcholy. Separátor
-$S(A,B)$ pak bude tvoøen výhradnì hranami øezu (ne~nutnì v¹emi) a sám bude øezem.
+\itemize\ibull
+\:$f(A,B) = \sum_{e\in E(A,B)} f(e)$ (prùtok z~$A$ do~$B$)
+\:$f^\Delta(A,B) = f(A,B) - f(B,A)$ (èistý prùtok z~$A$ do~$B$)
+\endlist
-\s{Definice:} Pro libovolnou mno¾inu vrcholù $A$ zavedeme její {\I doplnìk} $\overline A:=V(G)\setminus A$.
+\s{Definice:} {\I Øez} je uspoøádaná dvojice mno¾in vrcholù ($A,B$) taková, ¾e
+$A$ a $B$ jsou disjunktní, dohromady obsahují v¹echny vrcholy, $A$ obsahuje zdroj a $B$
+obsahuje stok.
+Mno¾inì~$A$ budeme øíkat {\I levá mno¾ina øezu,} mno¾inì~$B$ {\I pravá.}
+{\I Kapacitu øezu} definujeme jako souèet kapacit hran zleva doprava, tedy $c(A,B)$.
-Nyní si v¹imneme, ¾e velikost toku mù¾eme mìøit pøes libovolný separátor: je to mno¾ství
-tekutiny, které teèe pøes separátor z~$A$ do~$B$ minus to, které se vrací zpátky
-(zatím jsme velikost mìøili u~zdroje, vlastnì na~triviálním separátoru $A=\{z\}$, $B=\overline A).$
+\s{Poznámka:} Jiná obvyklá definice øezu øíká,
+¾e øez je mno¾ina hran grafu, po~jejím¾ odebrání se~graf rozpadne na~více
+komponent. Tuto vlastnost mají i na¹e øezy, ale opaènì to nemusí platit.
-\s{Lemma:} Nech» $A\subseteq V(G),z\in A,s\not\in A$ a $f$ je libovolný tok. Potom platí,
-¾e: $$\vert f\vert=f(A,\overline A)-f(\overline A,A).$$
+\s{Lemma:} Pro ka¾dý øez $(A,B)$ a ka¾dý tok~$f$ platí $f^\Delta(A,B)
+= \vert f\vert$.
\proof
-provedeme pomocí Kirchhoffova zákona a definice velikosti toku:
-$$\hbox{Pro ka¾dý vrchol~$u\ne z,s$ platí:~~} \sum_{ux \in E}{f(ux)}-\sum_{xu \in E}{f(xu)}=0,$$
-$$\hbox{pro zdroj pak:~~} \sum_{zx \in E}{f(zx)}-\sum_{xz \in E}{f(xz)=\vert f\vert}.$$
-Rovnice seèteme:
-$$\sum_{u\in A}{\left(\sum_{ux \in E}{f(ux)}-\sum_{xu \in E}{f(xu)}\right)}=\vert f\vert.$$
-V¹imneme si, ¾e hrany, jeji¾ oba koncové vrcholy le¾í v~mno¾inì~$A$, pøispívají
-k~této sumì jednou kladnì a jednou zápornì, hrany, její¾ ani jeden vrchol nele¾í v~$A$,
-nepøispívají vùbec, a koneènì hrany vedoucí z~$A$ do~$B$, resp. opaènì pøispìjí jen jednou
-(kladnì, resp. zápornì). Tedy:
-$$f(A,\overline A)-f(\overline A,A)=\sum_{u\in A,v\not\in A}{f(uv)}-\sum_{u\not\in A,v\in A}{f(uv)}=\vert f \vert.$$
+Opìt ¹ikovným seètením pøebytkù vrcholù:
+$$
+f^\Delta(A,B) = \sum_{v\in B} f^\Delta(v) = f^\Delta(s).
+$$
+První rovnost získáme poèítáním pøes hrany: ka¾dá hrana vedoucí z~vrcholu v~$B$
+do~jiného vrcholu v~$B$ pøispìje jednou kladnì a jednou zápornì; hrany le¾ící
+celé mimo~$B$ nepøispìjí vùbec; hrany s~jedním koncem v~$B$ a druhým mimo pøispìjí
+jednou, pøièem¾ znaménko se bude li¹it podle toho, který konec je v~$B$. Druhá
+rovnost je snadná: v¹echny vrcholy v~$B$ mimo spotøebiè mají podle Kirchhoffova
+zákona nulový pøebytek (zdroj toti¾ v~$B$ nele¾í).
\qed
-\s{Dùsledek:} Pokud $f$ je tok, $R$ je øez, pak platí: $\vert f \vert\le c(R)$.
+\s{Poznámka:} Pùvodní definice velikosti toku coby pøebytku spotøebièe je speciálním
+pøípadem pøedchozího lemmatu -- mìøí toti¾ prùtok pøes øez $(V\setminus\{s\},\{s\})$.
+
+\s{Dùsledek:} Pro ka¾dý tok~$f$ a ka¾dý øez $(A,B)$ platí $\vert f \vert \le c(A,B)$.
+(Velikost ka¾dého toku je shora omezena kapacitou ka¾dého øezu.)
\proof
-Doká¾eme pro separátory (u¾ víme, ¾e ke~ka¾dému øezu najdeme stejnì velký nebo men¹í separátor):
-$$\vert f \vert=f(A,\overline A)-f(\overline A,A)\le f(A,\overline A)\le c(A,\overline A)\le c(R).$$
+$f^\Delta(A,B) = f(A,B) - f(B,A) \le f(A,B) \le c(A,B)$.
\qed
-Nyní víme, ¾e velikost ka¾dého toku je shora omezena velikostí ka¾dého øezu. Kdybychom tedy
-k~na¹emu toku umìli najít stejnì velký øez, hned víme, ¾e tok je maximální a øez minimální.
-Pøekvapivì platí, ¾e se to povede v¾dy. K~tomu se nám budou hodit zlep¹ující cesty:
+\s{Dùsledek:} Pokud $\vert f\vert = c(A,B)$, pak je tok~$f$ maximální a øez~$(A,B)$
+minimální. Jinými slovy pokud najdeme dvojici tok a stejnì velký øez, mù¾eme øez pou¾ít
+jako certifikát maximality toku. Následující vìta nám zaruèí, ¾e je to v¾dy mo¾né:
-\s{Definice:} {\I Zlep¹ující cesta} budeme øíkat takové cestì mezi danými dvìma vrcholy,
-která pou¾ívá buïto hrany sítì (hrany orientované po~smìru cesty) nebo hrany k~nim opaèné (v~síti jsou
-tedy proti smìru cesty).
+\s{Vìta:} Pokud se~Fordùv-Fulkersonùv algoritmus zastaví, tak vydá maximální tok.
-\figure{cesta.eps}{Pøíklad zlep¹ující cesty.}{3in}
+\proof
+Nech» se~Fordùv-Fulkersonùv algoritmus zastaví. Definujme mno¾iny vrcholù $A
+:= \{v \in V \mid \hbox{existuje nenasycená cesta ze~$z$ do~$v$}\}$ a~$B := V \setminus A$.
+
+Dvojice $(A,B)$ je øez, nebo» $z \in A$ (ze~$z$ do~$z$ existuje cesta délky 0)
+a~$s \in B$ (kdyby $s \not\in B$, musela by existovat nenasycená cesta ze~$z$ do~$s$,
+tudí¾ by algoritmus neskonèil, nýbr¾ by po této cestì stávající tok vylep¹il).
+
+Dále víme, ¾e~v¹echny hrany øezu mají nulovou rezervu: kdyby toti¾ pro nìjaké $u\in A$
+a $v\in B$ mìla hrana $uv$ rezervu nenulovou (nebyla nasycená), spojením nenasycené
+cesty ze zdroje do~$u$ s~touto hranou by vznikla nenasycená cesta ze~zdroje do~$v$, tak¾e
+vrchol~$v$ by také musel le¾et v~$A$, co¾ není mo¾né.
+
+Proto po~v¹ech hranách øezu vedoucích z~$A$ do~$B$ teèe tolik, kolik jsou
+kapacity tìchto hran, a~po~hranách vedoucích z~$B$ do~$A$ neteèe nic. Nalezli
+jsme tedy øez $(A,B)$ pro nìj¾ $f^\Delta(A,B) = c(A,B)$. To znamená, ¾e~tento
+øez je minimální a tok~$f$ maximální.
+\qed
-\s{Definice:} {\I Zlep¹ující cesta} $P$ ze $z$ do $s$ je {\I nasycená}, pokud:
-$$\exists e \in P:\cases{
- f(e)=c(e) & \hbox{je-li $e$ orientovaná po smìru} \cr
- f(e)=0 & \hbox{je-li $e$ orientovaná proti smìru} \cr
-}$$
-\>Jinak je zlep¹ující cesta nenasycená.
+Nyní ji¾ mù¾eme vyslovit vìtu o~chování Fordova-Fulkersonova algoritmu:
-\s{Definice:} {\I Tok je nasycený,} pokud je ka¾dá zlep¹ující cesta $P$ ze $z$ do $s$ nasycená.
+\s{Vìta:} Pro ka¾dou sí» s~racionálními kapacitami se~Fordùv-Fulkersonùv algoritmus
+zastaví a~vydá maximální tok a~minimální øez.
-\s{Vìta:} Tok $f$ je nasycený $\Leftrightarrow$ $f$ je maximální. Navíc pro ka¾dý maximální tok $f$ existuje øez $R$ takový, ¾e $\vert f \vert=c(R)$.
+\s{Dùsledek:} Sí» s~celoèíselnými kapacitami má aspoò jeden z~maximálních tokù
+celoèíselný a~Fordùv-Fulkersonùv algoritmus takový tok najde.
\proof
+Kdy¾ dostane Fordùv-Fulkersonùv algoritmus celoèíselnou sí», najde v~ní maximální tok
+a~ten bude zase celoèíselný (algoritmus nikde nevytváøí z~celých èísel necelá).
+\qed
-\>\uv{$\Leftarrow$} doká¾eme nepøímo -- uká¾eme, ¾e pokud nìjaký tok není nasycený, tak ho
-je¹tì lze zlep¹it, proèe¾ nemù¾e být maximální. Mìjme nìjaký nenasycený tok~$f$. Existuje tedy
-nenasycená zlep¹ující cesta $P$. Podél této cesty budeme tok vylep¹ovat.
-Zvolíme:
-$$
-\eqalign{
-\varepsilon_1&:=\min_{e\in P\hbox{\sevenrm~po smìru}}{\{c(e)-f(e)\}}, \cr
-\varepsilon_2&:=\min_{e\in P\hbox{\sevenrm~proti smìru}}{\{f(e)\}}, \cr
-\varepsilon&:=\min{\{\varepsilon_1,\varepsilon_2\}}. \cr
-}
-$$
-Jeliko¾ cesta byla nenasycená, musí být $\varepsilon>0$. Nyní z~toku~$f$ vytvoøíme
-tok~$f'$ takto:
-$$f'(e):=\cases{
- f(e)+\varepsilon & \hbox{je-li $e$ po smìru cesty,} \cr
- f(e)-\varepsilon & \hbox{je-li $e$ proti smìru,} \cr
- f(e) & \hbox{pokud $e\not\in P$.} \cr
-}
-$$
-\>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.$$
+To, ¾e~umíme najít celoèíselné øe¹ení, není vùbec samozøejmé.
+(U~jiných problémù takové ¹tìstí mít nebudeme.)
+Uka¾me si rovnou jednu aplikaci, která celoèíselnost vyu¾ije.
-\>Platnost Kirchhoffova zákona ovìøíme rozborem pøípadù:
-\figure{kirch.eps}{Rozbor pøípadù.}{4in}
+\h{Hledání nejvìt¹ího párování v~bipartitních grafech}
-\>Funkce $f'$ je tedy tok. Jeho velikost se ov¹em oproti~$f$ zvý¹ila o~$\varepsilon$, tak¾e~$f$ nebyl maximální.
+\s{Definice:} Mno¾ina hran $F \subseteq E$ se~nazývá {\I párování}, jestli¾e
+¾ádné dvì hrany této mno¾iny nemají spoleèný ani jeden vrchol. Neboli $\forall
+e,f \in F : e \cap f = \emptyset$. {\I Velikostí} párování myslíme poèet jeho
+hran.
-\>\uv{$\Rightarrow$}: Uvá¾íme mno¾inu vrcholù $A\subseteq V(G)$ definovanou tak, ¾e $v\in A$
-právì tehdy, kdy¾ existuje nenasycená cesta ze $z$ do $v$. V¹imnìme si, ¾e $z \in A$ a $s \not\in A$.
-Potom $S(A,\overline A)$ je øez, který je stejnì velký jako tok~$f$. Jak u¾ víme, pokud k~toku
-najdeme stejnì velký øez, je tok maximální.
-\qed
+Chceme-li v~daném bipartitním grafu $(V,E)$ nalézt nejvìt¹í párování,
+pøetvoøíme graf nejprve na sí» $(V',E',c,z,s)$ takto:
+
+\itemize\ibull
+\:Nalezneme partity grafu, budeme jim øíkat {\I levá} a {\I pravá.}
+\:Pøidáme zdroj~$z$ a vedeme z~nìj hrany do v¹ech vrcholù levé partity.
+\:Pøidáme spotøebiè~$s$ a vedeme do nìj hrany ze~v¹ech vrcholù pravé partity.
+\:Hrany zadaného grafu zorientujeme zleva doprava.
+\:V¹em hranám nastavíme jednotkovou kapacitu.
+\endlist
+
+\figure{toky04.eps}{Hledání nejvìt¹ího párování v~bipartitním grafu.}{2in}
+
+\>Nyní v~této síti najdeme maximální celoèíselný tok. Jeliko¾ v¹echny hrany
+mají kapacitu~1, musí po ka¾dé hranì téci buï~0 nebo~1. Do~výsledného párování
+vlo¾íme právì ty hrany pùvodního grafu, po~kterých teèe~1.
+
+Dostaneme opravdu párování? Kdybychom nedostali, znamenalo by to, ¾e nìjaké
+dvì hrany mají spoleèný vrchol. Ov¹em kdyby se setkaly ve~vrcholu z~pravé
+partity, pøitekly by do tohoto vrcholu alespoò 2 jednotky toku a ty by nemìly
+kam odtéci. Analogicky pokud by se setkaly nalevo, musely by z~vrcholu odtéci
+alespoò 2 jednotky, ale ty se tam nemají kudy dostat.
-\figure{nenasyc.eps}{Rozdìlení $V(G)$ na mno¾inu $A$ a $\overline A$ v dùkazu hlavní vìty o tocích.}{2.5in}
+Zbývá nahlédnout, ¾e nalezené párování je nejvìt¹í mo¾né. K~tomu si staèí v¹imnout,
+¾e z~toku vytvoøíme párování o~tolika hranách, kolik je velikost toku, a naopak
+z~ka¾dého párování umíme vytvoøit celoèíselný tok odpovídající velikosti.
+Jinými slovy nalezli jsme bijekci mezi mno¾inou v¹ech celoèíselných tokù
+a mno¾inou v¹ech párování a tato bijekce zachovává velikost. Nejvìt¹í
+tok tedy musí odpovídat nejvìt¹ímu párování.
-\>To, co jsme o~tocích zjistili, mù¾eme shrnout do~následující \uv{minimaxové} vìty:
+Navíc doká¾eme, ¾e Fordùv-Fulkersonùv algoritmus na sítích tohoto druhu
+pracuje pøekvapivì rychle:
-\s{Vìta (Hlavní vìta o tocích, Ford-Fulkerson):} Pro ka¾dou sí» platí: $$\max_{f\hbox{\sevenrm~tok}}{\vert f \vert=\min_{R\hbox{\sevenrm~øez}}{c(R)}}.$$
+\s{Vìta:} Pro sí», její¾ v¹echny kapacity jsou jednotkové, nalezne Fordùv-Fulkersonùv
+algoritmus maximální tok v~èase $\O(nm)$.
\proof
-Nerovnost \uv{$\le$} je ná¹ Dùsledek lemmatu o~tocích a øezech, rovnost
-platí proto, ¾e k~maximálnímu toku existuje podle pøedcházející vìty stejnì
-velký øez.
+Jedna iterace algoritmu bì¾í v~èase $\O(m)$: nenasycenou cestu najdeme prohledáním
+grafu do ¹íøky, samotné zlep¹ení toku zvládneme v~èase lineárním s~délkou cesty.
+Jeliko¾ ka¾dá iterace zlep¹í tok alespoò o~1,\foot{Mimochodem, mù¾e i o~2, proto¾e
+pøi jednotkových kapacitách mohou rezervy být a¾ dvojky.}
+poèet iterací je omezen velikostí maximálního toku, co¾ je nejvý¹e~$n$
+(uva¾ujte øez tvoøený hranami okolo zdroje).
\qed
-\>Zlep¹ování tokù pomocí zlep¹ujících cest není jen pìkný dùkazový prostøedek,
-dá se pomocí nìj také formulovat elegantní algoritmus na~hledání maximálního toku:
+\s{Dùsledek:} Nejvìt¹í párování v~bipartitním grafu lze nalézt v~èase $\O(mn)$.
-\s{Algoritmus (hledání maximálního toku v síti, Ford-Fulkerson)}
+\proof
+Pøedvedená konstrukce vytvoøí z~grafu sí» o~$n'=n+2$ vrcholech a~$m'=m+2n$
+hranách a spotøebuje na to èas $\O(m'+n')$. Pak nalezneme maximální celoèíselný
+tok Fordovým-Fulkersonovým algoritmem, co¾ trvá $\O(m'n')$. Nakonec tok v~lineárním
+èase pøelo¾íme na~párování. V¹e dohromady trvá $\O(m'n') = \O(mn)$.
+\qed
-\algo
-\:$f \leftarrow \hbox{libovolný tok}$, tøeba v¹ude nulový ($\forall e \in E: f(e) \leftarrow 0 $).
-\:Dokud $\exists$ zlep¹ující cesta $P$: vylep¹íme $f$ podél $P$ jako v~dùkazu vìty.
-\:Prohlásíme $f$ za~maximální tok.
-\endalgo
+\exercises
-\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 jedna. Proto¾e máme horní odhad
-na velikost maximálního toku (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.
-Algoritmus se pøitom chová stejnì jako s~pùvodními kapacitami.
-\:A~pro reálné kapacity? Obecnì ne -- zkuste najít sí» s~nìkterými kapacitami
-iracionální, kde se algoritmus pøi ne¹ikovné volbì zlep¹ujících cest nikdy
-nezastaví a dokonce ani nekonverguje k~maximálnímu toku.
-\:Kolik krokù bude muset algoritmus na následující síti maximálnì udìlat, aby
-úspì¹nì dobìhl? ($2M$ krokù)
-\figure{2M.eps}{Pøíklad sítì. Kolik krokù musí maximálnì udìlat F-F algoritmus?}{2in}
-\:Pokud bychom v¾dy hledali {\I nejkrat¹í} zlep¹ující cestu, co¾ je snad
-nejpøímoèaøej¹í mo¾ná implementace (prohledávání do ¹íøky), algoritmus by
-se zastavil po~$\O(M^2N)$ krocích (tomu se øíká Edmondsùv-Karpùv algoritmus).
-To si nebudeme dokazovat a místo toho si na~pøí¹tí pøedná¹ce rovnou odvodíme
-efektivnìj¹í Dinicùv algoritmus.
-\endlist
+\ex{Najdìte pøíklad sítì s~nejvý¹e 10 vrcholy a 10 hranami, na ní¾ Fordùv-Fulkersonùv
+algoritmus provede více ne¾ milion iterací.}
+
+\exx{Najdìte sí» s~reálnými kapacitami, na ní¾ Fordùv-Fulkersonùv algoritmus nedobìhne.}
+
+\ex{Navrhnìte algoritmus, který pro zadaný orientovaný graf a jeho vrcholy $u$ a~$v$
+nalezne nejvìt¹í mo¾ný systém hranovì disjunktních cest z~$u$ do~$v$.}
+
+\ex{Upravte algoritmus z~pøedchozího cvièení, aby nalezené cesty byly vrcholovì
+disjunktní (a¾ na krajní vrcholy).}
+
+\ex{Mìjme ¹achovnici $R\times S$, z~ní¾ políèko¾rout se¾ral nìkterá políèka. Chceme na ni
+rozestavìt co nejvíce ¹achových vì¾í tak, aby se navzájem neohro¾ovaly. Vì¾ mù¾eme postavit
+na libovolné nese¾rané políèko a ohro¾uje v¹echny vì¾e v~tém¾e øádku èi sloupci. Navrhnìte
+efektivní algoritmus, který takové rozestavìní najde.}
+
+\ex{Situace stejná jako v~minulém cvièení, ale dvì vì¾e se neohro¾ují, pokud je na
+jejich pøímé spojnici alespoò jedno políèko se¾rané.}
+
+\ex{Opìt ¹achovnice po zásahu políèko¾routa. Chceme na nese¾raná políèka rozmístit kostky
+velikosti $1\times 2$ políèka tak, aby ka¾dé nese¾rané políèko bylo pokryto právì jednou kostkou.}
+
+\ex{Dopravní problém: Uva¾ujme továrny $T_1, \ldots, T_p$ a obchody $O_1, \ldots, O_q$. V¹ichni
+vyrábìjí a prodavají tentý¾ druh zbo¾í. Továrna $T_i$ ho dennì vyprodukuje $t_i$ kusù, obchod
+$O_j$ dennì spotøebuje $o_j$ kusù. Navíc máme bipartitní graf urèující, která továrna mù¾e
+dodávat zbo¾í kterému obchodu. Najdìte efektivní algoritmus, který zjistí, zda je po¾adavky
+obchodù mo¾né splnit, ani¾ by se pøekroèily výrobní kapacity továren, a~pokud je to mo¾né,
+vypí¹e, ze~které továrny se má pøepravit kolik zbo¾í do kterého obchodu.}
+
+\exxx{Uva¾ujeme o~vybudování dolù $D_1,\ldots,D_p$ a továren $T_1,\ldots,T_q$. Vybudování
+dolu~$D_i$ stojí cenu~$d_i$ a od té doby dùl zadarmo produkuje neomezené mno¾ství $i$-té
+suroviny. Továrna~$T_j$ potøebuje ke~své èinnosti zadanou mno¾inu surovin (pøiøazení
+surovin továrnám je dáno jako bipartitní graf na vstupu) a pokud jsou v~provozu v¹echny
+doly produkující tyto suroviny, vydìláme na továrnì zisk~$t_j$. Vymyslete algoritmus,
+který spoèítá, které doly postavit, abychom vydìlali co nejvíce.}
+
+%% FIXME: Zmínit permanent
+
+\endexercises
\bye
projects / ads2.git / blobdiff