X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=4-goldberg%2F4-goldberg.tex;h=9d996b4a5c159520e765847fb100f080c7ae7301;hb=4cfb6d2e01203214077c2cfe2bc984e8aae1aebd;hp=56f39ca79669a48a87d7952d36f29539018b57ff;hpb=be3502110aea505a6f8aa610374f58670c325524;p=ads2.git

diff --git a/4-goldberg/4-goldberg.tex b/4-goldberg/4-goldberg.tex
index 56f39ca..9d996b4 100644
--- a/4-goldberg/4-goldberg.tex
+++ b/4-goldberg/4-goldberg.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$.