Как найти гамильтонов путь в графе

Основные определения

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

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

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

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

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

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

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

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

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

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

Теорема Дирака

Теорема:

Если и для любой вершины неориентированного графа , то — гамильтонов граф.

Теорема Оре

Теорема:

Если и для любых двух различных несмежных вершин и неориентированного графа , то — гамильтонов граф.

Теорема Поша

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

Пусть граф имеет вершин и выполнены следующие два условия: для всякого , число вершин со степенями, не превосходящими , меньше чем ; для нечетного число вершин степени не превосходит , тогда — гамильтонов граф.

Теорема Редеи-Камиона

Теорема:

Любой сильносвязный турнир — гамильтонов.

Теорема Гуйя-Ури

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

Пусть — сильносвязный ориентированный граф. — гамильтонов.

Теорема Хватала

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

Пусть: — связный граф, — количество вершин, — его последовательность степеней. Тогда если верна импликация: то граф гамильтонов.

Задача о коммивояжере

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

Описание задачи

Задача:

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

Варианты решения

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

Перебор перестановок

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

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

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

Подмножества вершин будем кодировать битовыми векторами, обозначим значение -ого бита в векторе .

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

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

• Начальное состояние — когда находимся в -й вершине, ни одна вершина не посещена, а пройденный путь равен (т.е. и ).
• Для остальных состояний ( или ) перебираем все возможные переходы в -ую вершину из любой посещенной ранее и выбираем минимальный результат.
• Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как ).

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

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

Поиск любого гамильтонова пути методом динамического программирования

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

Сама динамика будет такая:

Это решение требует памяти и времени. Эту оценку можно улучшить, если изменить динамику следующим образом.

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

Тогда динамика перепишется следующим образом:

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

Окончательная проверка состоит в сравнении c .

Это решение использует памяти и имеет асимптотику .

Псевдокод

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

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

 // все переменные используются из описания алгоритма,  = бесконечность
 function findCheapest(i, mask):
   if d[i][mask] !=  
     return d[i][mask] 
   for j = 0 .. n - 1
     if w(i, j) существует and j-ый бит mask == 1  
       d[i][mask] = min(d[i][mask], findCheapest(j, mask - ) + w(i, j))
 return d[i][mask]
 
 function start():
   for i = 0 .. n - 1
     for mask = 0 ..  - 1
      d[i][mask] = 
   d[0][0] = 0
   ans = findCheapest(0,  - 1)
   return ans

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

 function findWay():
   i = 0
   mask =  - 1
   path.push(0)
   while mask != 0
     for j = 0 .. n - 1
       if w(i, j) существует and j-ый бит mask == 1 and d[i][mask] == d[j][mask - ] + w(i, j) 
         path.push(j)
         i = j
         mask = mask - 
         continue

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

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

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

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

См. также

• Кратчайший путь в ациклическом графе
• Задача о наибольшей общей подпоследовательности
• Задача о наибольшей возрастающей подпоследовательности
• Задача о рюкзаке
• Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре

Источники информации

• Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом «ЛИБРОКОМ», 2009. — 60 с.
• Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.
• Гамильтонов граф
• Задача коммивояжера в русской википедии
• Задача коммивояжера в немецкой википедии
• Романовский И. В. Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом «Вильямс», 2005. ISBN 5-8459-0857-4

1. Введение

В данной статье представлен вариант применения квантового алгоритма Гровера для решения задачи поиска гамильтоновых циклов в графе.

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

2. Постановка задачи

Представим, что существует граф, состоящий из пяти вершин O, A, B, C, D, и восьми ребер. Вершину O мы будем считать исходной точкой.

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

Решение этой задачи легко найти самостоятельно. Всего существуют 4 варианта такого пути, при том, что два из них являются обратными последовательностями двух других:

• OCADBO и OBDACO

• ODACBO и OBCADO

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

Маршрутом мы будем называть последовательность вершин, через которые должен пройти путник, например: OBCADO. Каким бы ни был маршрут (последовательность вершин), он должна удовлетворять следующим правилам:

• вершины маршрута должны быть уникальны, путник дважды не заходит в один и тот же пункт;

• переход на любом шаге маршрута возможен только в ту вершину, которая связана с текущей:

  • A соединяется с C и D

  • B соединяется с O, C и D

  • C соединяется с O, A, B, C, D

  • D соединяется с O, A, B, C, D

• маршрут начинается и заканчивается в точке O, поэтому для простоты мы исключим ее из маршрута, оставим только изменяющуюся часть — 4 вершины.

Как будем решать?

Решить данную задачу можно в лоб, методом перебора. Итак, мы будем перебирать 4 * 4 * 4 * 4 = 256 комбинации вершин:

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

Допустим, мы рассматриваем маршрут ADCB. Он невозможен для путника, поскольку первый шаг должен быть из точки O в одну из вершин, соединенных с этой точкой. Вершина A не соединяется с точкой O, такой маршрут мы должны отбросить.

Другой пример, маршрут CAAB — его также необходимо отбросить, поскольку в нем путнику придется дважды зайти в вершину A.

Еще пример, маршрут BACD, тоже отбрасываем, путник никак не может попасть из вершины B сразу в вершину A (второй шаг), так как эти вершины не связаны.

Итак, нам необходимо перебрать 256 комбинаций, из которых следует отбрасывать те, в которых:

• повторяется хотя бы одна из вершин

• любые две соседние вершины в комбинации не связаны ребром

• первая в комбинации вершина не связана с исходной точкой O

• последняя в комбинации вершина не связана с исходной точкой O

Решить данную задачу можно в цикле на обычном ПК, однако, мы преследуем учебные цели и хотим разработать решение для квантового компьютера. Для этого будем использовать квантовый алгоритм Гровера.

Выразим маршрут и вершины на языке кубит.

Возьмем 8 кубит, разобьем их условно на 4 пары. Первая пара соответствует первой вершине пути, вторая пара — второй вершине, и т.д. В каждой паре кубит возможна одна из 4-х комбинаций кубит: 00, 01, 10, 11. Положим, что каждой из этих комбинаций соответствует одна из возможных вершин: A, B, C, D:

Рассмотренные ранее комбинации ADCB, CAAB и BACD будут соответствовать следующим комбинациям кубит: 00111001, 10000001 и 01001011 соответственно.

Если мы применим к этим восьми кубитам оператор Адамара, то получим суперпозицию из всех возможных вариантов движения путника, то есть все 256 комбинаций. Далее в оракуле нам необходимо реализовать процедуры, которые будут проверять эти комбинации на соответствие условиям задачи.

Однако, еще до реализации оракула мы можем воспользоваться одной хитростью, которая позволит нам сократить число комбинаций почти в два раза.

3. Суперпозиция

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

Поскольку 1-ый шаг совершается из точки O, и первая вершина должна быть связана с этой точкой, значит это не может быть вершина A, это могут быть только вершины B, C или D. Аналогично, последний 5-ый шаг совершается из 4-ой вершины в точку O, и она должна быть связана с точкой O, значит это не может быть вершина A.

Раз первая вершина в маршруте может быть только вершиной B, C или D, то и первая пара кубит, соответствующая первой вершине в маршруте путника, может принимать только следующие значения: 01, 10 и 11. Это же справедливо и для последней пары кубит, соответствующей четвертой вершине маршрута.

Таким образом, мы исключим из суперпозиции ненужную комбинацию 00 (вершину A) для первой и четвертой вершины и, благодаря этому нам уже не потребуется в оракуле проводить проверку на связь этих вершин с точкой O, и мы сократим число комбинаций до 3 * 4 * 4 * 3 = 144.

Итак, рассмотрим, как работает этот прием для пары кубит.

Начальное состояние системы из двух кубит запишем следующим образом:

Выполним ряд преобразований.

Шаг 1. Подействуем на первый кубит оператором

с таким углом , при котором матрица оператора принимает следующий вид:

Не будем для угла искать «красивое» значение, положим его равным:

Посмотрим, как этот оператор подействует на первый кубит :

После действия оператора на первый кубит пары мы получим следующую суперпозицию 2-х кубит:

Шаг 2. Подействуем на второй кубит контролируемым вентилем Адамара

Контролируемый вентиль Адамара изменяет второй кубит только тогда, когда первый кубит равен

Шаг 3. Подействуем на второй кубит вентилем NOT

Ко второму кубиту применим вентиль NOT:

Итак, мы получили суперпозицию, в которой отсутствует комбинация 00.

После того, как мы подробно разобрали теоретическую часть, приступим к написанию соответствующей процедуры. Библиотека qiskit имеет в своем арсенале все вентили, приведенные в теоретической части:

• Однокубитный вентиль — QuantumCirquit.ry(theta, target_qubit)

  • theta — угол

  • target_qubit — кубит, на который воздействует вентиль

• Контролируемый вентиль Адамара — QuantumCirquit.ch(control_qubit, target_qubit)

  • control_qubit — контролирующий кубит

  • target_qubit — кубит, на который воздействует вентиль

• Однокубитный вентиль NOT— QuantumCirquit.x(target_qubit)

  • target_qubit — кубит, на который воздействует вентиль

Напишем процедуру, которая на вход будет получать пару кубит и применять к ним последовательно все перечисленные в теоретической части операторы:

import numpy as np

theta = 2 * np.arccos(1 / np.sqrt(3))

def exclude_00(qc, pair, reverse=False):

    if not reverse:
        qc.ry(theta, pair[0])
        qc.ch(pair[0], pair[1])
        qc.x(pair[1])
    else:
        qc.x(pair[1])
        qc.ch(pair[0], pair[1])
        qc.ry(-theta, pair[0])

Отмечу сразу, должна быть возможность выполнить данную процедуру в обратном порядке, поэтому мы ввели дополнительный аргумент reverse. О необходимости в этом подробнее расскажу позже.

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

4. Оракул

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

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

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

На рисунке условно изображена схема алгоритма для решения нашей задачи.

Рассмотрим детально содержание проверок на уникальность и на связанность вершин.

4.1. Контроль совпадения вершин

Задача данного блока состоит в том, чтобы не дать оракулу инвертировать результирующий кубит, если вдруг в комбинации встретятся хотя бы две одинаковых вершины.

Чтобы проверить, нет ли совпадающих вершин в комбинации, нам необходимо последовательно проверить все возможные пары вершин на равенство. Для каждой пары вершин будем проверять, не являются ли они обе одновременно либо вершинами A, либо B, либо C, либо D.

Представим, что на вход подаются две вершины A, тогда все четыре входных кубита равны 0. После применения ко всем четырем кубитам вентиля NOT они становятся равны 1. Множественный вентиль Тоффоли инвертирует результирующий кубит. Дальше в схеме кубиты будут подвержены преобразованию для проверки одновременного равенства вершинам B, C и D. Эти проверки будут неудачными и не изменят результирующий кубит, его значение останется инвертированным.

Если на вход подаются несовпадающие вершины, результирующий кубит на всех этапах схемы останется нетронутым.

Процедура проверки совпадения вершин

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

Eсли в качестве пар переданы одинаковые вершины, то процедура изменяет результирующий кубит на обратный, сигнализирует о совпадение вершин.

def find_equality(qc, pair_1, pair_2, result_qubit):

    qc.x(pair_1 + pair_2)
    qc.mct(pair_1 + pair_2, result_qubit)

    qc.x([pair_1[1], pair_2[1]])
    qc.mct(pair_1 + pair_2, result_qubit)

    qc.x(pair_1 + pair_2)
    qc.mct(pair_1 + pair_2, result_qubit)

    qc.x([pair_1[1], pair_2[1]])
    qc.mct(pair_1 + pair_2, result_qubit)

Полная схема «детектора совпадений» будет выглядеть примерно так:

В оракуле нам потребуется применить эту процедуру ко всем парам вершин, а поскольку у нас 4 вершины, то процедуру придется запустить 6 раз — это число сочетаний из 4-х по 2:

При восьми вершинах нам уже потребуется запустить данную функцию для 28 пар вершин. Именно эта часть алгоритма и является узким местом.

4.2. Проверка связи вершин

Задача данного блока оракула состоит в том, чтобы для всех трех пар рядом стоящих вершин определить, существует ли связывающее их ребро. Если хотя бы у одной такой пары нет связи, то процедура не позволяет оракулу, объявить комбинацию «хорошей» и изменить результирующий кубит. Изменив результирующий кубит на 0, процедура не даст оракулу объявить такой маршрут «хорошим».

Суммарная логика должна быть такая: результирующий кубит проверки на связанность вершин должен измениться (1 → 0) если хотя бы одна пара рядом стоящих вершин не будет связана ребром.

Как мы будем решать эту задачу?

Допустим мы проверяем 3-ю и 4-ю вершины маршрута. И допустим, 3-я вершина есть вершина A. Но мы знаем, что из вершины A можно попасть только в вершины C и D. Следовательно, сначала нужно проверить, выпала ли на 3-ем шаге вершина A, и если это так, то проверить, какая вершина следующая. Нам необходимо выявить именно негативные случаи, когда следующая 4-ая вершина не является ни вершиной C, ни D, и только в этом случае объявить комбинацию неудачной. Проверить это мы сможем от обратного, если 4-ая вершина является вершиной A или B (логически эквивалентно «ни C, ни D»), то считаем текущую комбинацию неудачной. Такая «обратная» форма для нас проще в реализации и позволит сократить число дополнительных кубит.

Не забываем про то, что нам необходимо провести аналогичные проверки для всех остальных случаев, когда третья вершина есть B, C или D. А также для всех возможных пар рядом стоящих вершин в маршруте.

Приступим к реализации данной процедуры. На вход ей будем подавать один кубит для результата и две пары кубит двух вершин. Первую будем называть основной, вторую — соседней.

Мы будем последовательно проверять, какой вершиной (A, B, C или D) является основная вершина. Для этого нам потребуется вентиль Тоффоли. Далее для каждой из возможных ситуаций будем проверять соседнюю вершину на предмет того, является ли она связанной с основной вершиной.

Логика работы процедуры следующая:

• Проверяем, является ли основная вершина вершиной A, если верно, то проверяем:

  • Является ли соседняя вершина вершиной A или B, если верно, то инвертируем результирующий кубит.

• Проверяем, является ли основная вершина вершиной B, если верно, то проверяем:

  • Является ли соседняя вершина вершиной A или B, если верно, то инвертируем результирующий кубит.

• Проверяем, является ли основная вершина вершиной C, если верно, то проверяем:

  • Является ли соседняя вершина любой, то инвертируем результирующий кубит (условие всегда выполняется).

• Проверяем, является ли основная вершина вершиной D, если верно, то далее логика аналогична логике с вершиной C.

Давайте детально рассмотрим алгоритм описанных выше проверок.

Сначала проверяем, является ли основная вершина вершиной A.

Но каким образом мы можем это проверить? Вершина A в виде кубит имеет представление 00, мы можем к обоим кубитам применить вентиль NOT, тогда пара станет равной 11. Далее мы направляем эту пару в вентиль Тоффоли в качестве контролирующих кубит, он инвертирует дополнительный кубит (0 → 1). Если основная вершина не является вершиной A, то дополнительный кубит останется неизменным. Если же равна — то дополнительный кубит будет инвертированным.

Далее, нам необходимо проверить соседнюю вершину на предмет равенства вершине A или B. Для этого мы вводим дополнительный кубит для сохранения промежуточного результата проверки, применяем множественный вентиль Тоффоли к двум кубитам проверяемой вершины, но также в качестве контрольного кубита подаем в вентиль дополнительный кубит с результатом проверки на равенство основной вершины вершине A. В случае успеха вентиль Тоффоли инвертирует кубит промежуточного результата проверки.

С теоретической частью закончили, приступаем к написанию процедуры.

Сначала составим общий список вершин, заодно зафиксируем для вершин представления в кубитах:

vertex_names = {
    'A': '00',
    'B': '01',
    'C': '10',
    'D': '11',
}

Зафиксируем все связи вершин (кроме точки O).

connections = {
    'A': ['C','D'],
    'B': ['C','D'],
    'C': ['A','B','D'],
    'D': ['A','B','C'],
}

Создадим справочник функций, который при подаче на вход вершины, соответствующей ключу в словаре, на выходе выдаст пару кубит 11. Вместе с вентилем Тоффоли этот справочник можно использовать как условный оператор.

vertex_to_11 = {
    'A': lambda qc, pair: qc.x(pair),
    'B': lambda qc, pair: qc.x(pair[0]),
    'C': lambda qc, pair: qc.x(pair[1]),
    'D': lambda qc, pair: None,
}

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

def find_disconnection(qc, pair_1, pair_2, ancilla_qubit, result_qubit):
    
    for letter_1 in connections.keys():
    
        vertex_to_find = [x for x in vertex_names.keys() if x not in connections[letter_1]]
        
        if len(vertex_to_find) > 0:

            vertex_to_11[letter_1](qc, pair_1)
            qc.toffoli(*pair_1, ancilla_qubit)
                        
            for letter_2 in vertex_to_find:
                vertex_to_11[letter_2](qc, pair_2)
                qc.mct([*pair_2, ancilla_qubit], result_qubit)
                vertex_to_11[letter_2](qc, pair_2)
            
            qc.toffoli(*pair_1, ancilla_qubit)
            vertex_to_11[letter_1](qc, pair_1)

Эта процедура проверяет одну пару рядом стоящих вершин на предмет существования связи между ними. Если подобной связи нет, то она инвертирует результирующий кубит (1 → 0) процедуры, что не позволит оракулу объявить данную комбинацию «хорошей».

5. Оператор диффузии

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

Пример действия оператора на вектор :

Пример действия оператора на любой другой вектор:

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

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

def diffusion(qc, qubits):

    qc.h(qubits)
    qc.x(qubits)

    qc.h(qubits[-1])

    length = len(qubits)

		if length > 3:
				qc.mct(qubits[0:-1], qubits[-1])
		elif length == 3:
				qc.toffoli(qubits[0:-1], qubits[2])
		elif length == 2:
				qc.cx(qubits[0], qubits[1])

    qc.h(qubits[-1])

    qc.x(qubits)
    qc.h(qubits)

В качестве центрального элемента оператора используется один из трех вентилей:

• когда на вход поступают всего 2 кубита — простой вентиль CNOT

• когда 3 кубита — вентиль Тоффоли

• когда 4 и более кубита — вентиль Тоффоли для многих кубит

Доработка оператора диффузии Гровера

Поскольку для создания начальной суперпозиции входных кубит мы не везде использовали однокубитный вентиль Адамара, нам потребуется видоизменить оператор диффузии.

В первоначальном виде оператор диффузии Гровера на входе применяет ко всем входным кубитам вентиль Адамара, тем самым как бы возвращая кубиты из суперпозиции в обычное несвязанное состояние. На выходе оператор снова применяет вентили Адамара для создания суперпозиции.

Однако, на шаге создания суперпозиции мы применили специальные операторы для исключения ненужных комбинаций из первой и четвертой пары кубит, а вентиль Адамара применили только ко второй и третьей.

Соответственно, для нашего алгоритма мы отключим в операторе диффузии Гровера входные и выходные вентили Адамара:

def diffusion(qc, qubits):
    # qc.h(qubits)
    qc.x(qubits)
    qc.h(qubits[-1])
    
    length = len(qubits)
    
    if length > 3:
        qc.mct(qubits[0:-1], qubits[-1])
    elif length == 3:
        qc.toffoli(qubits[0:-1], qubits[2])
    elif length == 2:
        qc.cx(qubits[0], qubits[1])
    
    qc.h(qubits[-1])
    qc.x(qubits)
    # qc.h(qubits)

Теперь он выглядит так:

А перед вызовом оператора будем применять преобразование, обратное созданию суперпозиции, после оператора — снова создание суперпозиции:

exclude_00(qc, qr[0:2], reverse=True)
qc.h(qr[2:6])
exclude_00(qc, qr[6:8], reverse=True)

diffusion(qc, qr[0:8])

exclude_00(qc, qr[0:2])
qc.h(qr[2:6])
exclude_00(qc, qr[6:8])

Тут нам и пригодилась инверсная версия процедуры исключения комбинации 00 из суперпозиции.

5. Собираем все вместе

Мы не будем подробно рассматривать принципы работы алгоритма Гровера с его учебными примерами, а сразу приступим к его реализации. Рассчитаем число итераций, пусть n — число входных кубит для оракула, в нашем случае оно равно 8, тогда количество итераций алгоритма Гровера должно быть следующим:

То есть, нам потребуется всего 2 итерации алгоритма для получения отчетливого результата.

5.1. Общая схема

Все составляющие алгоритма мы рассмотрели, начинаем сборку элементов в единую рабочую цепь. Общая схема выглядит следующим образом:

Скачиваем и устанавливаем библиотеки Qiskit, NumPy и Matplotlib для Python.

> pip3 install qiskit numpy matplotlib

Импортируем необходимые библиотеки.

import numpy as np
from qiskit import ClassicalRegister, QuantumRegister, QuantumCircuit, Aer, execute

Заранее подготовим процедуру поиска совпадений вершин.

def find_equality(...):
    # См. код процедуры выше

Заводим необходимые для работы переменные и вспомогательные функции:

vertex_names = {
    'A': '00',
    'B': '01',
    'C': '10',
    'D': '11',
}

connections = {
    'A': ['C','D'],
    'B': ['C','D'],
    'C': ['A','B','D'],
    'D': ['A','B','C'],
}

vertex_to_11 = {
    'A': lambda qc, pair: qc.x(pair),
    'B': lambda qc, pair: qc.x(pair[0]),
    'C': lambda qc, pair: qc.x(pair[1]),
    'D': lambda qc, pair: None,
}

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

def find_disconnection(...):
    # См. код процедуры find_disconnection выше

def diffusion(...):
    # См. код процедуры diffusion выше

Подготавливаем процедуру для исключения ненужных вершин из суперпозиции:

theta = 2 * np.arccos(1 / np.sqrt(3))

def exclude_00(qc, pair, reverse=False):
    # См. код процедуры exclude_00

Теперь необходимо решить, сколько нам всего потребуется кубит:

Итого, нам потребуются 19 кубит. Для измерения результата также необходимо зарезервировать 8 обычных бит.

Создаем квантовую цепь:

qr = QuantumRegister(19)
cr = ClassicalRegister(8)
qc = QuantumCircuit(qr, cr)

Создаем суперпозицию:

exclude_00(qc, qr[0:2])
qc.h(qr[2:6])
exclude_00(qc, qr[6:8])

Подготавливаем результирующий кубит:

qc.x(17)
qc.h(17)

Пишем цикл, который дважды запускает оракул и оператор диффузии Гровера.

pairs = [
    [[qr[0],qr[1]], [qr[2],qr[3]]],
    [[qr[0],qr[1]], [qr[4],qr[5]]],
    [[qr[0],qr[1]], [qr[6],qr[7]]],
    [[qr[2],qr[3]], [qr[4],qr[5]]],
    [[qr[2],qr[3]], [qr[6],qr[7]]],
    [[qr[4],qr[5]], [qr[6],qr[7]]],
]

for i in range(2):

    # Oracle
        
    qc.x(qr[8:17])
    
    for i, pair in enumerate(pairs):    
        find_equality(qc, pair[0], pair[1], qr[8 + i])
    
    find_disconnection(qc, pair_1=qr[2:4], pair_2=qr[0:2], ancilla_qubit=qr[18], result_qubit=qr[14])
    find_disconnection(qc, pair_1=qr[4:6], pair_2=qr[2:4], ancilla_qubit=qr[18], result_qubit=qr[15])
    find_disconnection(qc, pair_1=qr[6:8], pair_2=qr[4:6], ancilla_qubit=qr[18], result_qubit=qr[16])
    
    # Store result
    
    qc.mct(qr[8:17], qr[17])
    
    # Oracle (reverse)
    
    find_disconnection(qc, pair_1=qr[6:8], pair_2=qr[4:6], ancilla_qubit=qr[18], result_qubit=qr[16])
    find_disconnection(qc, pair_1=qr[4:6], pair_2=qr[2:4], ancilla_qubit=qr[18], result_qubit=qr[15])
    find_disconnection(qc, pair_1=qr[2:4], pair_2=qr[0:2], ancilla_qubit=qr[18], result_qubit=qr[14])

    for i, pair in enumerate(pairs):    
        find_equality(qc, pair[0], pair[1], qr[8 + i])
    
    qc.x(qr[8:17])

    # Diffuser
    
    exclude_00(qc, qr[0:2], reverse=True)
    qc.h(qr[2:6])
    exclude_00(qc, qr[6:8], reverse=True)
    
    diffusion(qc, qr[0:8])
    
    exclude_00(qc, qr[0:2])
    qc.h(qr[2:6])
    exclude_00(qc, qr[6:8])

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

Измерение результата:

qc.measure(qr[0:8], cr)

Итак, схема готова, теперь необходимо ее запустить.

Поскольку всего комбинаций 144, из них удачных только 4, то нам потребуется запустить алгоритм «приличное» число раз, чтобы отчетливо увидеть распределение вероятности удачных и неудачных маршрутов.

Запускаем алгоритм на симуляторе.

simulator = Aer.get_backend('qasm_simulator')
result = execute(qc, backend = simulator, shots = 1000).result()
counts = result.get_counts()
print(counts)

Получаем результат.

{'10011001': 1, ..., '11000110': 146, ..., '01100010': 4}

Метод measure класса QuantumCirquit возвращает ответ в виде массива с ключами, где каждый ключ соответствует комбинации кубит, а значение есть частота появления этой комбинации среди всех запусков алгоритма. Ключ представляет кубиты с 0-го по n-й справа налево, как принято при записи двоичных и десятичных чисел. Например:

Кроме того, этот массив не отсортирован, и найти в нем наиболее вероятные варианты тяжело. Напишем небольшое выражение, которое придаст результату «человекопонятный» вид.

answers = {''.join(dict(zip(map(lambda x: x[::-1], vertex_names.values()), vertex_names.keys()))[k[i*2:i*2+2]]
           for i in range(len(k)//2)): v
           for k, v in {item[0]: item[1]
           for item in sorted(counts.items(), key=lambda x:x[1], reverse=True)}.items()}
print(answers)

Получаем результат.

{'CADB': 161, 'BDAC': 135, 'DACB': 130, 'BCAD': 127, 'DCAC': 8, ... }

Теперь мы видим, что наибольшую частоту имеют маршруты:

{
    'CADB': 161,
    'BDAC': 135,
    'DACB': 130,
    'BCAD': 127
}

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

from qiskit.visualization import plot_histogram
plot_histogram(counts)

6. Выводы

Используя квантовый алгоритм Гровера мы с вами нашли гамильтоновы пути в графе с 5-ю вершинами. Практическое применение алгоритма Гровера требует учета ряда особенностей:

1. Характер суперпозиции влияет на оператор диффузии.

2. При запуске нескольких итераций необходимо применять инверсию оракула для экономии дополнительных кубит.

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

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

• Решения вообще может не быть, тогда вероятность всех маршрутов будет примерно одинаковая.

• Заранее неизвестно количество ответов. Зная это число, можно значительно сократить объем вычислений, необходимо применить к задаче алгоритмы поиска числа решений.

• Решение не подходит для числа вершин, отличного от 5-ти как в большую так и в меньшую сторону. Потребуется значительная переработка для адаптации.

• Рост числа вершин значительно увеличивает число кубит для обнаружения неуникальных вершин.

Надеюсь, статья будет кому-либо полезной:)

Ссылка на код алгоритма в репозитории GitHub

From Wikipedia, the free encyclopedia

This article is about the nature of Hamiltonian paths. For the question of the existence of a Hamiltonian path or cycle in a given graph, see Hamiltonian path problem.

In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are NP-complete.

Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the icosian game, now also known as Hamilton’s puzzle, which involves finding a Hamiltonian cycle in the edge graph of the dodecahedron. Hamilton solved this problem using the icosian calculus, an algebraic structure based on roots of unity with many similarities to the quaternions (also invented by Hamilton). This solution does not generalize to arbitrary graphs.

Despite being named after Hamilton, Hamiltonian cycles in polyhedra had also been studied a year earlier by Thomas Kirkman, who, in particular, gave an example of a polyhedron without Hamiltonian cycles.^[1] Even earlier, Hamiltonian cycles and paths in the knight’s graph of the chessboard, the knight’s tour, had been studied in the 9th century in Indian mathematics by Rudrata, and around the same time in Islamic mathematics by al-Adli ar-Rumi. In 18th century Europe, knight’s tours were published by Abraham de Moivre and Leonhard Euler.^[2]

Definitions[edit]

A Hamiltonian path or traceable path is a path that visits each vertex of the graph exactly once. A graph that contains a Hamiltonian path is called a traceable graph. A graph is Hamiltonian-connected if for every pair of vertices there is a Hamiltonian path between the two vertices.

A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once. A graph that contains a Hamiltonian cycle is called a Hamiltonian graph.

Similar notions may be defined for directed graphs, where each edge (arc) of a path or cycle can only be traced in a single direction (i.e., the vertices are connected with arrows and the edges traced «tail-to-head»).

A Hamiltonian decomposition is an edge decomposition of a graph into Hamiltonian circuits.

A Hamilton maze is a type of logic puzzle in which the goal is to find the unique Hamiltonian cycle in a given graph.^[3][4]

Examples[edit]

• A complete graph with more than two vertices is Hamiltonian
• Every cycle graph is Hamiltonian
• Every tournament has an odd number of Hamiltonian paths (Rédei 1934)
• Every platonic solid, considered as a graph, is Hamiltonian^[5]
• The Cayley graph of a finite Coxeter group is Hamiltonian (For more information on Hamiltonian paths in Cayley graphs, see the Lovász conjecture.)
• Cayley graphs on nilpotent groups with cyclic commutator subgroup are Hamiltonian.^[6]
• The flip graph of a convex polygon or equivalently, the rotation graph of binary trees, is Hamiltonian.^[7][8]

Properties[edit]

Any Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges, but a Hamiltonian path can be extended to Hamiltonian cycle only if its endpoints are adjacent.

All Hamiltonian graphs are biconnected, but a biconnected graph need not be Hamiltonian (see, for example, the Petersen graph).^[9]

An Eulerian graph G (a connected graph in which every vertex has even degree) necessarily has an Euler tour, a closed walk passing through each edge of G exactly once. This tour corresponds to a Hamiltonian cycle in the line graph L(G), so the line graph of every Eulerian graph is Hamiltonian. Line graphs may have other Hamiltonian cycles that do not correspond to Euler tours, and in particular the line graph L(G) of every Hamiltonian graph G is itself Hamiltonian, regardless of whether the graph G is Eulerian.^[10]

A tournament (with more than two vertices) is Hamiltonian if and only if it is strongly connected.

The number of different Hamiltonian cycles in a complete undirected graph on n vertices is (n – 1)!/2 and in a complete directed graph on n vertices is (n – 1)!. These counts assume that cycles that are the same apart from their starting point are not counted separately.

Bondy–Chvátal theorem[edit]

The best vertex degree characterization of Hamiltonian graphs was provided in 1972 by the Bondy–Chvátal theorem, which generalizes earlier results by G. A. Dirac (1952) and Øystein Ore. Both Dirac’s and Ore’s theorems can also be derived from Pósa’s theorem (1962). Hamiltonicity has been widely studied with relation to various parameters such as graph density, toughness, forbidden subgraphs and distance among other parameters.^[11] Dirac and Ore’s theorems basically state that a graph is Hamiltonian if it has enough edges.

The Bondy–Chvátal theorem operates on the closure cl(G) of a graph G with n vertices, obtained by repeatedly adding a new edge uv connecting a nonadjacent pair of vertices u and v with deg(v) + deg(u) ≥ n until no more pairs with this property can be found.

Bondy–Chvátal Theorem (1976) — A graph is Hamiltonian if and only if its closure is Hamiltonian.

As complete graphs are Hamiltonian, all graphs whose closure is complete are Hamiltonian, which is the content of the following earlier theorems by Dirac and Ore.

Dirac’s Theorem (1952) — A simple graph with n vertices () is Hamiltonian if every vertex has degree or greater.

Ore’s Theorem (1960) — A simple graph with n vertices () is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is n or greater.

The following theorems can be regarded as directed versions:

Ghouila–Houiri (1960) — A strongly connected simple directed graph with n vertices is Hamiltonian if every vertex has a full degree greater than or equal to n.

Meyniel (1973) — A strongly connected simple directed graph with n vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to

The number of vertices must be doubled because each undirected edge corresponds to two directed arcs and thus the degree of a vertex in the directed graph is twice the degree in the undirected graph.

Rahman–Kaykobad (2005) — A simple graph with n vertices has a Hamiltonian path if, for every non-adjacent vertex pairs the sum of their degrees and their shortest path length is greater than n.^[12]

The above theorem can only recognize the existence of a Hamiltonian path in a graph and not a Hamiltonian Cycle.

Many of these results have analogues for balanced bipartite graphs, in which the vertex degrees are compared to the number of vertices on a single side of the bipartition rather than the number of vertices in the whole graph.^[13]

Existence of Hamiltonian cycles in planar graphs[edit]

Theorem — A 4-connected planar triangulation has a Hamiltonian cycle.^[14]

Theorem — A 4-connected planar graph has a Hamiltonian cycle.^[15]

The Hamiltonian cycle polynomial[edit]

An algebraic representation of the Hamiltonian cycles of a given weighted digraph (whose arcs are assigned weights from a certain ground field) is the Hamiltonian cycle polynomial of its weighted adjacency matrix defined as the sum of the products of the arc weights of the digraph’s Hamiltonian cycles. This polynomial is not identically zero as a function in the arc weights if and only if the digraph is Hamiltonian. The relationship between the computational complexities of computing it and computing the permanent was shown by Grigoriy Kogan.^[16]

See also[edit]

Notes[edit]

References[edit]

• Berge, Claude; Ghouila-Houiri, A. (1962), Programming, games and transportation networks, New York: Sons, Inc.
• DeLeon, Melissa (2000), «A study of sufficient conditions for Hamiltonian cycles» (PDF), Rose-Hulman Undergraduate Math Journal, 1 (1), archived from the original (PDF) on 2012-12-22, retrieved 2005-11-28.
• Dirac, G. A. (1952), «Some theorems on abstract graphs», Proceedings of the London Mathematical Society, 3rd Ser., 2: 69–81, doi:10.1112/plms/s3-2.1.69, MR 0047308.
• Hamilton, William Rowan (1856), «Memorandum respecting a new system of roots of unity», Philosophical Magazine, 12: 446.
• Hamilton, William Rowan (1858), «Account of the Icosian Calculus», Proceedings of the Royal Irish Academy, 6: 415–416.
• Meyniel, M. (1973), «Une condition suffisante d’existence d’un circuit hamiltonien dans un graphe orienté», Journal of Combinatorial Theory, Series B, 14 (2): 137–147, doi:10.1016/0095-8956(73)90057-9, MR 0317997.
• Ore, Øystein (1960), «Note on Hamilton circuits», The American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928, MR 0118683.
• Pósa, L. (1962), «A theorem concerning Hamilton lines», Magyar Tud. Akad. Mat. Kutató Int. Közl., 7: 225–226, MR 0184876.

External links[edit]

• Weisstein, Eric W. «Hamiltonian Cycle». MathWorld.
• Euler tour and Hamilton cycles

Введение
После окончания Codeforces Beta Round #11 несколько участников захотели почитать что нибудь о задачах, похожих на задачу D этого раунда. Автор статьи, в целях помочь этим участникам, попытался найти подобную информацию, однако был удивлен, что ничего путного в интернете нет. Неизвестно, то ли автор плохо искал, то ли это действительно так, однако (на всякий случай), он решил написать собственную статью на эту тему.

В некотором смысле эту статью можно рассматривать как разбор задачи D 11го бета раунда.

В данной статье рассмотрены довольно известные алгоритмы поиска оптимальных гамильтоновых путей и циклов, а так же подсчет их количества, проверки существования и еще кое что. В качестве метода используется так называемый метод «динамика по подмножествам». Данный метод работает экспоненциальное время и использует экспоненциальный объем памяти от размерности графа. Поэтому применим только если граф очень маленький — как правило не более 20 вершин.

Динамика по подмножествам
Рассмотрим множество элементов, занумерованных от 0 до N - 1. Каждое подмножество этого множества можно закодировать последовательностью битов длины N (эту последовательность будем называть маской). Если i-й бит маски равен 1, то i-й элемент входит в подмножество, иначе — нет. Например, маска 00010011 означает, что в подмножестве находятся элементы 0, 1 и 4 из множества [0… 7]. Всего получается 2^N масок, задающих 2^N подмножеств. Каждая маска по сути является целым числом, записанном в двоичной системе счисления.

Метод состоит в том, чтобы каждой маске (а значит и каждому подмножеству) сопоставлять какое либо значение и, на основе уже просчитанных значений для некоторых масок, получать значения для других масок. Как правило, в процессе просчета из текущего подмножества A извлекается один элемент всеми допустимыми способами и из полученных подмножеств A₁‘, A₂‘, … , A_k‘ получается значение для A. Однако для этого все значения для A_i‘ уже должны быть вычислены. Поэтому требуется установить порядок, в котором будут просматриваться маски. Несложно понять, что перебор масок в порядке возрастания чисел, которыми и являются эти маски, нам подойдет.

Для дальнейшего повествования примем следующие обозначения:
bit(i, mask) — i-й бит маски mask
count(mask) — количество битов 1 в маске mask
first(mask) — наименьший номер бита 1 в маске mask
(a?b: c) — возвратить b если выполняется a, или возвратить c в противном случае.
Элементами множества будут являться вершины графа. Для простоты мы будем считать, что граф является неориентированным. Модификация нижеприведенных алгоритмов для случая ориентированного графа предоставляется читателю.

1. Нахождение кратчайшего гамильтонова пути
Пусть в графе G = (V, E) n вершин и каждое ребро имеет некоторый вес d(i, j). Необходимо найти гамильтонов путь, сумма весов по ребрам которого минимальна.

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

Динамика считается по следующим соотношениям:
dp[mask][i] = 0, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1 и bit(i, mask) = 1;
dp[mask][i] = ∞ во всех остальных случаях.

Теперь искомая минимальная длина пути . Если p_min = ∞, то гамильтонова пути в графе, увы, нет. Восстановить сам путь несложно. Пусть минимальный путь заканчивается в вершине i. Тогда j ≠ i, для которого , является предыдущей вершиной пути. Теперь удалим i из множества и только что описанным способом найдем вершину предыдущую к j. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.

Данное решение требует O(2ⁿn) памяти и O(2ⁿn²) времени.

2. Нахождение количества гамильтоновых путей
Пусть теперь у нас есть невзвешенный граф G = (V, E). Модифицируем предыдущий алгоритм. Пусть dp[mask][i] теперь означает количество гамильтоновых путей подмножества mask, заканчивающихся в вершине i. Динамика перепишется следующим образом:
dp[mask][i] = 1, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1 и bit(i, mask) = 1;
dp[mask][i] = 0 во всех остальных случаях.

Ответом будет число .

Решение требует O(2ⁿn) памяти и O(2ⁿn²) времени.

3. Нахождение количества простых цепей
Посчитаем динамику, указанную в предыдущем пункте. Ответом будет являться число . Коэффициент 1 / 2 необходим, поскольку каждую цепь мы учитываем 2 раза — в одном и обратном направлении. Так же следует отметить, что тут учтены только пути длины хотя бы 1. При желании можно к ответу добавить n путей длины 0.

Данное решение требует O(2ⁿn) памяти и O(2ⁿn²) времени.

4. Проверка существования гамильтонова пути
Тут можно обойтись решением 2, заменив сумму на побитовое ИЛИ. Тогда dp[mask][i] будет содержать булево значение — существует ли в подмножестве mask гамильтонов путь, заканчивающийся в вершине i. Сама динамика будет такая:
dp[mask][i] = 1, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1 и bit(i, mask) = 1;
dp[mask][i] = 0 во всех остальных случаях.

Это решение, как и решение 2, требует O(2ⁿn) памяти и O(2ⁿn²) времени. Эту оценку можно улучшить, если изменить динамику следующим образом.

Пусть dp‘[mask] хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве mask, заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: dp‘[mask] будет равно . Для графа G выпишем n масок M_i, для каждой вершины задающие множество вершин, которые связаны ребром в данной вершиной. То есть .

Тогда динамика перепишется следующим образом:
dp‘[mask] = 2ⁱ, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1;
dp‘[mask] = 0 во всех остальных случаях.

Особое внимание следует уделить выражению . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве mask без вершины i, а вторая — подмножество вершин, связанных с i ребром. Если эти множества пересекаются хотя бы по одной вершине (их and не равен 0), то, как нетрудно понять, в mask существует гамильтонов путь, заканчивающийся в вершине i.

Окончательная проверка состоит в сравнении dp[2ⁿ - 1] c 0.

Это решение использует O(2ⁿ) памяти и имеет асимптотику O(2ⁿn).

5. Нахождение кратчайшего гамильтонова цикла
Поскольку нам безразлично с какой вершины начинаться цикл, пусть он начинается с вершины 0. Далее, воспользуемся решением 1 для подмножества вершин, видоизменив соотношения следующим образом:
dp[1][0] = 0;
, если i > 0, bit(0, mask) = 1 и bit(i, mask) = 1;
dp[mask][i] = ∞ во всех остальных случаях.

Таким образом, dp[mask][i] будет содержать длину кратчайшего гамильтонова пути от вершины 0 до вершины i.

Искомый минимум нужно будет выбирать по формуле . Если полученный минимум равен ∞, то искомого цикла не существует. Искомый цикл восстанавливается аналогично решению 1.

6. Нахождение количества гамильтоновых циклов
Используя идеи решений 5 и 2, можно получить динамику, считающую количество гамильтоновых циклов за время O(2ⁿn²), использующее O(2ⁿn) памяти.

7. Нахождение количества простых циклов
Пусть dp[mask][i] означает количество гамильтоновых путей в подмножестве вершин mask, начинающихся в вершине first(mask) и заканчивающихся в вершине i. Переход динамики выглядит так:
dp[mask][i] = 1, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1, bit(i, mask) = 1 и i ≠ first(mask);
dp[mask][i] = 0 иначе.

Ответом будет являться сумма .

Это решение за время O(2ⁿn²) и память O(2ⁿn).

8. Проверка существования гамильтонова цикла
Модифицируем решение 5 и, воспользовавшись приемом, описанном в решении 4, получим решение для этой задачи за время O(2ⁿn) и память O(2ⁿ).

Упражнения
CFBR11D
CCTOOLS

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

Если граф содержит срезанную вершину или срезанное ребро, то у него нет гамильтонова цикла. Когда срезанные вершины или ребра пересекаются, пропадает возможность вернуться, чтобы завершить цикл. Например:

На графике видно, что нет способа вернуться на другую сторону графа, когда мы пересекаем вершину

или ребро

.

Рассмотрим следующую теорему:

Например, мы можем попытаться удалить одну вершину, которая разбивает граф на два или более компонентов. Это будет вершина разреза. Или мы можем попытаться удалить две вершины, чтобы разбить граф на три или более компонентов. И так дальше по возрастанию.

Например, возьмем

. Три компоненты графа

показаны справа:

Число компонентов

больше, чем

, поэтому гамильтонова цикла не существует.

и

действуют как узкое место. Каждый раз, когда мы хотим покинуть одну из компонент

, мы должны использовать либо

, либо

. Таким образом, мы расходуем

и

и не можем завершить наше круговое путешествие.

Эта теорема дает необходимое, но не достаточное условие для гамильтонова цикла. Существует множество графов, которые удовлетворяют этому условию, но не имеют гамильтоновых циклов. Одним из таких примеров является граф Петерсена.

Существует противоположная теорема:

Такую теорему доказать немного проще. Основная идея состоит в том, что когда мы проходим через гамильтонов цикл в

и достигаем компоненты

, единственный способ достичь других вершин, не входящих в эту компоненту — это вернуться через

. Получается, у

должно быть столько же вершин, сколько и компонент

:

Другой пример приведен ниже. Четыре вершины удалены, и полученный граф имеет пять компонент, поэтому в нем нет гамильтонова цикла: