У области математике, теорији графова, проблем Хамилтоновог пута и проблем Хамилтоновог циклуса су проблеми одређивања да ли постоји Хамилтонов пут или Хамилтонов циклус у датом графу (усмереном или неусмереном). Оба проблема су НП-комплетна. Проблем проналажења Хамилтоновог циклуса или пута је у класи ФНП.
Постоји проста релација између ова два проблема. Проблем Хамилтоновог пута за граф -{G}- је еквивалентан проблему Хамилтоновог циклуса за граф -{H}- који се добија из -{G}- додавањем новог чвора, и спајањем тог новог чвора са свим чворовима из -{G}-.
Проблем Хамилтоновог циклуса је специјални случај проблема трговачког путника, добијеног постављањем раздаљине између два града на коначну константу ако су суседни, а у супротном на бесконачно.
Усмерени и неусмерени проблеми Хамилтоновог циклуса су били два од 21 Карпових НП-комплетних проблема. Гери и Џонсон су убрзо затим, 1974, показали да проблем Хамилтоновог циклуса остаје НП-комплетан и за планарне графове а да неусмерени проблем Хамилтоновог циклуса остаје НП-комплетан за кубне планарне графове.
Види још Проблем трговачког путника
Спољашње везе -{Hamiltonian Page}- : Проблем Хамилтоновог циклуса и пута, њихове генерализације и варијације
Литература
-{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.}- -{ A1.3: GT37-39, pp. 199-200.}-
Категорија:Теорија графова Категорија:НП-комплетни проблеми Категорија:Рачунарски проблеми у теорији графова
es:Problema del ciclo hamiltoniano