X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=3-goldberg%2F3-goldberg.tex;h=92cc877b54d514d69b562b31c6ca303209353602;hb=4de3e77f9c20bc20a71bdd3beb2b94d70270dcc6;hp=ce5857f7dd67113d20c97ec94f599288a19fc395;hpb=665d33beeafeb38c0b3aacefeadb73764ff9e6a6;p=ads2.git

diff --git a/3-goldberg/3-goldberg.tex b/3-goldberg/3-goldberg.tex
index ce5857f..92cc877 100644
--- a/3-goldberg/3-goldberg.tex
+++ b/3-goldberg/3-goldberg.tex
@@ -256,7 +256,7 @@ Rozd
 Teï potøebujeme odhadnout, kolik nás budou stát oba typy fází. Zaènìme s~tìmi jednodu¹¹ími -- s~lacinými. Víme, ¾e~v¹ech fází je~$\O(N^2)$. Tìch laciných bude tedy urèitì také~$O(N^2)$. Nenasycených pøevedení se~bìhem jedné laciné fáze provede nejvíce~$K$. Tedy celkem se~bìhem laciných fází provede~$\O(N^2K)$ nenasycených pøevedení.
 
 Pro~poèet nenasycených pøevedení v~drahých fázích si~zaveïme nový potenciál definovaný následovnì:
-$$\Phi := \sum_{\scriptstyle{v \ne z,s} \atop \scriptstyle{f^{\Delta}(v) = 0}} {p(v) \over K},$$
+$$\Phi := \sum_{\scriptstyle{v \ne z,s} \atop \scriptstyle{f^{\Delta}(v) \ne 0}} {p(v) \over K},$$
 kde~$p(v)$ je poèet takových vrcholù~$u$, které nejsou vý¹e ne¾~$v$. Neboli
 $$p(v) = \vert \{ u \in V \mid h(u) \leq h(v) \} \vert.$$
 Tedy platí, ¾e~$p(v)$ je v¾dy nezáporné a~nejvý¹e má hodnotu~$N$. Dále víme, ¾e~$\Phi$ bude v¾dy nezáporné (nebo» je to souèet nezáporných èlenù) a~nejvý¹e bude nabývat hodnoty~$N^2 \over K$. Rozmysleme si, jak nám ovlivní tento potenciál na¹e tøi operace: