Hamiltonovská kružnice
Cvičení k předmětu MA007 Matematická logika, podzim 2009 Tomáš Brázdil a Jan Krčál
Definice 1. Orientovaný graf je dvojíce G = (V, E), kde V je soubor vrcholů a E C V2 je soubor orientovaných hran mezi vrcholy.
Definice 2. Nechi G = (V, E) je orientovaný graf a n = \V\. Hamiltonovská kružnice
(HK) v orientovaném grafu G je posloupnost vrcholů vq, v i, ..., vn taková, že
1.   pro všechna 0 < i < n piati («j, vi+i) G E
2.   pro všechna 0 < i < j < n platí v^ ^ v j
3.   v0 = vn
Cvičení.   Nechi G je orientovaný graf takový, že n =  \V\  > 2. Zadejte formuli ip takovou, že platí
ip je splnitelná -<=> G obsahuje Hamiltonovskou kružnici                     (1)
a ip lze sestrojit v polynomiálním čase.
Poznámka. Naším úkolem je tedy redukovat problém Hamiltonovské kružnice na NP-úplný problém splnitelnosti výrokových formuli (SAT) v polynomiálním čase.
Protože n > 2, graf G obsahuje HK právě tehdy, když graf (V, E\ {(w, u) \ u G V}) (tedy G bez smyček) obsahuje HK.
Budeme předpokládat, že pro každé u G V platí (w, u) ^ E
(jinými slovy, že G neobsahuje smyčky). Dále budeme předpokládat, že pro každé u e V existuje alespoň jedno v G V takové, že (w, v) G E.
Klíčem k řešení je následující alternativní charakterizace HK v grafu G.
Definice 3. Řekneme, že soubor hran K G E je HK pokud splňuje následující podmínky:
A.   pro každé u G V existuje právě jedno v G V takové, že (w, v) G K (tedy každý vrchol u G V má právě jednu výstupní hranu v K).
B.   \Jl=íKl = V x V 1  (tedy pro každou dvojící vrcholů w, v G V platí, že existuje cesta "po hranách z K" z vrcholu u do vrcholu v)
Lemma 1.  G obsahuje HK právě když existuje soubor hran K C E, který je HK. ^^Pro dané soubory hran K, L C E definujeme
K ■ L := {(u, v) | =!iu G V : (u, w) G K a (w, v) G L}
Definujeme K1 = K a pro í > 1 definujeme ííl+1 := Kz ■ K. (Všimněte si, že Kz ■ K = K ■ Kz, a že (u, v) G Kz právě tehdy, když v grafu (V, K) existuje orientovaná cesta délky í z -u do v.)
1
Důkaz. Nechť vq, v\, • • • vn je HK. Nyní soubor
K = {(v0, ví), (vi, v2), ■ ■ ■, (vn-í, vn), (vn, v0)}
je zřejmě HK dle Definice 3.
Naopak, nechť K je HK. Definujme posloupnost vrcholů vq,v\, ... ,vn kde
•   vo je libovolný vrchol
•   pro každé 0 < i < n je Vi+i unikátni vrchol splňující (ví, Vj+i) G K
Ukážeme, že u> = vq, v\, ..., vn je HK. Z podmínky A. plyne, že dennice u> je korektní, protože každé vi má právě jednu výchozí hranu v K.
Zbývá dokázat podmínky 1. - 3. z Definice 2. Podmínka 1. plyne přímo z definice u> a z K C E. Podmínky 2. a 3. vyplynou snadno z následujícího tvrzení:
Pokud pro nějaká 0 < i < j < n platí v i = Vj, pak pro každé 1 < £ < n platí
{u | (ví, u) G Ke} C {ví, vi+1,..., Vj}                                      (2)
Důkaz povedeme indukcí vzhledem k i. Pokud i = 1, pak díky podmínce A.,
{u | (ví,u) G Ke} = {u | (ví,u) £ K} = {vi,vi+1} C {vi,vi+1,.. .,Vj}
Předpokládejme, že (2) platí pro £ a uvažme £+1. Nechť (vi,u) G Ke+1. Ukážeme, že m G {ví, vi+i,..., Vj}. Jelikož (vi: u) G Ke+1 = Ke ■ K, existuje w e V takové, že (ví,w) G K£ a (w,u) G if. Z indukčního předpokladu (který aplikujeme na (ví,w)) obdržíme, že w G {ví,Ví+\, ..., Vj}, tedy w = vj. pro nějaké i < k < j. Z definice u> plyne, že pokud k < j, pak u = Vk+i a pokud k = j, pak u = Vj+i. Tedy u G
{Vi,Vi+l,...,Vj}.
Nyní můžeme snadno dokázat podmínky 2. & 3. z Definice 2. Nejprve předpokládejme, že podmínka 2. není splněna, tedy že existují 0 < i < j < n taková, že ví = Vj. Potom ovšem (2) implikuje, že existuje nejvýše j — i < n vrcholů u e V takových, že (ví, u) G U"=i ^i coz Je ve sporu s podmínkou B. Nyní předpokládejme, že podmínka 3. není splněna, tedy že vn ^ vq. Z Dirichletova principu plyne, že musí existovat 0 < i < j < n taková, že Ví = Vj. Z»„^ vq plyne buď i > 0 nebo j < n. Pak ovšem z (2) plyne, že existuje nejvýše j — i < n vrcholů u e V takových, že (vi: u) G U™=i ^i což je ve sporu s podmínkou B.                                                                                            D
Díky Lemmatu 1 zřejmě stačí zkonstruovat formuli ip, která je splnitelná právě tehdy, když existuje množina K, která je HK dle Definice 2.
Nejprve musíme určit, jaké výrokové proměnné budeme ve formuli ip používat. Pro každou hranu (u, v) G E zavedeme výrokovou proměnnou Xuv. Každá valuace v nám potom bude zadávat množinu hran
K1J = {(u,v)eE\v(Xuv) = l}
Formuli <p definujeme tak, aby v(p>) = 1 právě tehdy, když Kv je HK. Potom Lemma 1 implikuje, že <p je splnitelná právě když graf G obsahuje HK. Formuli <p definujeme postupně tak, že nejprve definujeme formule, které zajistí podmínky A. a B. z Definice 2.
Podmínku A. je možné zajistit následující formulí
£:= A (   V   (X™A       A       -,*™'
uEV   \(u,v)GE   \             (u,v')eE\{(u,v)}
2
Lemma 2. Pro libovolnou valuaci v platí, že z/(£) = 1 právě tehdy, když pro každé u G V existuje právě jedno v G V takové, že (u,v) G Kv.
Důkaz. Pokud z/(£) = 1, pak pro každé u e V existuje v G V takové, že (u,v) G E, v(Xuv) = 1 a pro každé (u,v') G E \ {(u, v)} platí v(Xuvi) = 0. Potom ovšem je v jediný vrchol splňující (u, v) G Kv.
Naopak, předpokládejme, že pro každé u G V existuje právě jedno v G V takové, že (u,v) G Kv. Potom pro každé u G V musí platit, že existuje právě jedno v G V takové, že v(Xuv) = 1. Potom ovšem z/(£) = 1.                                                                 D
Abychom byli schopni zajistit podmínku B. z Definice 2, zavedeme nové výrokové proměnné tvaru Xluv kde 1 < i < n. Definujeme formuli rj tak, aby pro každou valuaci v platilo, že v[r\) = 1 právě tehdy, když pro každé 1 < i < n platí Klv = {(u,v) | v(Xluv) = 1}. Potom bude podmínka B. snadno vyjádřitelná pomocí formule 1 A A« vgv Vľ=i ^-uv (Intuice za Xluv a rj je následující: formule rj je splněna při va-luacích v, které jsou konzistentní v tom smyslu, že v(X%uv) = 1 právě tehdy, když v grafu (V, Kv) existuje cesta délky i z m do v.)
n i=í
kde formule rrf definujeme induktivně takto:
rř ■=         A     (Xuv » Xuv) A               A           ^X-
(u,v)EE                                   \(w,z)e(VxV)\E
vi+1-=    A  (xít1»   V   (XL**™)
u,v£V   y                 (w,v)£E
Lemma 3. v(rj) = 1 právě když pro každé 1 < i < n platí Kl = {(u, v) \ v{Xluv) = 1}. Zejména v[r\ A A^ev Vľ=i Xlv) = l Právě tehdy, když \J"=1 Klu = V x V.
Důkaz. Předpokládejme, že v(r)) = 1. Dokážeme, že K\, = {(u,v) \ v(X%uv) = 1} indukcí vzhledem k i. Pokud i = 1 pak přímo z v(rf) = v('qr) = 1 dostaneme
Kl=Kv = {(u,v) G E I V{XUV) = 1} = {(u, v) I v{Xluv) = 1}
Předpokládejme, že tvrzení platí pro i a uvažme i + 1. Pak
Ki+1 = KÍ-Kly                                                                             (definice Kl+Í)
= Kl ■ {{w, v)eE\ v{Xwv) = 1}                                     (definice Kv)
= {(u,w) | v(Xluw) = 1} • {(w,v) G E I v(Xwv) = 1}     (indukční předpoklad)
= {(u,v) | 3w G V^ : v(Xluw) = 1 a v(Xwv) = 1}            (definice zřetězení •)
= {(u,v)\u(XÍ+1) = l}                                                     W+1) = l)
Nyní předpokládejme, že pro každé 1 < i < n platí Klv = {(u,v) \ v(X%uv) = 1}. Ukážeme, že v(rf) = 1 pro každé 1 < i < n indukcí vzhledem k i. Předpokládejme nejprve, že i = 1. Pak
{(u,v) | u(XÍv) = \} = KÍ = Kl = Ku = {(u,v) G E \ v{Xuv) = 1}
a tedy v(rf) = 1.
3
Předpokládejme, že tvrzení platí pro i a uvažme i + í. Pak dle našeho předpokladu,
Kt+1 = {(u,v)\u(Xt+1) = l}
a zároveň
Ki+Í = KÍ-Ku                                                                (definice Klu+1)
= {(u,w) | v(Xluw)} ■ {(w,v) G E I i/(Xwv)}            (indukční předpoklad)
= {(u,v) | 3w G V : v{Xluw) = 1 a v(Xwv) = 1}      (definice zřetězení •)
Tedy
{(u,v) | uiXit1) = 1} = Kt+1 = {(u,v) \3weV: v{XÍw) = 1 a v(Xwv) = 1}
To ovšem znamená, že pro libovoné vrcholy u,veV platí
v(XÍÍ1)=vl    V    (XL**™)
\(w,v)£E
a tedy is(r]i+1) = 1.                                                                                                      D
Na závěr definujeme formuli <p takto:
^:=eAí?A   A   Vx«
uv u:vEV i=l
Lemma 2 a Lemma 3 implikují, že v(<p) = 1 právě když Kv je HK. Potom ovšem Lemma 1 implikuje, že <p je splnitelná právě když G obsahuje HK. Velikost formule <p se snadno odhadne takto:
kde
Me	Om + \v\+n3)
	lil € 0(n2)
| eO	(EkÍ)cO(n4
\i=l
Celkem |^| G 0(n4).
4