Merge branch 'master' of git+ssh://git.ucw.cz/home/mj/GIT/ads2

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

diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex
index fe5b8f9ea4c6c1d3a7f01f75c63fef18e740793e..da0df3d69c0b637ffefe16096ba30a17fffacc15 100644 (file)
--- a/1-toky/1-toky.tex
+++ b/1-toky/1-toky.tex
@@ -1,26 +1,35 @@
 \input lecnotes.tex
 
 \input lecnotes.tex
 

-\prednaska{2}{Toky v sítích}{(zapsala Markéta Popelová)}
+\prednaska{1}{Toky v sítích}{(zapsala Markéta Popelová)}

 
 

-\s{Motivaèní úloha:} Rozvod èajovodu do~v¹ech uèeben
+\s{První motivaèní úloha:} Rozvod èajovodu do~v¹ech uèeben.
+
+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?

 
 

-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~na~orientovaném grafu, kde by jeden vrchol pøedstavoval èajovar a~druhý uèebnu, ve~které sedíme. Jak rozvést co nejefektivnìji dostatek èaje do~dané uèebny?

 
 \figure{toky01.eps}{Èajovod}{2in}
 
 
 \figure{toky01.eps}{Èajovod}{2in}
 

+
+\s{Druhá motivaèní úloha:} Pøenos dat.
+
+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)$, kde platí: 
 \itemize\ibull
 \:$(V,E)$ je orientovaný graf.
 \s{Definice:} {\I Sí»} je uspoøádaná pìtice $(V,E,z,s,c)$, kde platí: 
 \itemize\ibull
 \:$(V,E)$ je orientovaný graf.

-\:$c:E\to{\bb R}_{0}^{+}$ je funkce znázoròující kapacitu hran.
-\:$z,s \in V$ jsou dva vrcholy grafu, kterým øíkáme zdroj a~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 mohu do~grafu pøidat hranu, která v~nìm je¹tì nebyla, a~dát jí nulovou kapacitu).
+\:$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{Definice:} {\I Tok} je funkce $f:E \to {\bb R}_{0}^{+}$ taková, ¾e~platí:
 \numlist{\ndotted}
 \endlist
 
 \figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{2.5in}
 
 \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 : 0\le f(e)\le c(e)$.
+\: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á.
 \endlist
 
 \: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á.
 \endlist
 


@@ -32,15 +41,13 @@ P
 \endlist
 Pak mù¾eme Krichhoffùv zákon zapsat jednodu¹e jako: $$\forall v \in V \setminus \{z,s\}: f^\Delta(v) = 0.$$
 
 \endlist
 Pak mù¾eme Krichhoffùv zákon zapsat jednodu¹e jako: $$\forall v \in V \setminus \{z,s\}: f^\Delta(v) = 0.$$
 

-\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$} (jako source a~target).
+\s{Poznámka:} V~angliètinì se~obvykle zdroj znaèí {$s$} a~stok {$t$} jako source a~target.

 
 \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 funkci nulovou (po~¾ádné hranì nic nepoteèe). Tato funkce splòuje podmínky toku, a~tedy takovýto nulový tok je zcela korektní.
 
 
 \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 funkci nulovou (po~¾ádné hranì nic nepoteèe). Tato funkce splòuje podmínky toku, a~tedy takovýto nulový tok je zcela korektní.
 

-\s{Definice:} {\I Velikost toku} $f$ je: $$\vert f\vert:=f^\Delta(s).$$
+\s{Definice:} {\I Velikost toku} $f$ je rozdíl souètu velikostí toku na~hranách vedoucích do~$s$ a~souètu velikostí toku na~hranách vedoucích z~$s$. Neboli od~toho, co do~stoku pøitéká odeèteme to, co ze~stoku odtéká. $$\vert f\vert:=f^\Delta(s).$$

 
 \s{Cíl:} Budeme chtít najít v~zadané síti tok, jeho¾ velikost je maximální. 
 
 
 \s{Cíl:} Budeme chtít najít v~zadané síti tok, jeho¾ velikost je maximální. 
 


@@ -50,7 +57,7 @@ Pak m
 
 \s{Poznámka:} Pro~na¹e pøípady pøedpokládejme, ¾e~kapacity jsou racionální. Pomìrnì nám to zjednodu¹í práci a~pøíli¹ nám to neublí¾í, nebo» práce s~reálnými èísly je stejnì pro~informatika pomìrnì zapeklitá.
 
 
 \s{Poznámka:} Pro~na¹e pøípady pøedpokládejme, ¾e~kapacity jsou racionální. Pomìrnì nám to zjednodu¹í práci a~pøíli¹ nám to neublí¾í, nebo» práce s~reálnými èísly je stejnì pro~informatika pomìrnì zapeklitá.
 

-\s{První øe¹ení:} 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 $$\epsilon := \min_{e \in P} c(e) - f(e).$$ Nový tok $f'$ pak definujme jako $f'(e):=f(e) + \epsilon$. Kapacity nepøekroèíme ($\epsilon$ je nejvìt¹í mo¾ná hodnota, abychom tok zvìt¹ili, ale nepøekroèili kapaicitu ani jedné z~hran cesty $P$) a~Kirchhoffovy zákony zùstanou neporu¹eny, nebo» zdroj a~stok nezahrnují a~ka¾dému jinému vrcholu na~cestì $P$ se~pøítok $f^+(v)$ i~odtok $f^-(v)$ zvìt¹í pøesnì o~$\epsilon$.
+\s{První øe¹ení:} 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) + \epsilon$. Kapacity nepøekroèíme ($\epsilon$ je nejvìt¹í mo¾ná hodnota, abychom tok zvìt¹ili, ale nepøekroèili kapaicitu ani jedné z~hran cesty $P$) a~Kirchhoffovy zákony zùstanou neporu¹eny, nebo» zdroj a~stok nezahrnují a~ka¾dému jinému vrcholu na~cestì $P$ se~pøítok $f^+(v)$ i~odtok $f^-(v)$ zvìt¹í pøesnì o~$\epsilon$.

 
 \s{Otázka:} Najdeme takto ov¹em opravdu maximální tok?
 
 
 \s{Otázka:} Najdeme takto ov¹em opravdu maximální tok?
 


@@ -58,45 +65,41 @@ Pak m
 
 \figure{toky02.eps}{Èísla pøedstavují kapacity jednotlivých hran.}{1.5in}
 
 
 \figure{toky02.eps}{Èísla pøedstavují kapacity jednotlivých hran.}{1.5in}
 

-Nìkdy je potøeba poslat nìco i~v~protismìu. Definujme si~tedy rezervu hrany. Vyu¾ijeme zde, ¾e~sí» je symetrická.
+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.
+
+Nìkdy je tedy potøeba poslat nìco i~v~protismìru. Definujme si~{\I rezervu hrany}. Ta nám øíká, kolik mù¾eme daným smìrem je¹tì poslat. Vyu¾ijeme zde, ¾e~sí» je symetrická.

 
 \s{Definice:} {\I Rezerva hrany} $uv$ je $r(uv):=c(uv) - f(uv) + f(vu).$
 
 
 \s{Definice:} {\I Rezerva hrany} $uv$ je $r(uv):=c(uv) - f(uv) + f(vu).$
 

-Uka¾me si~tedy algoritmus, který rezervu vyu¾ívá a~doka¾me, ¾e~je koneèný a~najde maximální tok ke~ka¾dé racionální síti.
+Uka¾me si~nyní algoritmus, který rezervy vyu¾ívá, a~doka¾me, ¾e~je koneèný a~¾e najde maximální tok ka¾dé racionální sítì.

 
 \s{Algoritmus (Fordùv-Fulkersonùv)}
 
 \algo
 \:$f \leftarrow$ libovolný tok, napø. v¹ude nulový ($\forall e \in E: f(e) \leftarrow 0 $).
 \:Dokud $\exists P$ cesta ze $z$ do $s$ taková, ¾e~$\forall e \in P: r(e) > 0$, opakujeme:
 
 \s{Algoritmus (Fordùv-Fulkersonùv)}
 
 \algo
 \:$f \leftarrow$ libovolný tok, napø. v¹ude nulový ($\forall e \in E: f(e) \leftarrow 0 $).
 \:Dokud $\exists P$ cesta ze $z$ do $s$ taková, ¾e~$\forall e \in P: r(e) > 0$, opakujeme:

-\::$\epsilon \leftarrow \min \{r(e) \mid e \in P\}$.
+\::$\varepsilon \leftarrow \min \{r(e) \mid e \in P\}$.

 \::Pro v¹echny hrany $uv \in P$:
 \::Pro v¹echny hrany $uv \in P$:

-\:::$\delta \leftarrow min\{f(uv),\epsilon\}$
+\:::$\delta \leftarrow \min \{f(vu),\varepsilon\}$

 \:::$f(vu) \leftarrow f(vu) - \delta$
 \:::$f(vu) \leftarrow f(vu) - \delta$

-\:::$f(uv) \leftarrow f(uv) + \epsilon - \delta$
+\:::$f(uv) \leftarrow f(uv) + \varepsilon - \delta$

 \:Prohlásíme $f$ za~maximální tok.
 \endalgo
 
 \s{Problém:} Zastaví se~Fordùv-Fulkersonùv algoritmus?
 
 \itemize\ibull
 \:Prohlásíme $f$ za~maximální tok.
 \endalgo
 
 \s{Problém:} 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 zasatví po~nejvíce tolika krocích, jako je nìjaká horní závora pro~velikost maximálního toku -- napø. souèet kapacit v¹ech hran vedoucích do~stoku $$\sum_{u:us \in E}{c(us)}.$$
-\:Pro~racionální kapacity vyu¾ijeme jednoduchý trik -- kapacity vynásobíme spoleèným jmenovatelem a~pøevedeme na~pùvodní pøípad. Uvìdomme si, ¾e~algoritmus nikde kapacity hran nedìlí, tak¾e u¾ zùstanou celoèíselné, a~algoritmus se~tedy zastaví.
+\: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, jako je nìjaká horní závora pro~velikost maximálního toku -- napø. souèet kapacit v¹ech hran vedoucích do~stoku $$\sum_{u:us \in E}{c(us)}.$$
+\:Pro~racionální kapacity vyu¾ijeme jednoduchý trik -- kapacity vynásobíme spoleèným jmenovatelem a~pøevedeme na~pùvodní pøípad. Uvìdomme si, ¾e~algoritmus nikde kapacity hran ale ani toky na~hranách nedìlí, tak¾e u¾ zùstanou celoèíselné. A tak jsme pøevedli racionální kapacity na~celoèíselné, pro~které u¾ víme, ¾e~se algoritmus zastaví.

 \:Na~síti s~iracionálními kapacitami se~algoritmus chová mnohdy divoce, nemusí se~zastavit ale dokonce ani konvergovat ke~správnému výsledku.
 \s{K zamy¹lení:} Zkuste vymyslet pøíklad takové sítì.
 \endlist
 
 \s{Otázka:} Vydá algoritmus maximální tok?
 
 \:Na~síti s~iracionálními kapacitami se~algoritmus chová mnohdy divoce, nemusí se~zastavit ale dokonce ani konvergovat ke~správnému výsledku.
 \s{K zamy¹lení:} Zkuste vymyslet pøíklad takové sítì.
 \endlist
 
 \s{Otázka:} Vydá algoritmus maximální tok?
 

-\s{Odpovìï:} Vydá. Abychom si~to dokázali, zaveïme si~øezy a~pou¾ijme je jako certifikát pravdivosti tvrzení, ¾e~algoritmus vydá maximální tok.
+\s{Odpovìï:} Vydá. Abychom si~to dokázali, zaveïme si~øezy a~pou¾ijme je jako certifikát maximality nalezeného toku.

 
 

-\s{Definice:} {\I Øez} je uspoøádaná dvojice mno¾in vrcholù ($A,B$) taková, ¾e:
-\itemize\ibull
-\:$A \cap B = \emptyset$.
-\:$A \cup B = V$.
-\:$z \in A$.
-\:$s \notin 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 tok. Neboli $A \cap B = \emptyset$, $A \cup B = V$, $z \in A$, $s \notin B$.

 
 \s{Definice:} {\I Hrany øezu} $E(A,B) := E \cap A \times B$.
 
 
 \s{Definice:} {\I Hrany øezu} $E(A,B) := E \cap A \times B$.
 


@@ -114,41 +117,41 @@ $$f(A,B) = \sum_{e \in (A,B)}{f(e)} - \sum_{e \in E(B,A)}{f(e)} \leq \sum_{e \in
 
 \s{Lemmátko:} Pro~ka¾dý tok $f$ a~pro~ka¾dý øez $(A,B)$ platí $f(A,B) = \vert f \vert$.
 
 
 \s{Lemmátko:} Pro~ka¾dý tok $f$ a~pro~ka¾dý øez $(A,B)$ platí $f(A,B) = \vert f \vert$.
 

-\proof{Indukcí a~obrázkem}
+\proof{Indukcí a~obrázkem.}

 
 

-Zaèneme s øezem ($V \setminus \{s\}, \{s\}$). Pro~tento øez lemma platí z~definice velikosti toku.
+Zaèneme s øezem ($V \setminus \{s\}, \{s\}$). Pro~tento øez lemma platí z~definice velikosti toku. Dále budu postupnì pøesouvat vrcholy z~mno¾iny $B$ do~mno¾iny $A$. Libovolý øez mù¾e být takto vytvoøen z~toho triviálního. 

 
 

-Dále si~pøedstavme, ¾e~máme ji¾ libovolný øez ($A,B$) a~pøesouváme vrchol $v$ z~$A$ do~$B$. Tedy $A' = A \setminus \{v\}$ a $B' = B \cup \{v\}$.
+Pøedstavme si, ¾e~máme ji¾ libovolný øez ($A,B$) a~pøesouváme vrchol $v$ z~$A$ do~$B$. Tedy $A' = A \setminus \{v\}$ a $B' = B \cup \{v\}$.

 
 

-Uvìdomme si, ¾e~v¹echny hrany jednoho typu (napø. vedoucí z~$A$ do~$v$) se~chovají stejnì, tak¾e staèí uva¾ovat hrany pouze 4 typù:
+Uvìdomme si, ¾e~v¹echny hrany jednoho typu (napø. vedoucí z~$A$ do~$v$) se~chovají stejnì, tak¾e staèí uva¾ovat hrany pouze 4 typù (+ ostatní hrany (ty, které pøesun neovlivní) oznaèíme $\varepsilon$):

 \itemize\ibull
 \:$\alpha$ -- hrany vedoucí z~$A$ do~$v$
 \:$\beta$ -- hrany vedoucí z~$v$ do~$B$
 \:$\gamma$ -- hrany vedoucí z~$v$ do~$A$
 \:$\delta$ -- hrany vedoucí z~$B$ do~$v$
 \itemize\ibull
 \:$\alpha$ -- hrany vedoucí z~$A$ do~$v$
 \:$\beta$ -- hrany vedoucí z~$v$ do~$B$
 \:$\gamma$ -- hrany vedoucí z~$v$ do~$A$
 \:$\delta$ -- hrany vedoucí z~$B$ do~$v$

-\:$\epsilon$ -- hrany øezu stejné pøed pøesunem i~po~pøesunu

 \endlist
 
 \endlist
 

+

 \figure{toky03.eps}{Pøesun vrcholu $v$ z~$A$ do~$B$.}{1in}
 
 \figure{toky03.eps}{Pøesun vrcholu $v$ z~$A$ do~$B$.}{1in}
 

-Potom pøed pøesunem ($v \in A$) se~$f(A,B)$ skládá z~$\epsilon + \beta - \delta$. Po~pøesunu ($v \in B$) se~$f(A',B')$ skládá z~$\epsilon + \alpha - \gamma$. Rozdíl tìchto hodnot je $\alpha + \delta - \beta - \gamma$.
+Pøed pøesunem ($v \in A$) se~$f(A,B)$ skládá z~$\varepsilon + \beta - \delta$. Po~pøesunu ($v \in B$) se~$f(A',B')$ skládá z~$\varepsilon + \alpha - \gamma$. Rozdíl tìchto hodnot je $\alpha + \delta - \beta - \gamma$.

 
 

-Nicménì z Kirchhoffova zákonu o~vrcholu $v$ (co¾ není ani zdroj ani stok) víme, ¾e~$\alpha + \delta - \beta - \gamma = f^\Delta(v) = 0$, nebo» $\alpha + \delta $ je to, co do~$v$ pøitéká a~$\beta + \gamma$ je to, co z~$v$ vytéká. Tedy tok pøes øez pøed pøesunem je stejnì velký jako tok pøes øez po~pøesunu. Pokud tedy lemma platilo pøed pøesunem, musí platit i~po~pøesunu.
+Nicménì z Kirchhoffova zákonu o~vrcholu $v$ (co¾ není ani zdroj ani stok) víme, ¾e~$\alpha + \delta - \beta - \gamma = f^\Delta(v) = 0$, nebo» $\alpha + \delta $ je to, co do~$v$ pøitéká, a~$\beta + \gamma$ je to, co z~$v$ vytéká. Tedy tok pøes øez pøed pøesunem je stejnì velký jako tok pøes øez po~pøesunu. Pokud lemma platilo pøed pøesunem, musí platit i~po~pøesunu.

 \qed
 
 \s{Dùsledek:} Pro~ka¾dý tok $f$ a~øez ($A,B$) platí, ¾e~$\vert f \vert = f(A,B) \leq c(A,B)$.
 
 \qed
 
 \s{Dùsledek:} Pro~ka¾dý tok $f$ a~øez ($A,B$) platí, ¾e~$\vert f \vert = f(A,B) \leq c(A,B)$.
 

-\s{Pozorování:} Pokud najdeme dvojici tok $f$ a~øez $(A,B)$ takovou, ¾e~platí $\vert f \vert = c(A,B)$, tak jsme na¹li maximální tok a~minimální øez.
+\s{Pozorování:} Pokud najdeme dvojici tok $f$ a~øez $(A,B)$ takovou, ¾e~platí $\vert f \vert = c(A,B)$, pak tok $f$ je maximální a~ øez $(A,B)$ minimální.

 
 \s{Vìta:} Pokud se~Fordùv-Fulkersonùv algoritmus zastaví, tak vydá maximální tok.
 
 \proof
 
 
 \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 $A = \{v \in V ; \exists $ 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 $A = \{v \in V ; \exists$~cesta ze~$z$ do~$v$ jdoucí po~hranách s~$r > 0\}$ a~$B = V \setminus A$.

 
 

-Uvìdomme si, ¾e~($A,B$) je øez, nebo» $z \in A$ (ze~$z$ do~$z$ existuje cesta délky 0) a~$s \notin B$ (kdyby $s \in B$, tak by musela existovat cesta ze~$z$ do~$s$ s~kladnou rezervou, tudí¾ by ale algoritmus neskonèil, nýbr¾ tuto cestu vzal a~stávající tok vylep¹il). 
+Uvìdomme si, ¾e~($A,B$) je øez, nebo» $z \in A$ (ze~$z$ do~$z$ existuje cesta délky 0) a~$s \notin B$ (kdyby $s \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, neboli $\forall uv \in E(A,B) : r(uv) = 0$ (kdyby mìla hrana $uv$ rezervu nenulovou, tedy kladnou, tak by patøil vrchol $v$ 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 tedy øez $(A,B)$ takový, ¾e~$f(A,B) = c(A,B)$. To znamená, ¾e~jsme na¹li maximální tok a~minimální øez.
+Dále víme, ¾e~v¹echny hrany øezu mají nulovou rezervu, neboli $\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(A,B) = c(A,B)$. To znamená, ¾e~jsme na¹li maximální tok a~minimální øez.

 \qed
 
 Zformulujme si, co jsme zjistili a~dokázali o~algoritmu pánù Forda a~Fulkersona.
 \qed
 
 Zformulujme si, co jsme zjistili a~dokázali o~algoritmu pánù Forda a~Fulkersona.


@@ -156,10 +159,10 @@ Zformulujme si, co jsme zjistili a~dok
 \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:} (Fordova-Fulkersonova)
 \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:} (Fordova-Fulkersonova)

-$$\min_{(A,B)} c(A,B) = \max_f \vert f \vert .$$
+$$\min_{(A,B)~øez} c(A,B) = \max_{f~tok} \vert f \vert .$$

 \proof
 
 \proof
 

-Ji¾ víme, ¾e~$\min_{(A,B)} c(A,B) \geq \max_f \vert f \vert$. Staèí tedy dokázat, ¾e~v¾dy existuje tok $f$ a~øez ($A,B$) takové, ¾e~$c(A,B) = \vert f \vert$. Pro~racionální kapacity nám Fordùv-Fulkersonùv algoritmus takový tok (maximální) a~øez (minimální) vydá. Jak je to ale s~reálnými kapacitami? Vyu¾ijeme tvrzení, ¾e~maximální tok existuje v¾dy. Pak mù¾eme spustit Fordùv-Fulkersonùv algoritmus rovnou na~tento maximální tok. Algoritmus se~nutnì ihned zastaví, nebo» neexistuje cesta, která by mìla alespoò jednu hranu s~kladnou rezervu. A~my víme, ¾e~pokud se~algoritmus zastaví, tak vydá minimální øez. Proto i~pro sí» s~reálnými kapacitami platí, ¾e~existuje maximální tok $f$ a~minimální øez $(A,B)$ a $c(A,B) = \vert f \vert$.
+Ji¾ víme, ¾e~$\min_{(A,B)} c(A,B) \geq \max_f \vert f \vert$. Staèí tedy dokázat, ¾e~v¾dy existují tok $f$ a~øez ($A,B$) takové, ¾e~$c(A,B) = \vert f \vert$. Pro~racionální kapacity nám Fordùv-Fulkersonùv algoritmus takový tok (maximální) a~øez (minimální) vydá. Jak je to ale s~reálnými kapacitami? Vyu¾ijeme tvrzení, ¾e~maximální tok existuje v¾dy. Pak mù¾eme spustit Fordùv-Fulkersonùv algoritmus rovnou na~tento maximální tok (místo nulového). Algoritmus se~nutnì ihned zastaví, nebo» neexistuje cesta, která by mìla alespoò jednu hranu s~kladnou rezervou. A~my víme, ¾e~pokud se~algoritmus zastaví, tak vydá minimální øez. Proto i~pro sí» s~reálnými kapacitami platí, ¾e~existuje maximální tok $f$ a~minimální øez $(A,B)$ a $c(A,B) = \vert f \vert$.

 \qed
 
 \s{Vìta:}
 \qed
 
 \s{Vìta:}


@@ -169,14 +172,21 @@ S
 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
 
 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. 
+

 \s{Aplikace:} Hledání maximálního párování v~bipartitních grafech.
 
 \s{Aplikace:} Hledání maximálního párování v~bipartitních grafech.
 

-\s{Definice:} Mno¾ina hran $F \subseteq E$ sevnazývá párování $\equiv \forall e,f \in F : e \cap f = \emptyset$.
+\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$.

 
 \s{Definice:} Párování je maximální, pokud obsahuje nejvìt¹í mo¾ný poèet hran.
 
 
 \s{Definice:} Párování je maximální, pokud obsahuje nejvìt¹í mo¾ný poèet hran.
 

-Mìjme bipartitní graf $G = (V,E)$. Na~nìm hledáme maximální 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. Nyní staèí jen na~tuto sí» spustit Fordùv-Fulkersonùv algoritmus a~a¾~dobìhne, tak prohlásit hrany s~kapacitami 1 za~maximální párování.
+Mìjme bipartitní graf $G = (V,E)$. V~nìm hledáme maximální 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~kapacitami 1 za~maximální párování.

 
 \figure{toky04.eps}{Hledání maximálního párování v~bipartitním grafu.}{2in}
 
 
 \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 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))$. Forù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))$.
+
+

 \bye
 \bye