Problem Hamiltonovog puta

U oblasti matematike, teoriji grafova, problem Hamiltonovog puta i problem Hamiltonovog ciklusa su problemi određivanja da li postoji Hamiltonov put ili Hamiltonov ciklus u datom grafu (usmerenom ili neusmerenom). Oba problema su NP-kompletna. Problem pronalaženja Hamiltonovog ciklusa ili puta je u klasi FNP.

Postoji prosta relacija između ova dva problema. Problem Hamiltonovog puta za graf G je ekvivalentan problemu Hamiltonovog ciklusa za graf H koji se dobija iz G dodavanjem novog čvora, i spajanjem tog novog čvora sa svim čvorovima iz G.

Problem Hamiltonovog ciklusa je specijalni slučaj problema trgovačkog putnika, dobijenog postavljanjem razdaljine između dva grada na konačnu konstantu ako su susedni, a u suprotnom na beskonačno.

Usmereni i neusmereni problemi Hamiltonovog ciklusa su bili dva od 21 Karpovih NP-kompletnih problema. Geri i Džonson su ubrzo zatim, 1974, pokazali da problem Hamiltonovog ciklusa ostaje NP-kompletan i za planarne grafove a da neusmereni problem Hamiltonovog ciklusa ostaje NP-kompletan za kubne planarne grafove.

Vidi još

• Problem trgovačkog putnika

Spoljašnje veze

• Hamiltonian Page : Problem Hamiltonovog ciklusa i puta, njihove generalizacije i varijacije

Literatura

• Rubin, Frank, "A Search Procedure for Hamilton Paths and Circuits'". Journal of the ACM, Volume 21, Issue 4. October 1974. ISSN 0004-5411
• M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete problems. Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 47-63. 1974.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5.  A1.3: GT37-39, pp. 199-200.