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 25697a7e19c0fcb135ad189fcfd486eedd5770e1..aa6fb39d9c98aa537d9a72339e90addef9be0ab9 100644 (file)
--- a/12-apx/12-apx.tex
+++ b/12-apx/12-apx.tex
@@ -8,8 +8,8 @@ probl
 
 \h{Co dìlat, kdy¾ potkáme NP-úplný problém}
 \algo
-\:Nepanikaøit
-\:Spokojit se s~málem
+\:Nepanikaøit.
+\:Spokojit se s~málem.
 \:Rozmyslet, jestli opravdu potøebujeme obecný algoritmus. Mnohdy potøebujeme pouze
 speciálnìj¹í pøípady, které mohou být øe¹itelné v~polynomiálním èase.
 \:Spokojit se s~pøibli¾ným øe¹ením, (pou¾ít aproximaèní algoritmus).
@@ -120,7 +120,7 @@ pomoct t
 
 \s{Problém: Obchodní cestující}
 
-\>{\I Vstup:} neorientovaný graf~$G$, ka¾dá hrana
+\>{\I Vstup:} Neorientovaný graf~$G$, ka¾dá hrana
 je ohodnocená funkcí $w: E(G)\rightarrow {\bb R }^+_0$.
 
 \>{\I Výstup:} Hamiltonovská kru¾nice (obsahující v¹echny vrcholy grafu), a~to ta nejkrat¹í
@@ -159,7 +159,7 @@ hamiltonovsk
 
 Kdy¾ máme hamiltonovskou kru¾nici $C$ a z~ní vy¹krtneme hranu, dostaneme kostru
 grafu~$G$ s~váhou men¹í ne¾ $C$ -- ale ka¾dá kostra je alespoò tak tì¾ká
-jako minimální kostra $T$. Tedy optimální Hamiltonovská kru¾nice je urèitì tì¾¹í
+jako minimální kostra $T$. Tedy optimální hamiltonovská kru¾nice je urèitì tì¾¹í
 ne¾ minimální kostra $T$. Kdy¾ tyto dvì nerovnosti slo¾íme
 dohromady, algoritmus nám vrátí hamiltonovskou kru¾nici $T'$ s~váhou nanejvý¹
 dvojnásobnou vzhledem k optimální hamiltonovské kru¾nici ($T' \leq 2T < 2C$). Takovéto
@@ -181,16 +181,16 @@ $(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)$
 \: $w(e) = c \gg 1$, kdy¾ $e \not\in E(G)$
 \endlist
 \>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
+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$,
@@ -202,12 +202,12 @@ $$
 }
 $$
 \>Kdyby takový algoritmus existoval, máme polynomiální algoritmus
-na~Hamiltonovsku kru¾nici.
+na~hamiltonovskou kru¾nici.
 \qed
 
 \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}