Oprava prevodu hamiltonovske kruznice na obchodniho cestujiciho bez

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

diff --git a/4-goldberg/4-goldberg.tex b/4-goldberg/4-goldberg.tex
index 6d22bba17d03144a695e50d4184a1d0a0b5dff20..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
 
@@ -13,7 +13,7 @@ P
 Tento algoritmus narozdíl od~Dinicova algoritmu zaèíná s~pøebytky v~sousedních vrcholech zdroje a sna¾í se jich zbavit pomocí pøevádìní. Pokud bychom toto pøevádìní dìlali \uv{tupým zpùsobem}, mohl by se algoritmus zacyklit. Proto pro~ka¾dý vrchol budeme definovat vý¹ku, a jak uvidíme, s~její pomocí se vyhneme zacyklení. 
 
 \s{Definice:} Funkce $f:E \rightarrow {\bb R}_{0}^{+}$ 
-je {\I vlna} v~síti~$(V, E, z, s, c)$ tehdy, kdy¾ $ \forall uv \in E : f(uv) \leq c(uv) $, kde $c(uv)$ je kapacita hrany~$uv$, a $ \forall v \ne z, s : f^{\Delta}(v) \geq 0 $. Funkcí $f^{\Delta}(v)$ rozumíme {\I pøebytek}, který pøebývá ve~vrcholu~$v$, co¾ je souèet v¹eho, co do~vrcholu~$v$ pøiteèe, mínus souèet v¹eho, co z~$v$ odteèe. To mù¾eme zapsat jako:
+je {\I vlna} v~síti~$(V, E, z, s, c)$ tehdy, kdy¾ $ \forall uv \in E : f(uv) \leq c(uv) $, kde $c(uv)$ je kapacita hrany~$uv$, a $ \forall v \ne z, s : f^{\Delta}(v) \geq 0 $. Funkcí $f^{\Delta}(v)$ pro libovolný vrchol~$v$ rozumíme {\I pøebytek} v~tomto vrcholu, co¾ je souèet v¹eho, co do~vrcholu~$v$ pøiteèe, minus souèet v¹eho, co z~$v$ odteèe. To mù¾eme zapsat jako:
  $$f^{\Delta}(v):=\sum_{uv \in E}{f(uv)} - \sum_{vu \in E}{f(vu)}.$$
 Ka¾dý tok je vlna, kde $\forall v \ne z,s: f^{\Delta}(v) = 0$.
 
@@ -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