-\input ../lecnotes.tex
+\input lecnotes.tex
-\prednaska{2}{Toky v sítích}{(pøedná¹el T. Valla, zapsali K. Vandas a J. Machálek)}
+\prednaska{2}{Toky v sítích}{}
-\h{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 Sí»} je uspoøádaná ètveøice $(G,z,s,c)$, kde $G$ je orientovaný graf, $z$~a~$s$~jsou jeho vrcholy (zdroj a stok) a $c$ je kapacita sítì, kterou pøedstavuje funkce $c:E(G)\to\bb R_{0}^{+}$.
+\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
-\figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{3in}
+\figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{2.5in}
-\par\noindent {\sl Intuice:} Toky v sítích pøedstavují rozvr¾ení, jakým suroviny sítí poteèou.
+%% \figure{tok.eps}{Pøíklad toku. Èísla pøedstavují toky po~hranách, v~závorkách jsou kapacity.}{4in}
-\s{Definice:} {\I Tok} je funkce $f:E(G)\to\bb R$ taková, ¾e platí:
-\numlist{\ndotted}
-\:Tok ka¾dé hrany je omezen její kapacitou: $0\le f(e)\le c(e)$.
-\:Kirchhoffùv zákon -- nikde se neztrácejí suroviny: $$\sum_{(x,u)\in E}{f(x,u)}=\sum_{(u,x)\in E}{f(u,x)}\quad \forall u\in V(G), u\ne z, u\ne s.$$
+Sumy podobné tìm v~Kirchhoffovì zákonì budeme psát èasto, zavedeme si pro nì tedy
+¹ikovné znaèení:
+
+\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{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.
+
+\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{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
-\s{Poznámka:} V angliètinì se obvykle zdroj znaèí \uv{$s$} a stok \uv{$t$} (zkratky source a~target).
+\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
-\figure{tok.eps}{Pøíklad toku. Èísla pøedstavují ohodnocení funkcí toku (v závorkách jsou kapacity hran).}{4in}
+\s{Koneènost:} Zastaví se~Fordùv-Fulkersonùv algoritmus?
-\s{Definice:} {\I Velikost toku} $f$ je: $$w(f)=\sum_{(z,x)\in E}{f(z,x)}-\sum_{(x,z)\in E}{f(x,z)}.$$
+\itemize\ibull
-\s{Vìta:} Pro ka¾dou sí» existuje maximální tok (bez dùkazu).
+\: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 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á.
+\: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í.
-\par\noindent {\sl Intuice:} Øez grafu je mno¾ina hran oddìlující zdroj a stok.
+\: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 Øez} $R$ v síti $(G,z,s,c)$ je $R\subseteq E(G)$ taková, ¾e neexistuje cesta ze $z$ do $s$ v grafu $(V(G),E(G)\setminus R)$.
+\endlist
-\s{Definice:} {\I Kapacita øezu} $c(R)=\sum_{(u,v\in R)}{c(u,v)}$.
+\s{Maximalita:} Kdy¾ se algoritmus zastaví, je tok~$f$ maximální? K~tomu se
+bude hodit zavést øezy.
-\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{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:
-\proof
-Dùkaz provedeme pomocí dokázání dvou neostrých nerovností.
+\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
-\>Pomocné znaèení: Zaveïme konvenci, ¾e existují-li orientované hrany $(u,v)$, $u\in A$, $v\in B$, znaèíme je $S(A,B)$ (separátor). $f(A,B)=\sum_{(u,v)\in E,u\in A,v\in B}{f(u,v)}.$
+\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)$.
-{\narrower
-\par\noindent {\sl Intuice:} Uvá¾íme-li mno¾inu kapacit v¹ech øezù, je zdola omezená mno¾inou hodnot tokù.
+\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:} $A\subseteq V(G),z\in A,s\not\in A,f\hbox{ je tok}$. Potom platí, ¾e $$w(f)=f(A,V\setminus~A)-f(V\setminus~A,A)$$
+\s{Lemma:} Pro ka¾dý øez $(A,B)$ a ka¾dý tok~$f$ platí $f^\Delta(A,B)
+= \vert f\vert$.
\proof
-Dùkaz provedeme pomocí Kirchhoffova zákonu a definice velikosti toku:
-$$\sum_{(u,x)\in E}{f(u,x)}-\sum_{(x,u)\in E}{f(x,u)}=0\quad\forall u\in A,u\neq z,u\neq s$$
-$$\sum_{(z,x)\in E}{f(z,x)}-\sum_{(x,z)\in E}{f(x,z)=w(f)}$$
-
-\>Rovnice seèteme:
-$$\sum_{u\in A}{\left(\sum_{(u,x)\in E}{f(u,x)}-\sum_{(x,u)\in E}{f(x,u)}\right)}=w(f)$$
+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{Poznámka:} Tato rovnice neznamená nic jiného, ne¾ ¾e se hrany vedoucí z~$A$ do $A$ jednou pøiètou a jednou odeètou. Projeví se pouze hrany, které vedou dovnitø a ven z $V\setminus A$, tak¾e toky vnitøních hran $A$ se \uv{po¾erou}.
+\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\})$.
-\>Z toho plyne:
-$$f(A,V\setminus A)-f(V\setminus A,A)=\sum_{u\in A,v\not\in A}{f(u,v)}-\sum_{u\not\in A,v\in A}{f(u,v)}=w(f).$$
+\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
+$f^\Delta(A,B) = f(A,B) - f(B,A) \le f(A,B) \le c(A,B)$.
\qed
-\s{Dùsledek:} Pokud $f$ je tok, $R$ je øez, pak platí: $w(f)\le c(R)$.
+\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{Vìta:} Pokud se~Fordùv-Fulkersonùv algoritmus zastaví, tak vydá maximální tok.
\proof
-$w(f)=f(A,V\setminus A)-f(V\setminus A,A)\le f(A,V\setminus A)\le c(A,V\setminus A)\le c(R)$
+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
+
+Nyní ji¾ mù¾eme vyslovit vìtu o~chování Fordova-Fulkersonova algoritmu:
+
+\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{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
-\s{Definice:} {\I Zs-cesta} je posloupnost navazujících hran, u kterých ignorujeme orientaci.
+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.
+\h{Hledání nejvìt¹ího párování v~bipartitních grafech}
-\figure{cesta.eps}{Pøíklad zs-cesty.}{3in}
+\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.
-\s{Definice:} {\I Zs-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 zs-cesta nenasycená.
+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:
-\s{Definice:} {\I Tok} je {\I nasycený}, pokud $\forall$ zs-cesta $P$ ze $z$ do $s$ je nasycená.
+\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
-\s{Vìta:} Tok $f$ je nasycený $\Leftrightarrow$ $f$ je maximální. Navíc pro ka¾dý maximální tok $f$ existuje øez $R$, ¾e $w(f)=c(R)$.
+\figure{toky04.eps}{Hledání nejvìt¹ího párování v~bipartitním grafu.}{2in}
-\proof
+\>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.
-\>\uv{$\Leftarrow$} sporem: Mìjme tok $f$ maximální a nenasycený. Existuje tedy zs-cesta $P$ nenasycená. 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$$
-\>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.$$
+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.
-\>Platnost Kirchhoffova zákonu ovìøíme rozborem pøípadù:
-\figure{kirch.eps}{Rozbor pøípadù.}{4in}
+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í.
-\>$f^{'}$ je tedy tok, ov¹em potom platí:
-$$w(f^{'})=w(f)+\varepsilon\Rightarrow w(f^{'})>w(f)\Rightarrow\hbox{SPOR.}$$
+Navíc doká¾eme, ¾e Fordùv-Fulkersonùv algoritmus na sítích tohoto druhu
+pracuje pøekvapivì rychle:
-\>\uv{$\Rightarrow$}: Uvá¾íme $A\subseteq V(G)$, ¾e $\forall\ v\in{} A$ existuje nenasycená cesta ze $z$ do $v$. $z \in A$, $s \not\in A$. $S(A,V\setminus A)$ je hledaný øez $R$. Podle lemmatu:
-$$w(f)=f(A,V\setminus A)-f(V\setminus A,A)=c(A,V\setminus A)=c(R)$$
-Víme, ¾e $w(f)\le c(R)$. Staèilo uvá¾it nasycený tok $f$. Pak jsme sestrojili øez $R$ a~výraz pøe¹el v rovnost $c(R)=w(f)$ (a tedy je tok $f$ maximální).
+\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
+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
-}
-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.
+\s{Dùsledek:} Nejvìt¹í párování v~bipartitním grafu lze nalézt v~èase $\O(mn)$.
+
+\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
-\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}
+\exercises
-\s{Algoritmus:} (Fordùv-Fulkersonùv algoritmus hledání maximálního toku)
+\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í.}
-\algo
-\:$f(e) := 0\ \forall e \in E$
-\:while $\exists$ zlep¹ující cesta $P$, vylep¹i $P$ jako v dùkazu hlavní vìty
-\:f je maximální
-\endalgo
+\exx{Najdìte sí» s~reálnými kapacitami, na ní¾ Fordùv-Fulkersonùv algoritmus nedobìhne.}
-\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 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
+\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
-\figure{2M.eps}{Pøíklad sítì. Kolik krokù musí maximálnì udìlat F-F algoritmus?}{2in}
+\endexercises
\bye
projects / ads2.git / blobdiff