Dinic: Preznaceni obrazku (s,t -> z,s)

[ads2.git] / 12-apx / 12-apx.tex

diff --git a/12-apx/12-apx.tex b/12-apx/12-apx.tex
index 193bb49f362f32d3d6c5dd0c949f9202bd916458..aa6fb39d9c98aa537d9a72339e90addef9be0ab9 100644 (file)
--- a/12-apx/12-apx.tex
+++ b/12-apx/12-apx.tex
@@ -181,7 +181,7 @@ $(1+\varepsilon)$-aproxima
 \proof Uká¾eme, ¾e v~takovém pøípadì doká¾eme v~polynomiálním èase zjistit,
 zda v grafu existuje hamiltonovská kru¾nice.
 
-\>Dostali jsme graf~$G$, v~kterém hledáme hamiltonovskou kru¾nici. Doplníme
+\>Dostali jsme graf~$G$, ve~kterém hledáme hamiltonovskou kru¾nici. Doplníme
 $G$ na~úplný graf~$G'$ a~váhy hran~$G'$ nastavíme takto:
 \itemize\ibull
 \: $w(e) = 1$, kdy¾ $e \in E(G)$
@@ -190,7 +190,7 @@ $G$ na~
 \>Konstantu $c$ potøebujeme zvolit tak velkou, abychom jasnì poznali, jestli
 je ka¾dá hrana z nalezené hamiltonovské kru¾nice hranou grafu $G$ (pokud by
 nebyla, bude kru¾nice obsahovat aspoò jednu hranu s váhou $c$, která vy¾ene
-souèet poznatelnì vysoko). Pokuï existuje hamiltonovská kru¾nice v~$G'$ slo¾ená jen
+souèet poznatelnì vysoko). Pokud existuje hamiltonovská kru¾nice v~$G'$ slo¾ená jen
 z~hran, které byly
 pùvodnì v~$G$, pak optimální øe¹ení bude mít váhu~$n$, jinak bude urèitì
 minimálnì $n-1+c$. Kdy¾ máme aproximaèní algoritmus s~pomìrem~$1+\varepsilon$,
@@ -207,7 +207,7 @@ na~hamiltonovskou kru
 
 \s{Poznámka:} O existenci pseudopolynomiálního algoritmu
 platí analogická vìta, a doká¾e se analogicky -- existující hrany budou
-mít hranu 1, neexistující váhu 2.
+mít váhu 1, neexistující váhu 2.
 
 \h{Aproximaèní schéma pro problém batohu}