Oprava definice separatoru.

[ads2.git] / 4-goldberg / 4-goldberg.tex

diff --git a/4-goldberg/4-goldberg.tex b/4-goldberg/4-goldberg.tex
index 76e0fc3ff2a0b6d94c3c7e27ad5ca4db07971e7f..9d996b4a5c159520e765847fb100f080c7ae7301 100644 (file)
--- a/4-goldberg/4-goldberg.tex
+++ b/4-goldberg/4-goldberg.tex
@@ -1,4 +1,4 @@
-%version 1.6
+%version 1.8
 
 \input lecnotes.tex
 
@@ -29,7 +29,7 @@ D
 Pokud platí, ¾e:
 \numlist \ndotted
        \:ve~vrcholu~$u$ je nenulový pøebytek, tj. $f^{\Delta}(u) > 0$,
-       \:vrchol~$u$ je vý¹ ne¾ vrchol~$v$, tj. $h(u) > h(v)$ a
+       \:vrchol~$u$ je vý¹ ne¾ vrchol~$v$, tj. $h(u) > h(v)$, a
        \:hrana $uv$ má nenulovou rezervu, tj. $r(uv)>0$,
 \endlist
 \noindent pøevedeme tok o~velikosti $\delta:=\min(f^{\Delta}(u),r(uv))$ z~$u$ do~$v$ tímto zpùsobem:
@@ -53,7 +53,7 @@ Pokud b
 \:$\forall e \in E: f(e)\leftarrow 0$ (po~hranách na~poèátku nenecháme protékat nic).
 \:$\forall zu \in E : f(zu)\leftarrow c(zu)$ (ze~zdroje pustíme maximální mo¾nou vlnu).
 \:Dokud $\exists u \in V \setminus \{z,s\}, f^{\Delta}(u)>0$: 
-\::Pokud $\exists uv \in E, r(uv)>0$ a $h(u)>h(v)$, pøevedeme pøebytek po~hranì $uv$.
+\::Pokud $\exists uv \in E, r(uv)>0$ a $h(u)>h(v)$: pøevedeme pøebytek po~hranì $uv$.
 \::V~opaèném pøípadì zvedneme $u$.
 \:Vrátíme tok $f$ jako výsledek.
 \endalgo
@@ -78,7 +78,7 @@ Pod
 \proof
 Nejprve uká¾eme, ¾e $f$ je tok, a pak jeho maximalitu. Vyjdìme z~toho, ¾e $f$ je vlna a algoritmus se mù¾e zastavit, jen pokud nastanou oba následující pøípady souèasnì:
 \itemize\ibull
-\:Ve~vrcholech grafu nejsou ¾ádné pøebytky (mimo $z$ a $s$), proto¾e jinak by se algoritmus nezastavil a pokraèoval dále ve~výpoètu. Tudí¾ $f$ je tok. %todo check ? mimo~ ?
+\:Ve~vrcholech grafu nejsou ¾ádné pøebytky (mimo $z$ a~$s$), proto¾e jinak by se algoritmus nezastavil a pokraèoval dále ve~výpoètu. Tudí¾ $f$ je tok.
 \:Neexistuje nenasycená cesta ze~zdroje do~stoku, èím¾ z~{\I Ford-Fulkersonovy vìty} okam¾itì vyplývá, ¾e $f$ je tok maximální. A jak tuto neexistenci nahlédneme? Pro~spor pøedpokládejme, ¾e nìjaká nenasycená cesta~$P$ ze~$z$ do~$s$ existuje. Tato cesta mù¾e mít maximálnì $N-1$ hran. O~nich víme, ¾e v¹echny mají kladnou rezervu, a dále víme, ¾e po~celou dobu výpoètu je vý¹ka zdroje $N$ a vý¹ka stoku $0$. Tak¾e celkový spád cesty $P$ je $N$, co¾ ale znamená, ¾e na cestì $P$ existuje hrana s~kladnou rezervou, která má spád alespoò $2$. To je v¹ak v~rozporu s~invariantem~S.
 \qeditem
 \endlist