Voroneho diagramy: Oprava preklepu

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

diff --git a/4-goldberg/4-goldberg.tex b/4-goldberg/4-goldberg.tex
index c7cffd2f2677fe835dc84e5e451b648561509ab5..c7f53bfd55f081ed184e2a8ce9bf586347e8f701 100644 (file)
--- a/4-goldberg/4-goldberg.tex
+++ b/4-goldberg/4-goldberg.tex
@@ -149,7 +149,7 @@ Pak existuje nenasycen
 \proof
 Buï~$v$ vrchol s~kladným pøebytkem.
 Uva¾me mno¾inu $A := \{ u \in V \mid \hbox{existuje nenasycená cesta z~$v$ do~$u$} \}$.
-Uká¾eme, ¾e tato mno¾ína obsahuje zdroj.
+Uká¾eme, ¾e tato mno¾ina obsahuje zdroj.
 
 Pou¾ijeme u¾ mírnì okoukaný trik: seèteme pøebytky ve~v¹ech vrcholech mno¾iny~$A$.
 V¹echny hrany le¾ící celé uvnitø~$A$ nebo celé venku pøispìjí dohromady nulou.
@@ -224,6 +224,26 @@ v
 dohromady nejvý¹e~$nm$.
 \qed
 
+\s{Potenciálová metoda:}
+Pøedchozí dvì lemmata jsme dokazovali \uv{lokálním} zpùsobem -- zvednutí jsme poèítali
+pro ka¾dý vrchol zvlá¹» a nasycená pøevedení pro ka¾dou hranu. Tento pøístup pro nenasycená
+pøevedení nefunguje, jeliko¾ jich lokálnì mù¾e být velmi mnoho.
+Podaøí se nám nicménì omezit jejich celkový poèet.
+
+Jedím ze~zpùsobù, jak taková \uv{globální} tvrzení o~chování algoritmù dokazovat,
+je pou¾ít {\I potenciál.} To je nìjaká {\I nezáporná} funkce, která popisuje stav výpoètu.
+Pro ka¾dou operaci pak stanovíme, jaký vliv má na hodnotu potenciálu. Z~toho odvodíme,
+¾e operací, které potenciál sni¾ují, nemù¾e být výraznì více ne¾ tìch, které ho zvy¹ují.
+Jinak by toti¾ potenciál musel nìkdy bìhem výpoètu klesnout pod nulu.
+
+S~tímto druhem dùkazu jsme se vlastnì u¾ setkali. To kdy¾ jsme v~kapitole o~vyhledávání v~textu
+odhadovali poèet prùchodù po~zpìtných hranách. Roli potenciálu tam hrálo èíslo stavu.
+
+V~následujícím lemmatu bude potenciál trochu slo¾itìj¹í. Zvolíme ho tak, aby
+operace, jejich¾ poèty u¾ známe (zvednutí, nasycené pøevedení), pøispívaly
+nanejvý¹ malými kladnými èísly, a~nenasycená pøevedení potenciál v¾dy
+sni¾ovala.
+
 \s{Lemma N (Nenasycená pøevedení):} Poèet v¹ech nenasycených pøevedení je~$\O(n^2m)$.
 
 \proof
@@ -296,7 +316,7 @@ Podle lemmatu~K po~zastaven
 
 \h{Vylep¹ení Goldbergova algoritmu}
 
-Základní verze Goldbervova algoritmu tedy dosáhla stejné slo¾itosti jako Dinicùv algoritmus.
+Základní verze Goldbergova algoritmu tedy dosáhla stejné slo¾itosti jako Dinicùv algoritmus.
 Nyní uká¾eme, ¾e pokud budeme volit vrchol, ze~kterého budeme pøevádìt pøebytek, ¹ikovnìji
 -- toti¾ jako nejvy¹¹í z~vrcholù s~nenulovým pøebytkem~--, slo¾itost se je¹tì zlep¹í.