Как найти число гамильтоновых циклов, в которых не используются «запрещенные» ребра?

Question

Этот вопрос фактически перефразирует этот один .Проблема кодового застревания заключается в следующем:

Вам дан полный ненаправленный граф с N узлами и K"запрещенными" ребрами. N <= 300, <strong>K <= 15. Найдите число гамильтоновых циклов в графе, которые не используют ни одного из <strong>K «запрещенных» ребер.

Простой подход DP O(2^N*N^2) не работает для таких N .Похоже, что выигрышные решения равны O(2^K).Кто-нибудь знает, как решить эту проблему?

Answer 1

Давайте выясним для каждого подмножества S запрещенных ребер, сколько существует гамильтоновых циклов, которые используют все ребра S. Если мы решим эту подзадачу, то мы решим задачу по формуле включения-исключения .

Теперь, как мы решаем подзадачу?Давайте нарисуем все ребра S. Если существует вершина степени больше 2, то, очевидно, мы не можем завершить цикл, и ответ равен 0. В противном случае граф делится на связанные компоненты.Каждый компонент является единственной вершиной, циклом или простым путем.

Если существует цикл, то он должен проходить через все вершины, иначе мы не сможем завершить гамильтонов цикл.Если это так, ответ равен 2. (Цикл может быть пройден в 2 направлениях.) В противном случае ответ равен 0.

Остается случай, когда есть c путей и k единственные вершины.Чтобы завершить гамильтонов цикл, мы должны выбрать направление каждого пути ( 2 ^ c путей), а затем выбрать порядок компонентов.У нас есть c + k компонентов, поэтому их можно переставить (c + k)! способами.Но нас интересуют циклы, поэтому мы не различаем упорядочения, которые превращаются друг в друга циклическими сдвигами.(Таким образом, (1,2,3), (2,3,1) и (3,1,2) одинаковы.) Это означает, что мы должны разделить ответ на количество смен, c + k.Таким образом, ответ (на подзадачу): 2 ^ c (c + k-1)! .

Эта идея реализована в решении bmerry (очень чистый код, кстати).

Answer 2

Задача о гамильтоновом цикле является частным случаем задачи коммивояжера (полученной путем задания расстояния между двумя городами конечной постоянной, если они смежны, и бесконечности в противном случае.)

Это задачи NP Complete, которые в простомслова означают, что быстрое решение для них не известно.

Тривиальный эвристический алгоритм для определения местоположения гамильтоновых путей состоит в том, чтобы построить путь abc ... и расширить его до тех пор, пока он больше не станет невозможным;когда путь abc ... xyz больше не может быть расширен, поскольку все соседи z уже лежат на пути, каждый возвращается на один шаг назад, удаляя ребро yz и расширяя путь другим соседом y;если никакой выбор не приводит к гамильтонову пути, тогда делается следующий шаг назад, удаляя ребро xy и расширяя путь другим соседом x, и так далее.Этот алгоритм, безусловно, найдет гамильтонов путь (если он есть), но он работает за экспоненциальное время.

Для получения дополнительной информации см. NP Завершите главу проблемы "Введение в алгоритмы" Кормена