-\h{Druhý spôsob: Aproximácia}
-
-\>V predchádzajúcich problémoch sme sa zamerali na ¹peciálne prípady. Obèas v¹ak také ¹tastie nemáme a~musíme vyrie¹i» celý NP-úplný problém. Mo¾eme si v¹ak pomôc» tým, ¾e sa nebudeme sna¾i» vyrie¹i» ho optimálne -- iba v nejakom pomere k~optimálnosti ({\I aproximácia}), t.j. budeme vedie», o~koµko maximálne je na¹e rie¹enie hor¹ie ako optimálne.
-
-\s{Problém: Obchodný cestujúci}
-
-\>{\I Vstup:} neorientovaný graf $G$, popisujúci nejaku krajinu a~ka¾dá hrana je ohodnotená funkciou $w: E(G)\rightarrow {\bb R}^+_0$
-
-\>{\I Vystup:} Hamiltonovská kru¾nica (v¹etky vrcholy grafu), a~to tá najkrat¹ia (podµa ohodnotenia).
-
-\>Tento problém je hneï na~prvý pohµad nároèný -- u¾ problém, èi existuje Hamiltonovská kru¾nica, je NP-úplný. BUNV nech graf~$G$ je úplný (doplnime zvy¹né hrany ohodnotené $max(w)+1$ alebo viac, nie v¹ak nekoneènom, lebo by neplatila trojuholníková nerovnos», ktorú neskôr budeme potrebova»). Vyrie¹me tento problém najprv za~predpokladu, ¾e vrcholy grafu spåòajú trojuholníkovú nerovnos», potom bez nej.
-
-\>{\I a) trojuholníková nerovnos»:} $\forall x,y,z \in V: w(xz)\le w(xy)+w(yz)$
-
-\>Existuje pekný algoritmus, ktory nájde Hamiltonovsku kru¾nicu, èo je
-maximálne dvakrát tak veµká ako optimálna.
-
-\>Nájdeme najmen¹iu kostru a~obchodnému cestujúcemu poradíme, nech ide po~nej (staèí zakoreni» a~prejs» do~håbky). Problémom v¹ak je, ¾e daný sled obsahuje ka¾dý vrchol viackrát a~preto musíme nahradi» nepovolené vracania sa, t.j.~pre ka¾dý vrchol nájs» e¹te nenav¹tívený vrchol v~na¹om slede a~ís» priamo naò. Keï¾e platí trojuholníková nerovnos», tak si týmito skratkami neu¹kodíme. Nech minimálna kostra má váhu~$T$. Váha obídeného sledu tak bude~$2T$. Skrátenia urèite nezväè¹ujú, tak¾e váha nájdene Hamiltonovskej kru¾nice bude nanajvý¹~$2T$.
-
-\>Ak máme Hamiltonovskú kru¾nicu~$C$ a~z~nej vy¹krtneme hranu, tak máme kostru grafu~$G$ s~váhou najviac~$w(C)$, teda to aspoò takú, aká je váha minimálnej kostry --~$T$. To je optimálny prípad Hamiltonovskej kru¾nice. Ak to teda zlo¾íme dohromady, algoritmus nám vráti Hamiltonovskú kru¾nicu s~váhou najviac dvojnásobnou od~optimálnej Hamiltonovskej kru¾nice. Takéto algoritmy sa nazývajú {\I 2-aproximaèné}, keï¾e rie¹enie je maximálne dvojnásobné od~optimálneho.
-
-\>{\I b) bez~trojuholníkovej nerovnosti:}
-
-\>Tu sa budeme naopak sna¾i» ukáza», ¾e ¾iaden polynomiálny aproximaèný algoritmus neexistuje.
-
-\s{Veta:} Ak existuje polynomiálny $(1+\varepsilon)$-aproximaèný algoritmus pre~algoritmus obchodného cestujúceho bez~trojuholníkovej nerovnosti pre~µubovoµné $\varepsilon>0$, tak potom $P = NP$.
-
-\proof Uká¾eme, ¾e v~tom prípade doká¾eme v~polynomiálnom èase nájs» Hamiltonovskú kru¾nicu.
-
-\>Dostali sme graf $G$, v~ktorom hµadáme Hamiltonovskú kru¾nicu. Doplníme $G$ na~uplný graf~$G'$ a~váhy hrán~$G'$ nastavíme takto:
+\h{Druhý zpùsob: Aproximace}
+
+\>V pøedcházejících problémech jsme se zamìøili na~speciální pøípady. Obèas v¹ak
+takové ¹tìstí nemáme a musíme vyøe¹it celý NP-úplný problém. Mù¾eme si v¹ak
+pomoct tím, ¾e se ho nebudeme sna¾it vyøe¹it optimálnì -- namísto optimálního
+øe¹ení najdeme nìjaké, které je nejvý¹e $c$-krát hor¹í pro nìjakou konstantu $c$.
+
+\s{Problém: Obchodní cestující}
+
+\>{\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¹í
+(podle ohodnocení).
+
+\>Tento problém je hned na~první pohled nároèný -- u¾ sama existence
+hamiltonovské kru¾nice je NP-úplná. Najdeme aproximaèní algoritmus nejprve za pøedpokladu,
+¾e vrcholy splòují trojúhelníkovou nerovnost (tj. $\forall x,y,z \in V: w(xz)\le
+w(xy)+w(yz)$), potom uká¾eme, ¾e v úplnì obecném pøípadé by samotná existence
+aproximaèního algoritmu implikovala ${\rm P=NP }$.
+
+\>{\I a) trojúhelníková nerovnost:}
+
+Existuje pìkný algoritmus, který najde hamiltonovskou kru¾nici o délce $\leq
+2\cdot opt$, kde $opt$ je délka nejkrat¹í hamiltonovské kru¾nice.
+Vedle pøedpokladu trojúhelníkové
+nerovnosti budeme potøebovat, aby ná¹ graf byl úplný. Souhrnnì mù¾eme
+pøedpokládat, ¾e úlohu øe¹íme v nìjakém metrickém protoru, ve kterém jsou obì
+podmínky podle definice splnìny.
+
+Najdeme nejmen¹í kostru grafu a obchodnímu cestujícímu poradíme, a» jde po~ní -- kostru
+zakoøeníme a projdeme jako strom do hloubky, pøièem¾ se zastavíme a¾ v koøeni po projití
+v¹ech vrcholù. Problém v¹ak je, ¾e prùchod po kostøe obsahuje
+nìkteré vrcholy i hrany vícekrát, a proto musíme nahradit nepovolené vracení se.
+Máme-li na nìjaký vrchol vstoupit podruhé, prostì ho ignorujeme a pøesuneme se
+rovnou na dal¹í nenav¹tívený -- dovolit si to mù¾eme, graf je úplný a obsahuje
+hrany mezi v¹emi dvojicemi vrcholù
+(jinak øeèeno, poøadí vrcholù kru¾nice bude preorder výpis prùchodem do hloubky).
+Pokud platí trojúhelníková nerovnost, tak si tìmito zkratkami neu¹kodíme.
+Nech» minimální kostra má váhu~$T$. Pokud bychom pro¹li celou kostru, bude mít
+sled váhu~$2T$ (ka¾dou hranou kostry jsme ¹li tam a zpátky), a pøeskakování
+vrcholù celkovou váhu nezvìt¹uje (pøi pøeskoku
+nahradíme cestu $xyz$ jedinou hranou $xz$, pøièem¾ z trojúhelníkové nerovnosti
+máme $xz \leq xy + xz$), tak¾e váha nalezené
+hamiltonovské kru¾nice bude také nanejvý¹ $2T$.
+
+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ì¾¹í
+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
+algoritmy se nazývají {\I 2-aproximaèní}, kdy¾ øe¹ení je maximálnì dvojnásobné
+od~optimálního.\foot{Hezkým trikem se v obecných metrických prostorech umí
+$1{,}5$-aproximace. Ve~nìkterých metrických prostorech (tøeba v euklidovské
+rovinì) se aproximaèní pomìr dá dokonce srazit na
+libovolnì blízko k 1. Zaplatíme ale na èase -- èím pøesnìj¹í výsledek
+po algoritmu chceme, tím déle to bude trvat.}
+
+\>{\I b) bez~trojúhelníkové nerovnosti:}
+
+Zde se budeme naopak sna¾it ukázat, ¾e ¾ádný polynomiální aproximaèní
+algoritmus neexistuje.
+
+\s{Vìta:} Pokud pro~libovolné~$\varepsilon>0$ existuje polynomiální
+$(1+\varepsilon)$-aproximaèní algoritmus pro~problém obchodního cestujícího bez~trojúhelníkové nerovnosti, tak ${\rm P = NP }$.
+
+\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$, ve~kterém hledáme hamiltonovskou kru¾nici. Doplníme
+$G$ na~úplný graf~$G'$ a~váhy hran~$G'$ nastavíme takto: