Rešitev: Hamiltonov cikel

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Naloga: Hamiltonov cikel

Kot že vemo, so v razredu P odločitveni problemi, ki so rešljivi v polinomskem času na determinističnem Turingovem stroju, v razredu NP pa odločitveni problemi, rešljivi v polinomskem času na nedeterminističnem Turingovem stroju.

Najprej se vprašamo, če je to problem v odločitveni obliki:

Podano: graf z n vozli
Vprašanje: Ali graf vsebuje Hamiltonov cikel?
Odgovor: Da ali Ne.

Dokazali bomo, da je ta problem v NP.

(1)Uganjevalec nam poda zaporedje točk u1,u2,...,um
(2)Preverimo:
(a)m=n
(b)ui = uj natanko tedaj, ko je i = j
(c)obstaja povezava med ui in u(i + 1)
(d)obstaja povezava med un in u1  
Točke od (a) do (d) so pogoji, ki jim graf mora ustrezati, da vsebuje Hamiltonov cikel.
Preostane nam še, da preverimo, če je to rešljivo v polinomskem času.
(a)časovna zahtevnost je O(n)
(b)časovna zahtevnost je O(n2)
(c)časovna zahtevnost je O(n2)
(d)časovna zahtevnost je n
Je rešljivo v polinomskem času. 

Ta problem je torej v NP.

Glej tudi

Osebna orodja