Zadání:
Mám graf G(V,E), černou krabičku, která řeší SAT.
Postup:
Očísluju vrcholy grafu od 1..n (abych mohl určit, které pozici budu říkat první na HK).
Pro každý vrchol definuju Xvi (proměnná X s indexy v,i), která bude mít hodnotu:
1 - pokud vrchol v leží na i-té pozici v hamiltonovské kružnici
0 - jinak
Tedy proměnných Xvi bude celkem n^2, neboť vrcholů grafu mám n a různých pozic na hamiltonovské kružnici mám také n. Speciálně pro první vrchol (označme ho p) bude platit Xp1 = 1. Pokud by mi pro graf, jehož vrcholy označím abcd řekl SAT, že Xa1 = 1, Xb3 = 1, Xc4 = 1, Xd2 = 1, pak hamiltonovskou kružnici tvoří vrcholy v pořadí adbc.
Poté sestavím formule:
1,
Pro každý vrchol do formule přidám
vrchol v se vyskytuje alespoň na jedné pozici aneb vrchol (v je na pozici 1 v HK) nebo (v je na pozici 2 v HK) nebo ...nebo (v je na pozici n v HK) neboli (Xv1 = 1) or (Xv2 = 1) or ... (Xvn = 1) neboli
Xv1 or Xv2 or Xv3 or ...
2,
Pro každou dvojici vrcholů do formule přidám (jako náhradu za tvrzení, že se vrchol vyskytuje jen na jedné pozici)
žádné dva u,v se nevyskytují na stejné pozici
aneb
[ NOT(u je na pozici 1) or NOT(v je na pozici 1) ] AND [ NOT(u je na pozici 1) or NOT(v je na pozici 2) ] AND ... AND [ NOT(u je na pozici n) or NOT(v je na pozici n) ]
aneb
[NOT(Xu1) or NOT(Xv1)] AND ... AND [NOT(un) or NOT(Xvn)]
3,
Poté pro každou 'nehranu', tj. dvojici vrcholů u,v, které nejsou spojeny hranou přidám (dělám část vrcholy u a v na poziciach i a i+1 smu byt sucasne, ak je medzi u a v hrana):
když u je na pozici 1, pak v není na pozici 2 AND když u je na pozici 2, pak v není na pozici 3 AND ..
aneb
Xu1 => NOT(Xv2) AND Xu2 => NOT(Xv3) AND ... AND Xu{n-1} => NOT(Xvn)
aneb
[ NOT(Xu1) OR NOT(Xv2) ] AND [ NOT(Xu2) OR NOT(Xv3) ] AND ... AND [ NOT(Xu{n-1}) OR NOT(Xvn) ]
Nakonec spojím formule z 1,2,3 pomocí AND, neboť chci, aby platilo všechno. Nyní bych měl ověřit, že délka vytvořené formule je polynomiální, což přenechávám za DU
Na tuto mojí formuli pustím SAT, on mi právě n proměnných Xij ohodnotí 1 (protože jsem ho vymýšlel, aby to tak musel udělat).
Doufám, že to je blbovzdorné (a dobře
)