Проблем Хамилтоновог пута
У области математике, теорији графова, проблем Хамилтоновог пута и проблем Хамилтоновог циклуса су проблеми одређивања да ли постоји Хамилтонов пут или Хамилтонов циклус у датом графу (усмереном или неусмереном). Оба проблема су НП-комплетна. Проблем проналажења Хамилтоновог циклуса или пута је у класи ФНП.
Постоји проста релација између ова два проблема. Проблем Хамилтоновог пута за граф G је еквивалентан проблему Хамилтоновог циклуса за граф H који се добија из G додавањем новог чвора, и спајањем тог новог чвора са свим чворовима из G.
Проблем Хамилтоновог циклуса је специјални случај проблема трговачког путника, добијеног постављањем раздаљине између два града на коначну константу ако су суседни, а у супротном на бесконачно.
Усмерени и неусмерени проблеми Хамилтоновог циклуса су били два од 21 Карпових НП-комплетних проблема. Гери и Џонсон су убрзо затим, 1974, показали да проблем Хамилтоновог циклуса остаје НП-комплетан и за планарне графове а да неусмерени проблем Хамилтоновог циклуса остаје НП-комплетан за кубне планарне графове.
[уреди] Види још
[уреди] Спољашње везе
- Hamiltonian Page : Проблем Хамилтоновог циклуса и пута, њихове генерализације и варијације
[уреди] References
- 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, p.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 0-7167-1045-5. A1.3: GT37–39, pp.199–200.
