Проблем Хамилтоновог пута

У области математике, теорији графова, проблем Хамилтоновог пута и проблем Хамилтоновог циклуса су проблеми одређивања да ли постоји Хамилтонов пут или Хамилтонов циклус у датом графу (усмереном или неусмереном). Оба проблема су НП-комплетна. Проблем проналажења Хамилтоновог циклуса или пута је у класи ФНП.

Постоји проста релација између ова два проблема. Проблем Хамилтоновог пута за граф 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.
• 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.