[ads2.git] / 2-toky / 2-toky.tex

\input lecnotes.tex

\prednaska{2}{Toky v sítích}{}

\s{První motivaèní úloha:} {\I Rozvod èajovodu do~v¹ech uèeben.}
\smallskip

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?

\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?

\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.
\:$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

\figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{2.5in}

\s{Konvence:} 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ì pro neorientovaný
pí¹eme $uv$ namísto $\{u,v\}$.

\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í}).
\endlist

\s{Definice:} Pro libovolnou funkci $f:E \to {\bb R}$ se nám bude hodit následující znaèení:
\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)
\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{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).$

\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:} 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).$$ 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.

\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).$

\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{Algoritmus (Fordùv-Fulkersonùv)}

\algo
\:$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:
\::$\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{Koneènost:} Zastaví se~Fordùv-Fulkersonùv algoritmus?

\itemize\ibull

\: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
vedoucích do~stoku (tedy $c^+(s)$).

\: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í.

\: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ì.)

\endlist

\s{Maximalita:} Kdy¾ se algoritmus zastaví, je tok~$f$ maximální? K~tomu se
bude hodit zavést øezy.

\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:

\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:} {\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$.
Mno¾inì~$A$ budeme øíkat {\I levá mno¾ina,} 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. 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.)

\proof
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èe mají podle Kirchhoffova
zákona nulový pøebytek.
\qed

\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 $\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:

\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$.

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

Dokázali jsme tedy následující:

\s{Vìta:} Pro~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ù
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í).
\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.

\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, je¾ zachovává
velikost. 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 uvìdomit si, ¾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¾itost hledání maximálního párování bude tedy $\O(n \cdot (m+n))$.

\bye