\input lecnotes.tex
-\prednaska{1}{Toky v sítích}{(zapsala Markéta Popelová)}
+\prednaska{2}{Toky v sítích}{}
-\s{První motivaèní úloha:} {\I Rozvod èajovodu do~v¹ech uèeben.}
-\smallskip
+\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, kde by
-jeden významný vrchol pøedstavoval èajovar a~druhý uèebnu, ve~které sedíme.
-Hrany mezi vrcholy by pøedstavovaly vìtvící se trubky, které mají èaj rozvádìt.
-Jak rozvést co nejefektivnìji dostatek èaje do~dané uèebny?
+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}
-\s{Druhá motivaèní úloha:} {\I Pøenos dat.}
-\smallskip
-
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
\:$(V,E)$ je orientovaný graf.
-\:$c:E\to{\bb R}_{0}^{+}$ je {\I kapacita} hran.
+\:$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$ (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
+\: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).
-\figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{2.5in}
+\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)$.
-\: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í}).
+\:{\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:} Pro libovolnou funkci $f:E \to {\bb R}$ se nám bude hodit následující znaèení:
+\figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{2.5in}
+
+%% \figure{tok.eps}{Pøíklad toku. Èísla pøedstavují toky po~hranách, v~závorkách jsou kapacity.}{4in}
+
+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ý pøítok do vrcholu)
-\:$f^-(v) = \sum_{u: vu \in E}{f(vu)}$ (celkový odtok)
-\:$f^\Delta(v) = f^+(v) - f^-(v)$ (pøebytek ve~vrcholu)
+\:$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
\>(Kirchhoffùv zákon pak øíká prostì to, ¾e $f^\Delta(v)=0$ pro v¹echna $v\ne z,s$.)
-\figure{tok.eps}{Pøíklad toku. Èísla pøedstavují toky po~hranách, v~závorkách jsou kapacity.}{4in}
-
-\s{Pozorování:} Nìjaký tok v¾dy existuje. V libovolné síti mù¾eme v¾dy zvolit
-konstantnì nulovou funkci (po~¾ádné hranì nic nepoteè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{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
-rovnou rozdílu souètu velikostí toku na~hranách vedoucích do~$s$ a~souètu velikostí
-toku na~hranách vedoucích z~$s$. Neboli $\vert f\vert:=f^\Delta(s).$
+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.
+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
\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} (c(e) - f(e)).$$ Nový tok $f'$
-pak definujme jako $f'(e):=f(e) + \varepsilon$. Kapacity nepøekroèíme ($\varepsilon$
-je nejvìt¹í mo¾ná hodnota, abychom tok zvìt¹ili, ale nepøekroèili kapacitu ani
-jedné z~hran cesty $P$) 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í zlep¹ující cesty. A¾ se algoritmus
-zastaví (co¾ by obecnì nemusel, ale nás je¹tì chvíli trápit nemusí), získáme maximální tok?
-Pøekvapivì nemusíme. Napø. na~obrázku je vidìt, ¾e~kdy¾ najdeme nejdøíve cestu
-pøes hranu s~kapacitou 1 (na obrázku tuènì) a~u¾ hodnotu toku na~této hranì
-nesní¾íme, tak dosáhneme velikost toku nejvý¹e 19. Ale maximální tok této sítì
-má velikost 20.
+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}
\s{Definice:} {\I Rezerva hrany} $uv$ je $r(uv):=c(uv) - f(uv) + f(vu).$
-\smallskip
-Algoritmus bude vypadat následovnì. Postupnì dok¾eme, ¾e je koneèný a ¾e v~ka¾dé
-síti najde maximální tok.
+\s{Definice:} Hranì budeme øíkat {\I nasycená,} pokud má nulovou rezervu.
+Nenasycená cesta je taková, její¾ v¹echny hrany mají nenulovou rezervu.
-\s{Algoritmus (Fordùv-Fulkersonùv)}
+\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
+\algo{FordFulkerson}
\:$f \leftarrow$ libovolný tok, napø. v¹ude nulový.
-\:Dokud $\exists P$ cesta ze $z$ do $s$ taková, ¾e~$\forall e \in P: r(e) > 0$, opakujeme:
+\: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\}$
\: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í
-závora pro~velikost maximálního toku -- napø. souèet kapacit v¹ech hran
+mez pro~velikost maximálního toku -- napø. souèet kapacit v¹ech hran
vedoucích do~stoku (tedy $c^+(s)$).
\:Pro~racionální kapacity vyu¾ijeme jednoduchý trik. Nech» $M$ je nejmen¹í
\s{Maximalita:} Kdy¾ se algoritmus zastaví, je tok~$f$ maximální? K~tomu se
bude hodit zavést øezy.
-\s{Definice:} {\I Øez} je uspoøádaná dvojice mno¾in vrcholù ($A,B$) taková, ¾e
-$A$ a $B$ jsou disjunktní, pokrývají v¹echny vrcholy, $A$ obsahuje zdroj a $B$
-obsahuje stok. Neboli $A \cap B = \emptyset$, $A \cup B = V$, $z \in A$, $s \in B$.
-
-\>Ka¾dému øezu pøirozenì pøiøadíme mno¾iny hran:
-\itemize\ibull
-\:$E^+(A,B) = E \cap (A\times B)$ (hrany \uv{zleva doprava})
-\:$E^-(A,B) = E \cap (B\times A)$ (hrany \uv{zprava doleva})
-\:$E^\Delta(A,B) = E^+(A,B) \cup E^-(A,B)$ (v¹echny hrany øezu)
-\endlist
+\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:
-\>Také pro libovolnou funkci $f: E\rightarrow {\bb R}$ zavedeme:
\itemize\ibull
-\:$f^+(A,B) = \sum_{e\in E^+(A,B)} f(e)$ (prùtok pøes øez zleva doprava)
-\:$f^-(A,B) = \sum_{e\in E^-(A,B)} f(e)$ (prùtok zprava doleva)
-\:$f^\Delta(A,B) = f^+(A,B) - f^-(A,B)$ (èistý prùtok)
+\:$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
-\>{\I Kapacita øezu} budeme øíkat souètu kapacit hran zleva doprava, tedy $c+(A,B)$.
+\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)$.
-\s{Poznámka:} Øezy se~dají definovat více zpùsoby, jedna z~definic je, ¾e~øez
-je mno¾ina hran grafu takových, ¾e~po~jejich odebrání se~graf rozpadne na~více
+\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:} Pro ka¾dý øez $(A,B)$ a ka¾dý tok~$f$ platí, ¾e $f^\Delta(A,B)
-= \vert f\vert$. (Jinými slovy velikost toku mù¾eme mìøit na libovolném øezu,
-nejen na triviálních øezech kolem zdroje nebo kolem spotøebièe.)
+\s{Lemma:} Pro ka¾dý øez $(A,B)$ a ka¾dý tok~$f$ platí $f^\Delta(A,B)
+= \vert f\vert$.
\proof
Opìt ¹ikovným seètením pøebytkù vrcholù:
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èe mají podle Kirchhoffova
-zákona nulový pøebytek.
+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:} Pro ka¾dý tok~$f$ a ka¾dý øez $(A,B)$ platí $\vert f \vert \le c^+(A,B)$.
+\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
-$f^\Delta(A,B) = f^+(A,B) - f^-(A,B) \le f^+(A,B) \le c^+(A,B)$.
+$f^\Delta(A,B) = f(A,B) - f(B,A) \le f(A,B) \le c(A,B)$.
\qed
-\s{Dùsledek:} Pokud $\vert f\vert = c^+(A,B)$, pak je tok~$f$ maximální a øez~$(A,B)$
+\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 mo¾né v¾dy:
+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
-Nech» se~Fordùv-Fulkersonùv algoritmus zastaví. Definujme mno¾inu vrcholù $A
-:= \{v \in V \mid \hbox{existuje cesta ze~$z$ do~$v$ jdoucí po~hranách s~$r
-> 0$}\}$ a~$B := V \setminus A$.
+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$, tak by musela existovat cesta ze~$z$ do~$s$
-s~kladnou rezervou, tudí¾ by algoritmus neskonèil, nýbr¾ tuto cestu vzal
-a~stávající tok vylep¹il).
-
-Dále víme, ¾e~v¹echny hrany øezu mají nulovou rezervu, èili $\forall uv \in
-E^+(A,B) : r(uv) = 0$ (kdyby mìla hrana $uv$ rezervu nenulovou, tedy kladnou,
-tak by vrchol $v$ patøil do~$A$). 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, tedy $f(uv) = c(uv)$ a $f(vu) = 0$. Máme øez $(A,B)$
-takový, ¾e~$f^\Delta(A,B) = c^+(A,B)$. To znamená, ¾e~jsme na¹li maximální tok
-a~minimální øez. \qed
+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
-Dokázali jsme tedy následující:
+Nyní ji¾ mù¾eme vyslovit vìtu o~chování Fordova-Fulkersonova algoritmu:
-\s{Vìta:} Pro~sí» s~racionálními kapacitami se~Fordùv-Fulkersonùv algoritmus
+\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:} Sí» s~celoèíselnými kapacitami má aspoò jeden z~maximálních tokù
+\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í», tak najde maximální tok a~ten bude zase celoèíselný (algoritmus nikde nedìlí).
+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
-To, ¾e~umíme najít celoèíselné øe¹ení není úplnì samozøejmé. (U~jiných problémù takové ¹tìstí mít nebudeme.) Uka¾me si rovnou jednu aplikaci, která právì celoèíselný tok vyu¾ije.
+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.
-\s{Aplikace:} Hledání nejvìt¹ího párování v~bipartitních grafech.
+\h{Hledání nejvìt¹ího párování v~bipartitních grafech}
\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{Øe¹ení:}
-Mìjme bipartitní graf $G = (V,E)$. V~nìm hledáme nejvìt¹í párování. Sestrojme
-si~sí» takovou, ¾e~vezmeme vrcholy $V$ grafu $G$ a~pøidáme k~nim dva speciální
-vrcholy $z$ (zdroj) a~$s$ (stok) a~ze~zdroje pøidáme hrany do~v¹ech vrcholù
-levé partity a~ze~v¹ech vrcholù pravé partity povedeme hrany do~stoku. V¹echny
-kapacity nastavme na~1. Hrany bipartitního grafu zorientujme z levé partity do
-pravé. Nyní staèí jen na~tuto sí» spustit Fordùv-Fulkersonùv algoritmus (nebo
-libovolný jiný algoritmus, který najde maximální celoèíselný tok) a~a¾~dobìhne,
-tak prohlásit hrany s~tokem 1 za~maximální párování.
-
-\figure{toky04.eps}{Hledání maximálního párování v~bipartitním grafu.}{2in}
-
-Existuje toti¾ bijekce mezi párováním a~celoèíselnými toky pøi~zachování
-velikosti. Z ka¾dého celoèíselného toku na~vý¹e zmínìném grafu (viz obrázek) lze sestrojit
-párování o~stejné velikosti (velikost toku zde odpovídá poètu hran bipartitního
-grafu, po~kterých poteèe 1) a~naopak. Dùle¾ité je si uvìdomit, ¾e~definice toku
-(omezení toku kapacitou a~Kirchhoffovy zákony) nám zaruèují, ¾e~hrany
-s~nenulovým tokem (tedy jednièkovým) budou tvoøit párování (nestane se, ¾e~by
-dvì hrany zaèínaly nebo konèily ve~stejném vrcholu, nebo» by se~nutnì poru¹ila
-jedna ze~dvou podmínek definice toku). Potom i~maximální tok bude odpovídat
-maximálnímu párování a~naopak.
-
-V~bipartitním grafu najdeme maximální párování v~èase $\O(n \cdot (m+n))$. Fordùv-Fulkersonùv algoritmus stráví jednou iterací èas $\O(m+n)$ (za~prohledání do~¹íøky) a~pøi~jednotkových kapacitách bude iterací nejvý¹e~$n$, proto¾e ka¾dou se~tok zvìt¹í alespoò o~1 a v¹echny toky jsou omezené øezem kolem zdroje, který má kapacitu nejvý¹e~$n$. Výsledná èasová slo¾tost hledání maximálního párování bude tedy $\O(n \cdot (m+n))$.
+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.
+
+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í.
+
+Navíc doká¾eme, ¾e Fordùv-Fulkersonùv algoritmus na sítích tohoto druhu
+pracuje pøekvapivì rychle:
+
+\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
+
+\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
+
+\exercises
+
+\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