Гамильтонов путь в графе

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

В качестве примера рассмотрим задачу определения очередности решения на ЭВМ вычислительной программы (алгоритма) А,состоящей из п подпрограмм A_i ; i=1,2,…,n , причем на порядок выполнения подпрограмм накладываются ограничения в виде

т.е. выполнение подпрограммы A_i предшествует выполнению подпрограммы A_j , i, j Î <1,2,…,n> или

A_i A_j , (4.2)

т.е. порядок выполнения программ A_i и A_j безразличен.

Эту задачу удобно геометрически отобразить в виде графа, где каждой i вершине соответствует A_i – подпрограмма, а связи между подпрограммами соответствуют дугам или ребрам. Причем дуга соответствует связи A_i → A_j , а ребро – связи A_i A_j .

Если предполагается, что программа A будет выполнена, когда выполнены все подпрограммы A_i , i=1,2,…,n (без повторений), то определение очередности выполнения подпрограмм A_iсводится к определению на графе гамильтонова пути. Очевидно, что эту задачу можно решить перебором всех возможных вариантов (n! в насыщенном графе) с одновременной проверкой выполнения всех условий (4.1), (4.2). При n = 2 максимально возможно всего два варианта, при n = 3 – шесть, при n=10 существует более трех с половиной миллионов возможных вариантов, из которых надо выбрать допустимые, удовлетворяющие условиям (4.1), (4.2).

Решение поставленной задачи может быть облегчено, если воспользоваться алгоритмом Фаулкса, позволяющим во многих случаях значительно уменьшить количество рассматриваемых возможных вариантов [1].

Алгоритм Фаулкса. Рассматривается n операций (вершины графа) A_1, A_2,…, A_n , между которыми существуют соотношения:

Задача состоит в том, что среди всех возможных путей найти, если это возможно, путь (или несколько путей), проходящий один и только один раз через каждую извершин графа и удовлетворяющий написанным выше соотношениям (4.3), то есть гамильтонов путь.

Идея вычислений, которые необходимо выполнить при использовании алгоритма Фаулкса, заключается в нахождении матрицы R N путем последовательногобулевого умножения матрицы R 1 достижимости не более чем за один шаг саму на себяN раз (матрица R 1 может быть получена из матрицы смежности R в результате подстановки единиц на главной диагонали).

Элементы r N _ij матрицыR N , определяются как

Вычисления следует прекратить, если R N = R N -1 .

На каждом цикле вычисления возможны некоторые упрощения матрицы, связанные с выявлением «начальных» и «конечных» вершин, ограничивающих возможность дальнейшего построения ГП из общего множества возможных путей в графе.

Порядок решения задачи:

1. Задаем номер цикла вычислений N=1.

2. Используя соотношения (4.3), составляем граф, вершины которого есть операции, а направленные дуги графа определяются заданными соотношениями между операциями.

3. Составляем матрицу R 1 графа, элементы r 1 _ij которой могут принимать значения 0 либо 1. Если r 1 _ij = 1, то это указывает на то, что операция (вершина) A_j должна следовать за операцией (вершиной) A_i . Полученная таким образом матрица R 1 является булевой матрицей (каждый элемент может принимать значения 0 или 1). Она является исходной для всех дальнейших вычислений.

4. Используя матрицу R N (на первом цикле вычислений R N = R 1 ), длякаждой вершины графа (операции) проверяем принадлежность ее кначальной или конечной вершине ГП по следующим правилам.

Вершина (операция) является начальной вершиной ГП, если во всей строке матрицы стоят единицы, а во всем столбце (за исключением их пересечения) – нули. Вершина (операция) является конечной вершиной ГП, то во всей строке матрицы стоят нули (за исключением их пересечения), а во всем столбце – единицы.

5. Упрощаем матрицу R N графа, вычеркивая из нее строки и столбцы, соответствующие начальной или (и) конечной вершине ГП. Получаем матрицу (R N ) ‘ .

6. Увеличиваем на единицу номер цикла, т.е. N=N+1.

7. Находим матрицу (R N ) ‘ , выполнив булевое умножение матрицы (R N -1 ) ‘ на матрицу (R 1 ) ‘ , которая получается из исходной матрицы R 1 вычеркиванием из нее строк и столбцов, соответствующих начальным и конечным вершинам ГП, найденным во всех предыдущих циклах вычислений. Булевое перемножение матриц производится по обычным правилам умножения, только вместо умножения используется конъюнкция, а вместо сложения – дизъюнкция.

8. Проверяем условие выполнения равенства матриц (R N ) ‘ и (R N -1 ) ‘ .

Если это условие выполняется, то переходим к п. 10, Иначе – к п. 9.

9. Проверяем условие равенства всех элементов матрицы R N единице. Если это условие выполняется, то нет необходимости в дальнейших вычислениях матрицы (R N ) ‘ , так как очевидно, что (R N +1 ) ‘ =(R N ) ‘ , переходим к п. 10. Если нет – к п. 4.

10. Составляем матрицу R b , возвращая в матрицу (R N ) ‘ , строки и столбцы, вычеркнутые в п. 5 во всех циклах вычислений.

11. Составляем матрицу R c , перегруппировывая одновременно строки и столбцы матрицы R b таким образом, чтобы все нули были расположены под главной диагональю, а единицы – над ней.

Квадратные матрицы, состоящие из единиц, опирающихся на главную диагональ, образуют классы эквивалентности вершин (совокупности вершин графа, эквивалентных с точки зрения очередности их присутствия в гамильтоновом пути).

Если для данного графа мы получилиm классов эквивалентности (m £ n), то есть B₁,…,B_m , и в каждый класс эквивалентности B_d , d = 1,2,…,m входят S_d вершин графа, то можно сказать, что вершины, входящие в класс эквивалентности B_d, расположенные выше и левее класса эквивалентности B_l в матрице R c будут предшествовать в Гамильтоновом пути вершинам из класса эквивалентности B_l .

Нахождение Гамильтоновых путей в этом случае значительно упрощается. В соответствии с классами эквивалентности мы получили упорядоченные группы вершин. В качестве начальной выбирается вершина из первого класса эквивалентности. Если их в нем несколько, то следующая выбирается из этого же класса и так до тех пор, пока не будут исчерпаны все вершины этого класса. Затем переходим к вершинам следующего класса и т.д. пока не будут использованы все вершины графа и построен ГП. Следует заметить, что при выборе очередной вершины необходимо обязательно проверять выполнение условий (4.3). Если условия не выполняются, очередность следования вершин из одного класса эквивалентности меняется. Максимальное число возможных вариантов сокращается до произведения B₁ ! ∙ B₂ ! ∙ ,…, ∙ B_m !

Пример. Пусть программа A состоит из 6 операций (подпрограмм) A_1, A_2,…, A₆ , между которыми существуют следующие соотношения:

Цель задачи состоит в нахождении пути, проходящего только один раз через все операции (вершины графа) и удовлетворяющего написанным соотношениям. Без учета ограничений (4.4) всего возможно 6! = 720 вариантов следования вершин.

Для решения задачи воспользуемся приведенным алгоритмом.

1. Зададим номер цикла N = 1.

2. Составим граф (рис. 4.1), соответствующий соотношениям (4.4).

3. Составим матрицу R 1 достижимости не более чем за один шаг.

4. Проверим матрицу R 1 на наличие начальной или конечной вершин в графе.

Очевидно, что A₄ есть конечная вершина каждого гамильтонова пути, поскольку никакая дуга не имеет эту вершину своим началом, тогда как дуга, исходящая из любой другой вершины, достигает вершину A_4. Это свойство выражается наличием единиц во всем столбце A₄ и нулей во всей строке A₄ (за исключением их пересечения).

5. Вычеркиваем столбец и строку A₄. Получаем матрицу (R 1 ) ‘ .

7. Произведем булевое умножение матриц ) (R 1 ) ‘ Ä (R 1 ) ‘ = (R 2 ) ‘ .

Наличие 1 в матрице означает существование между соответствующими вершинами путей длиной меньшей или равной двум, а 0 – их отсутствие.

8. Проверяем условие равенства (R 2 ) ‘ и (R 1 ) ‘ . Так как они не равны, переходим к п. 9.

9. Проверяем условие равенства всех элементов матрицы единице. Так как оно не выполняется, то возвращаемся к п.4.

4. Рассмотрим матрицу (R 2 ) ‘ .

Вершина A₃ , является конечной вершиной гамильтонова пути на данном цикле вычислений.

5. Вычеркиваем столбец и строку A₃. Оставшаяся матрица имеет вид

(R 2 ) ‘ = .

7. Производим умножение (R 2 ) ‘ Ä (R ‘ ) = (R 3 ) ‘ .

(R 3 ) ‘ = .

9. Все элементы (R N ) ‘ , равны единице. Очевидно, что матрицы (R 4 ) ‘ , (R 5 ) ‘ и т.д. также будут равны, т.к. будут иметь все элементы, равные единице.

Переходим к п.10.

10. Матрицу R b получаем возвращением строк и столбцов, вычеркнутых в п. 5.

11. Перегруппируем строки и столбцы матрицы R b так, чтобы все нули были расположены под главной диагональю, а единицы – над ней: Получаем матрицу R c

Таким образом, получили три класса эквивалентности:,

Т.е. в гамильтоновом пути вершины A₁, A₂, A₅, A₆ предшествуют вершине A₃ , которая, в свою очередь, предшествует вершине A₄ . Всего возможно 4! ∙ 1! ∙ 1! = 24 вариантов следования вершин.

С учетом необходимости выполнения условий (4.4) определение гамильтонова пути становится достаточно простым делом. В данном примере получим единственный ГП: A₁,A₆,A₅,A₂,A₃,A₄ .

Алгоритм Фаулкса в общем случае не решает однозначно задачу определения Гамильтонова пути, он только частично упорядочивает множество вершин, снижая тем самым размерность решаемой задачи. В случае, когда в каждый класс эквивалентности входит только одна вершина, алгоритм Фаулкса определяет гамильтонов путь однозначно.

Дата добавления: 2017-01-13 ; Просмотров: 503 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Гамильто́нов граф — математический объект теории графов. Представляет собой граф (набор точек и соединяющих их линий), который содержит гамильтонов цикл [1] . При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу [2] .

Также с гамильтоновым графом тесно связано понятие гамильтонова пути, который является простым путём (путём без петель), проходящим через каждую вершину графа ровно один раз [1] . Гамильтонов путь отличается от цикла тем, что у пути начальные и конечные точки могут не совпадать, в отличие от цикла. Гамильтонов цикл является гамильтоновым путём.

Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру. В этой задаче вершины додекаэдра символизировали известные города, такие как Брюссель, Амстердам, Эдинбург, Пекин, Прага, Дели, Франкфурт и др., а рёбра — соединяющие их дороги. Путешествующий должен пройти «вокруг света», найдя путь, который проходит через все вершины ровно один раз [3] . Чтобы сделать задачу более интересной, порядок прохождения городов устанавливался заранее. А чтобы было легче запомнить, какие города уже соединены, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой верёвкой, которая могла обматываться вокруг гвоздя. Однако такая конструкция оказалась слишком громоздкой, и Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на рёбрах додекаэдра [4] .

Содержание

Условия существования [ править | править код ]

Необходимое условие существования гамильтонова цикла в неориентированном графе: если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины x ( i ) <displaystyle x(i)> с локальной степенью p ( x ( i ) ) 2 <displaystyle p(x(i)) . Доказательство следует из определения.

Условие Поша: Пусть граф G имеет 2>"> p > 2 <displaystyle p>2> 2"/> вершин. Если для всякого n <displaystyle n> , 0 n ( p − 1 ) / 2 <displaystyle 0 , число вершин со степенями меньшими или равными n меньше, чем n, и для нечетного p <displaystyle p> число вершин со степенью ( p − 1 ) / 2 <displaystyle (p-1)/2> не превосходит ( p − 1 ) / 2 <displaystyle (p-1)/2> , то G — гамильтонов граф. Это достаточное условие не является необходимым [5] .

Как следствие теоремы Поша, получаем более простые и менее сильные достаточные условия, найденные Дираком и Оре.

В 1952 году было сформулировано условие Дирака существования гамильтонова пути: пусть p <displaystyle p> — число вершин в данном графе и 3>"> p > 3 <displaystyle p>3> 3"/> ; если степень каждой вершины не меньше, чем p 2 <displaystyle <frac

<2>>> , то данный граф — гамильтонов [6] .

Условие Оре: пусть p <displaystyle p> — количество вершин в данном графе и 2>"> p > 2 <displaystyle p>2> 2"/> . Если для любой пары несмежных вершин ( x , y ) <displaystyle (x,y)> выполнено неравенство deg ⁡ x + deg ⁡ y ⩾ p <displaystyle deg x+deg ygeqslant p> , то данный граф — гамильтонов (другими словами: сумма степеней любых двух несмежных вершин не меньше общего числа вершин в графе) [6] .

Теорема Бонди [en] — Хватала [en] обобщает утверждения Дирака и Оре. Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф. Для графа G с n вершинами замыкание строится добавлением в G ребра (u,v) для каждой пары несмежных вершин u и v, сумма степеней которых не меньше n [7]

Алгоритм поиска гамильтонова пути [ править | править код ]

Эвристические оптимизации [ править | править код ]

При прямом переборе вариантов вершин возможно значительное увеличение средней сложности поиска гамильтонова пути на случайных графах (если гарантируется наличие гамильтонова пути в графе). Для улучшения данного способа можно на каждом шаге перебора при некоторой построенной части цепи проверять, образуют ли оставшиеся вершины связный граф (если не образуют, то цепь не может являться началом гамильтоновой цепи); на каждом шаге перебора при выборе следующей вершины пробовать сначала вершины с наименьшей остаточной степенью (количеством рёбер, ведущих в ещё не посещённые вершины). Кроме того, если это дерево является цепью, то гамильтонов цикл в нём возможен. Иначе (если в дереве есть вершины со степенью не меньше, чем 3) построение гамильтонова цикла невозможно [8] .

Примеры использования [ править | править код ]

Криптография [ править | править код ]

Гамильтонов цикл используется в системе так называемых протоколов с нулевым разглашением.

Пусть Пегги и Виктор знают один и тот же гамильтонов граф G, причем Пегги знает в нём гамильтонов цикл. Она хочет доказать это Виктору, не раскрывая ему самого цикла. Существует алгоритм того, как он должен действовать [9] :

1. Пегги случайным образом преобразовывает граф G. Передвигая точки и изменяя их метки, он создает новый граф H, топологически изоморфный G. Тогда, зная гамильтонов цикл в G, она легко найдет его в H. Если он не сам создает H, то определение изоморфизма между графами является слишком сложной задачей, решение которой требует огромного количества времени. Затем она шифрует H и получает граф H / .

2. Пегги передает Виктору H / .

3. Виктор просит Пегги либо:

1. Доказать, что H / – зашифрованная изоморфная копия G, либо
2. Показать гамильтонов цикл для H.

4. Пегги выполняет его просьбу. Она либо:

1. Доказывает, что H / – зашифрованная изоморфная копия G, раскрывая преобразования и все расшифровывая, не показывая гамильтонов цикл для G или H, либо
2. Показывает гамильтонов цикл для H, расшифровывая только то, что образует гамильтонов цикл, не доказывая, что H и G топологически изоморфны.

5. Пегги и Виктор повторяют этапы 1 — 4 n раз.

Если Пегги не обманывает, то она сможет рассказать Виктору одно из доказательств на этапе 3. Однако, если гамильтонов цикл для G ему самому неизвестен, он не сможет создать H / , удовлетворяющий обоим доказательствам. Правда, Пегги может создать или граф изоморфный G, или граф с таким же числом вершин и ребер и правильным гамильтоновым циклом. И, хотя с вероятностью 50 % она может угадать, какое доказательство попросит Виктор на этапе 3, Виктор может повторить протокол достаточное число раз, пока не убедится, что Пегги знает гамильтонов цикл в G.

Экстремальные задачи теории графов: Задача коммивояжёра [ править | править код ]

Коммивояжёру необходимо посетить каждый город в пределах некоторой территории и возвратиться в пункт отправления. Требуется, чтобы путь был как можно короче. Таким образом, исходная задача преобразуется в задачу поиска минимальной протяженности (длительности или стоимости) [10] .

Задачу можно переформировать в терминах теории графов — построить такой граф G(X, A), вершины которого соответствуют городам, а ребра — коммуникации между городами. Решение этой задачи ищут среди гамильтоновых циклов построенного графа.

Известно много способов решения этой задачи. Можно выделить методы, разработанные Беллмором и Немхаузером [11] , Гарфинкелем и Немхаузером [12] , Хелдом и Карпом [13] , Стекханом [14] . Также известными решениями задачи коммивояжёра являются метод ветвей и границ и метод последовательного улучшения решения [15] .

Связанные термины [ править | править код ]

Полугамильтоновым [16] графом называется граф, содержащий простую цепь, проходящую через каждую его вершину ровно один раз. При этом, всякий гамильтонов граф является полугамильтоновым. Гамильтонов цикл является простым остовным циклом [17] .

Суть задачи о гамильтоновом цикле — выяснить, имеет ли заданный граф G гамильтонов цикл. Данная задача является NP-полной [18] .

Гамильтонова орцепь орграфа [19] — простая цепь, проходящая через каждую вершину орграфа ровно один раз.

Гамильтоновым орциклом [19] называется орцикл [19] орграфа, который проходит через каждую его вершину.

Орграф называется полугамильтоновым [19] , если он имеет гамильтонову орцепь, и гамильтоновым [19] , если обладает гамильтоновым орциклом.

Содержание

Основные определения [ править ]

Определение:

Гамильтоновым путём (англ. Hamiltonian path) называется простой путь, проходящий через каждую вершину графа ровно один раз.

Определение:

Гамильтоновым циклом (англ. Hamiltonian cycle) называют замкнутый гамильтонов путь.

Определение:

Граф называется полугамильтоновым (англ. Semihamiltonian graph), если он содержит гамильтонов путь.

Определение:

Граф называется гамильтоновым (англ. Hamiltonian graph), если он содержит гамильтонов цикл.

Очевидно, что любой гамильтонов граф также и полугамильтонов.

Достаточные условия гамильтоновости графа [ править ]

Теорема Дирака [ править ]

Теорема Оре [ править ]

Теорема:

Теорема Поша [ править ]

Теорема:

Теорема Редеи-Камиона [ править ]

Теорема (Поша):

Теорема Гуйя-Ури [ править ]

Теорема:

Теорема Хватала [ править ]

Теорема (Ghouila-Houri):

Тогда если [math] forall k in mathbb N [/math] верна импликация:

[math] d_k leqslant k lt n/2 Rightarrow d_ geqslant n – k, (*) [/math] то граф [math] G [/math] гамильтонов.

Задача о коммивояжере [ править ]

Рассмотрим алгоритм нахождения гамильтонова цикла на примере задачи о коммивояжёре.

Описание задачи [ править ]

Теорема (Хватал):

Задача:

Задача о коммивояжере (англ. Travelling salesman problem, TSP) — задача, в которой коммивояжер должен посетить [math] N [/math] городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?

Варианты решения [ править ]

Задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения с экспоненциальным временем работы.

Перебор перестановок [ править ]

Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все [math] N! [/math] всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших [math]N[/math] . Сложность алгоритма [math]O( imes)[/math] .

Динамическое программирование по подмножествам (по маскам) [ править ]

Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе. Зафиксируем начальную вершину [math]s[/math] и будем искать гамильтонов цикл наименьшей стоимости — путь от [math]s[/math] до [math]s[/math] , проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор [math]s[/math] не имеет значения. Поэтому будем считать [math]s = 0 [/math] .

Подмножества вершин будем кодировать битовыми векторами, обозначим [math]mask_i[/math] значение [math]i[/math] -ого бита в векторе [math]mask[/math] .

Обозначим [math]d[i][mask][/math] как наименьшую стоимость пути из вершины [math]i[/math] в вершину [math]0[/math] , проходящую (не считая вершины [math]i[/math] ) единожды по всем тем и только тем вершинам [math]j[/math] , для которых [math]mask_j = 1[/math] (т.е. [math]d[i][mask][/math] уже найденный оптимальный путь от [math]i[/math] -ой вершины до [math]0[/math] -ой, проходящий через те вершины, где [math]mask_j=1[/math] . Если [math]mask_j=0[/math] ,то эти вершины еще не посещены).

Алгоритм поиска цикла будет выглядеть следующим образом:

• Начальное состояние — когда находимся в [math]0[/math] -й вершине, ни одна вершина не посещена, а пройденный путь равен [math]0[/math] (т.е. [math]i = 0[/math] и [math]mask = 0[/math] ).
• Для остальных состояний ( [math]i
  e 0[/math] или [math]mask
  e 0[/math] ) перебираем все возможные переходы в [math]i[/math] -ую вершину из любой посещенной ранее и выбираем минимальный результат.
• Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как [math]infty[/math] ).

Стоимостью минимального гамильтонова цикла в исходном графе будет значение [math] d[0][2^n-1][/math] — стоимость пути из [math]0[/math] -й вершины в [math]0[/math] -ю, при необходимости посетить все вершины. Данное решение требует [math]O(<2^n> imes)[/math] памяти и [math]O(<2^n> imes)[/math] времени.

Для того, чтобы восстановить сам путь, воспользуемся соотношением [math] d[i][mask] = w(i, j) + d[j][mask – 2^j] [/math] , которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния [math] i = 0 [/math] , [math] mask = 2^n – 1[/math] , найдем вершину [math]j[/math] , для которой выполняется указанное соотношение, добавим [math]j[/math] в ответ, пересчитаем текущее состояние как [math]i = j[/math] , [math] mask = mask – 2^j [/math] . Процесс заканчивается в состоянии [math]i = 0[/math] , [math] mask = 0 [/math] .

Оптимизация решения методом динамического программирования [ править ]

Пусть [math]d[mask][i][/math] содержит булево значение — существует ли в подмножестве [math]mask[/math] гамильтонов путь, заканчивающийся в вершине [math]i[/math] .

Сама динамика будет такая:
[math] d[mask][i] = left<egin 1&; |mask| = 1, mask_i = 1\ igvee_limits d[mask oplus 2^i][j] &; |mask| gt 1, mask_i= 1 \ 0&; otherwise\ end
ight. [/math]

Это решение требует [math]O(2^nn)[/math] памяти и [math]O(2^nn^2)[/math] времени. Эту оценку можно улучшить, если изменить динамику следующим образом.

Пусть теперь [math]d'[mask][/math] хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве [math]mask[/math] , заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: [math]d'[mask][/math] будет равно [math]sum_limits d[mask][i] cdot 2 ^i [/math] . Для графа [math]G[/math] выпишем [math]n[/math] масок [math]M_i[/math] , для каждой вершины задающие множество вершин, которые связаны ребром с данной вершиной. То есть [math]M_i = sum_limits 2^j cdot ((i, j) in E ? 1:0) [/math] .

Тогда динамика перепишется следующим образом:
[math] d'[mask] = left<egin mask &; |mask| = 1 \ sum_limits 2^i cdot ((d[mask oplus 2^i] & M_i)
eq 0?1:0) &; |mask| gt 1 \ 0&; otherwise\ end
ight. [/math]

Особое внимание следует уделить выражению [math]d[mask oplus 2^i] & M_i[/math] . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве [math]mask[/math] без вершины [math]i[/math] , а вторая — подмножество вершин, связанных с [math]i[/math] ребром. Если эти множества пересекаются хотя бы по одной вершине (их [math]&[/math] не равен [math]0[/math] ), то, как нетрудно понять, в [math]mask[/math] существует гамильтонов путь, заканчивающийся в вершине [math]i[/math] .

Окончательная проверка состоит в сравнении [math]d[2^n – 1][/math] c [math]0[/math] .

Это решение использует [math]O(2^n)[/math] памяти и имеет асимптотику [math]O(2^nn)[/math] .

Псевдокод [ править ]

Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за [math]|mask|[/math] количество единиц в маске (иначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния [math]langle i, mask
angle[/math] мы смотрим на состояния

[math]langle j, mask – 2^j
angle[/math] , и [math]|mask| = |mask – 2^j| + 1[/math] , то состояния с большим [math]|mask|[/math] должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта. Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти).

Дальше ищем сам цикл:

Алгоритм нахождения гамильтонова цикла [ править ]

Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла. В массиве [math]d[i][mask][/math] мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает [math] true[/math] , то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.

Алгоритм нахождения гамильтонова пути [ править ]

Алгоритм нахождения гамильтонова пути легко получить, используя алгоритм нахождения гамильтонова цикла. Нужно добавить в граф еще одну вершину и ребра от нее до всех остальных вершин и из всех остальных вершин до неё. И далее запустить алгоритм поиска цикла от новой вершины. В восстановлении пути учтем, что эта вершина лишняя, и не будем записывать её в путь.