Нахождение гамильтоновых циклов в кубических плоских графиках
Я имею относительно маленький (40-80 узлов) кубические (3-регулярные) плоские графики, и я должен решить их Hamiltonicity. Я знаю о том, что эта задача полна NP, но я надеюсь на асимптотически экспоненциальные алгоритмы времени, которые, тем не менее, очень быстры для размера графика, которым я интересуюсь.
2 ответа
40 узлов кажутся выполнимыми. Вы выбираете 40 из 60 граней для включения.
Давайте попробуем поиск в глубину.
Для начала выберите вершину V. Вам нужно будет исключить ровно одно из трех инцидентных ребер. Попробуйте эти 3 возможности по очереди. Когда вы выбираете край для исключения, вы принудительно включаете 4 ребра. После этого мы будем называть вершины исключенного ребра «использованными».
Если бы вы могли повторить этот процесс 10 раз, вы бы выбрали все 40 ребер, ища только 3 ^ 10 (59049) вариантов. Конечно, у вас закончатся "изолированные" вершины после того, как будет определено достаточное количество ребер.
Но теперь у нас есть идея алгоритма. На каждом шаге старайтесь выбирать вершину с наименьшим количеством «используемых» соседей. На самом деле, лучше всего выбрать вершину с двумя использованными соседями, поскольку используемое ребро принудительно. Я не уверен, что лучше выбрать вершину с 1 или 0 использованными соседями. Попробуйте оба способа! (А 3 использованных соседа указывают на неудачный поиск)
Когда мы закончим выбор ребер, проверьте, образуют ли они единый цикл.
У вас есть несколько образцов графиков? Я мог бы попробовать простую реализацию.
from http://mathworld.wolfram.com/HamiltonianCycle.html : "Рубин (1974) описывает эффективную процедуру поиска, которая может найти некоторые или все гамильтоновы пути и цепи в графе, используя умозаключения, которые значительно сокращают обратный путь и догадки."
Статья продается здесь: http://portal.acm.org/citation.cfm?id=321850.321854