Задача о гамильтоновом цикле (HC) состоит в том, чтобы найти цикл, который проходит через все вершины в данном неориентированном графе. Задача коммивояжера (TSP) состоит в том, чтобы найти цикл, который проходит через все вершины в данном графе, взвешенном по ребрам, и минимизирует общее расстояние, измеренное суммой весов ребер в цикле. HC является частным случаем TSP, и оба они известны как NP-полные [Garey & Johnson]. (См. Ссылки выше для более подробной информации и вариантов этих проблем.)
Существуют ли изученные классы графов, на которых задача о гамильтоновом цикле разрешима за полиномиальное время с помощью нетривиального алгоритма, но задача коммивояжера NP-трудна?
Нетривиальным является исключение таких классов, как класс полных графов, где гамильтонов цикл гарантированно существует и может быть легко найден, или вообще классы графов, где HC всегда гарантированно существует.
источник
Как насчет полных графиков ? Так как TSP всегда может быть сведен к экземпляру на полных графах (путем добавления правильных расстояний между не ребрами), все еще непросто решить TSP на полных графах. Но любые полные графы гамильтоновы.
источник
Существует много бесконечных классов графов, которые, как известно, имеют гамильтоновы схемы. Два особенно интересных класса - это n-кубы и графы Халина. Один из способов мышления для графов Халина состоит в том, чтобы встроить дерево, по крайней мере, с 3 вершинами, в котором нет вершин валентности 2 на плоскости, а затем пропустить простую схему через 1-валентные вершины дерева.
http://en.wikipedia.org/wiki/Halin_graph
Известно, что эти графики имеют HC, и на самом деле они либо панциклические (цепи любой длины), либо не имеют ровно одной длины цепи, которая должна быть четной длины.
источник