несколько определений:Проверка, если цикл Гамильтон существует в плотном графике первого
Определение 1
Граф G = (V, E) называется `` плотным «», если для каждой пары несмежных вершин u и v, d (u) + d (v)> = n где n = | V | и г (*) обозначает степень вершины *
Определение 2
Символ 'гамильтонов цикл '' на G представляет собой последовательность вершин (vi1, vi2, .... Vin , vi1) таким образом, что Виль = VIH для всех л = Н и {Виль, Виль} является ребром G.
проблема заключается в том:! написать программу, которая, учитывая плотный неориентированный граф G = (V; E), определяет, допускает ли G гамильтонов цикл на G и выводит этот цикл, если он есть, или выводит `` N '', если его нет.
Мое решение состоит в том, чтобы найти все возможные пути, начинающиеся с источника, и проверить, существует ли путь к этому источнику. К сожалению, это решение неэффективно.
любые предложения? Спасибо.
[This] (http://stackoverflow.com/questions/1387725/what-is-dynamic-programming-algorithm-for-finding-a-hamiltonian-cycle?rq=1) использует динамическое программирование для выполнения задания , – denahiro
Хотя вышеупомянутое сообщение упоминает об этом, я также упомянул об этом, чтобы сохранить некоторое время поиска - существует алгоритм, но это не полиномиальное время. Вариант решения гамильтонова цикла - NP-Hard. Вы не найдете «эффективного» решения - ну, если это так, то сообщество компьютерных наук с удовольствием это услышит. :) – adelbertc
Согласно теореме Оре (http://en.wikipedia.org/wiki/Ore%27s_theorem), графики, удовлетворяющие определению 1, всегда имеют гамильтонов цикл. –