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