Алгоритм все гамильтоновы циклы

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

Полный взвешенный граф из 500 вершин задан матрицей смежности.

Необходимо найти гамильтонов цикл в этом графе как можно меньшей суммарной стоимости.

2. Решение

1. Жадный алгоритм

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

Просто и быстро.

Однако ответ может быть очень и очень далеким от правды.

Жадина хорошо работает на случайном графе, однако тут мы ничего про граф не знаем.

Поэтому идем дальше.

2. Честный перебор

Задача коммивояжера, она же поиск гамильтонова цикла минимальной суммарной стоимости – NP-тяжелая, так что полный перебор для такого графа может продлиться вечность, поэтому данная идея не подходит.

3. Метод ветвей и границ

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

Один из наиболее эффективных алгоритмов такого рода является метод ветвей и границ («поиск с возвратом», «backtracking»), разработанный Литтлом, Мерти, Суини, Кэрелом в 1963 г.

Пусть S(0) – множество всех допустимых замкнутых маршрутов задачи о коммивояжере с n городами и матрицей затрат c.

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

Алгоритм состоит из двух этапов:

Первый этап

Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r.

1. Вычисляем наименьший элемент в каждой строке(константа приведения для строки)

2. Переходим к новой матрице затрат, вычитая из каждой строки ее константу приведения

3. Вычисляем наименьший элемент в каждом столбце(константа приведения для столбца)

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

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

5. Вычисляем r как сумму констант приведения для столбцов и строк.

Второй (основной) этап

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

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

а) Ищем все нулевые элементы в приведенной матрице

б) Для каждого из них считаем его штраф за неиспользование.

в) Выбираем элемент, которому соответствует максимальный штраф

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

2. Теперь наше множество S(0) разбиваем на два – Sw(содержащие ребро h,k) и Sw/o(не содержащие ребро h,k)

3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.

а) Для множества Sw/o все просто: раз мы не берем ребро (h,k), то для него оценка затрат равна оценки затрат множества S(0) + штраф за неиспользование ребра (h,k)

б) При вычислении затрат для множества Sw примем во внимание, что раз ребро (h,k) входит в маршрут, то значит ребро (k,h) в маршрут входить не может, поэтому в матрице затрат пишем c(k,h)=infinity, а так как из пункта h мы «уже ушли», а в пункт k мы «уже пришли», то ни одно ребро, выходящее из h, и ни одно ребро, приходящее в k, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h и столбец k. После этого приводим матрицу, и тогда оценка затрат для Sw равна сумме оценки затрат для S(0) и r(h,k), где r(h,k) – сумма констант приведения для измененной матрицы затрат.

4. Из множеств Sw и Sw/o выбирается то, которое имеет наибольшую оценку.

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

Теперь результаты.

Если на каждом шаге выбирать только из двух множеств(Sw и Swo) то алгоритм работает вполне вменяемое время, однако точность просто ужасна ( проигрывает ОЧЕНЬ много жадине из п.1)

Если же на каждом шаге выбирать лучшее множество из всех, полученных к этому шагу и не использовавшихся до этого,

то для маленьких графов(порядка 40-50) вершин, получается хорошая точность, но 500 вершин дождаться не удалось.

Поэтому в голову приходит следующая идея:

4. Метод ветвей и границ с эвристикой

Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (x,y) или нет, и вешаем двух детей – Sw(x,y) и Sw/o(x,y). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.

Первый и самый простой вариант эвристики cost=mark – k*depth. k подбираем в зависимости от среднего веса ребра так, чтобы все-таки глубина не играла определяющей роли. Так же добавим, например, что depth равно минимум b, т.е. если наша вершина находится на расстоянии q от корня, и q<b, то depth=b, иначе depth=q. В качестве b выбираем такое число, что до такой глубины честный алгоритм ветвей и границ ( без эвристики ) доходит за адекватное время. В моем случае было b=30.

Запускаем, ждем.

За ночь работы получаем ответ, который выигрывает у жадного алгоритма ~2%.

Мало, очень мало, учитывая, что жадный алгоритм работает пару секунд и пишется за 5 минут.

И теперь победитель:

Жадный алгоритм с локальным методом границ и ветвей

Алгоритм такой:

1.Запускаем жадный алгоритм, получаем некоторый маршрут.

2. Делим маршрут на несколько частей.

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

4. На каждой из этих частей запускаем метод ветвей и границ, без эвристики.

5. Объединяем части, оптимизированные методом ветвей и границ, размыкая фиктивные ребра и соединяя последнюю вершину n-1 части с первой n части.

Как легко понять, этот алгоритм имеет несколько плюсов.

– честный метод ветвей и границ, без использования эвристики;

– легко параллелится, выигрываем во времени работы;

– жадный алгоритм говорит нам лишь части разбиений, после объединения мы используем только NUMBER_OF_PARTS-1 ребер, данных нам жадным алгоритмом, и не оптимизированных методом ветвей и границ.

Результат.

Время работы на 25 частях – 3 минуты, выигрываем у жадины ~7%

10 частей – 4 часа, выигрыш ~15%

продолжение

Источник

Гамильтоновы пути и циклы

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

Рис. 8.1.

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

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

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

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

Алгоритм 2. Поиск гамильтоновых циклов

выбрать произвольно вершину
while do
if
then взять
if вершина не находится в PATH
then
if PATH содержит все вершины
then if смежна с
then выдать цикл
else удалить вершину из PATH

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

Рис. 8.2.

Источник

Описание алгоритма[править]

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

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

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

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

Функция получает на вход граф и находит гамильтонов цикл в нем.

– очередь вершин графа

findHamiltonianCycle(): for : // Добавляем все вершины графа в очередь queue.pushBack() for k = 0..n * (n – 1) if (queue.at(0), queue.at(1)) // Проверяем существования ребра между первой и второй вершинами очереди i = 2 while (queue.at(0), queue.at(i)) or (queue.at(1), queue.at(i + 1)) i++ // Ищем индекс удовлетворяющую условию вершины queue.swapSubQueue(1, i) // Разворачиваем часть перестановки от 1-й до найденной позиции включительно queue.pushBack(queue.top()) queue.pop()

Доказательство алгоритма[править]

Лемма:

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

Доказательство:

Рассмотрим множество , состоящее из индексов вершин, смежных с , и множество , индексов вершин смежных с . Заметим, что , а , тогда , а значит , в то же время (по условию теоремы Оре или теоремы Дирака). Из этого следует, что , а это и значит, что искомая вершина существует.

Лемма:

После итераций между каждой парой соседних вершин очереди существует ребро.

Доказательство:

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

Теорема:

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

Доказательство:

Из предыдущих лемм следует корректность алгоритма.

Сложность алгоритма[править]

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

См.также[править]

Гамильтоновы графы
Теорема Оре
Теорема Дирака
Очередь

Источники информации[править]

Дискретная математика: Алгоритмы – Гамильтоновы графы

Источник

Задача о гамильтоновом пути и задача о гамильтоновом цикле – это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны[1].

Связь задач о гамильтоновом пути и гамильтоновом цикле[править | править код]

Существует простое отношение между задачами нахождения гамильтонова пути и нахождения гамильтонова цикла. В одном направлении задача о гамильтоновом пути для графа эквивалентна задаче о гамильтоновом цикле в графе H, полученного из графа G путём добавления новой вершины и соединения её со всеми вершинами графа G. Таким образом, поиск гамильтонова пути не может быть существенно медленнее (в худшем случае, как функция числа вершин), чем поиск гамильтонова цикла.

В обратном направлении задача о гамильтоновом цикле для графа G эквивалентна задаче о гамильтоновом пути в графе H, полученном копированием одной вершины v графа G (в v’), то есть вершина v’ будет иметь ту же окрестность, что и v, и добавлением двух вспомогательных вершин степени один, одна из которых соединена с v, а другая с v'[2].

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

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

Есть n! различных последовательностей вершин, которые могут быть гамильтоновыми путями в заданном графе с n вершинами (и их столько в полном графе), так что алгоритм полного перебора, который перебирает все возможные последовательности, был бы очень медленным.

Ранний точный алгоритм нахождения гамильтонова цикла в ориентированном графе был алгоритмом перебора (алгоритм Мартелло)[3].

Процедура поиска Франка Рубина[4] разбивает рёбра графа на три класса – те, которые должны быть на пути, те, которые пути принадлежать не могут, и рёбра, для которых решение не принято. В процессе поиска набор правил принятия решений классифицирует рёбра, для которых решение не принято, и определяет, остановиться или продолжить поиск. Алгоритм разбивает граф на компоненты, которые могут быть обработаны отдельно.

Для решения задачи за время может быть использован алгоритм динамического программирования Беллмана, Хелда и Карпа. В этом методе определяется для каждого набора S вершин и каждой вершины v из S, существует ли путь, проходящий через все вершины S и заканчивающийся в v. Для каждой пары (S,v) путь существует тогда и только тогда, когда v имеет соседнюю вершину w такую, что существует путь для , который можно получить из уже полученной информации динамического программирования[5][6].

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

Используя этот метод, он показал, как решить задачу о гамильтоновом цикле для произвольных графов с n вершинами с помощью алгоритма Монте-Карло за время . Для двудольных графов этот алгоритм можно улучшить до времени [7].

Для графов с максимальной степенью три аккуратный поиск с возвратом может найти гамильтонов цикл (если таковой существует) за время [8].

Гамильтоновы пути и циклы можно найти с помощью SAT решателя.

Ввиду сложности решения задач о гамильтоновом пути и цикле на обычных компьютерах, они изучались для нестандартных моделей вычислений. Например, Леонард Адлеман показал, что задачи о гамильтоновом пути могут быть решены с помощью ДНК-компьютера. Используя параллелелизм, свойственный химическим реакциям, задача может быть решена с помощью нескольких шагов химических реакций, линейно зависящих от числа вершин графа. Однако это требует факториальное число молекул ДНК, участвующих в реакции[9].

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

Сложность[править | править код]

Задача нахождения гамильтонова цикла или пути имеет сложность FNP[en]. Аналогичная задача разрешимости – проверить, существует ли гамильтонов цикл или путь. Ориентированные и неориентированные задачи о гамильтоновом цикле являлись двумя из 21 NP-полных задач Карпа. Они остаются NP-полными даже для неориентированных планарных графов максимальной степени три[11], для ориентированных планарных графов с полустепенью входа и выхода, не превосходящими двух[12], для неориентированных планарных 3-регулярных двудольных графов без мостов, для 3-связных 3-регулярных двудольных графов[13], подграфов квадратной решётки[14] и для кубических подграфов квадратной решётки[15].

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

Складывая всё вместе, остаётся открытой задача, всегда ли 3-связные 3-регулярные двудольные планарные графы должны содержать гамильтонов цикл и если должны, задача, ограниченная этими графами, не будет NP-полной (см. статью «Гипотеза Барнетта»).

В графах в которых все вершины имеют нечётную степень, довод, связанный с леммой о рукопожатиях, показывает, что число гамильтоновых циклов через фиксированное ребро всегда чётно, так что если дан один гамильтонов цикл, то и другой должен существовать[18]. Однако поиск этого второго цикла не выглядит как простая вычислительная задача. Пападимитриу определил класс сложности PPA[en], чтобы собрать вместе задачи, подобные этой[19].

Примечания[править | править код]

↑ Garey, Johnson, 1979, с. 199-200, A1.3: GT37 – 39.
↑ graph theory – Reduction from Hamiltonian cycle to Hamiltonian path – Mathematics Stack Exchange
↑ Martello, 1983, с. 131-138.
↑ Rubin, 1974, с. 576-80.
↑ Bellman, 1962, с. 61-63.
↑ Held, Karp, 1962, с. 196-210.
↑ Björklund, 2010, с. 173-182.
↑ Iwama, Nakashima, 2007, с. 108-117.
↑ Adleman, 1994, с. 1021-1024.
↑ Oltean, 2006, с. 217-227.
↑ Garey, Johnson, Stockmeyer, 1974, с. 47-63.
↑ Plesńik, 1979, с. 199-201.
↑ Akiyama, Nishizeki, Saito, 1980-1981, с. 73-76.
↑ Itai, Papadimitriou, Szwarcfiter, 1982, с. 676-686.
↑ Buro, 2000, с. 250-261.
↑ Chiba, Nishizeki, 1989, с. 187-211.
↑ Schmid, Schmidt, 2018.
↑ Thomason, 1978, с. 259-268.
↑ Papadimitriou, 1994, с. 498-532.

Литература[править | править код]

Michael R. Garey, David S. Johnson. [Computers and Intractability: A Guide to the Theory of NP-Completeness Computers and Intractability: A Guide to the Theory of NP-Completeness]. – W.H. Freeman, 1979. – ISBN 978-0-7167-1045-5.
Silvano Martello. An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph // ACM Transactions on Mathematical Software. – 1983. – Т. 9, вып. 1. – С. 131-138. – doi:10.1145/356022.356030.
Frank Rubin. A Procedure for Hamilton Paths and Circuits // Journal of the ACM. – 1974. – Т. 21, вып. 4. – С. 576-80. – doi:10.1145/321850.321854.
Richard Bellman. Dynamic programming treatment of the travelling salesman problem // Journal of the ACM. – 1962. – Т. 9. – С. 61-63. – doi:10.1145/321105.321111.
Held, Karp. A dynamic programming approach to sequencing problems // J. SIAM. – 1962. – Т. 10, вып. 1. – С. 196-210. – doi:10.1137/0110015.
Andreas Björklund. Determinant sums for undirected Hamiltonicity // Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS ’10). – 2010. – С. 173-182. – ISBN 978-1-4244-8525-3. – doi:10.1109/FOCS.2010.24.
Kazuo Iwama, Takuya Nakashima. An improved exact algorithm for cubic graph TSP // Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007). – 2007. – Т. 4598. – С. 108-117. – (Lecture Notes in Computer Science). – ISBN 978-3-540-73544-1. – doi:10.1007/978-3-540-73545-8_13.
Leonard Adleman. Molecular computation of solutions to combinatorial problems // Science. – 1994. – Ноябрь (т. 266, вып. 5187). – С. 1021-1024. – doi:10.1126/science.7973651. – Bibcode: 1994Sci…266.1021A. – PMID 7973651.
Mihai Oltean. A light-based device for solving the Hamiltonian path problem // Unconventional Computing. – Springer LNCS 4135, 2006. – doi:10.1007/11839132_18.
Michael Garey, David S. Johnson, Larry Stockmeyer. Some simplified NP-complete problems // Proc. 6th ACM Symposium on Theory of Computing (STOC ’74). – 1974. – С. 47-63. – doi:10.1145/800119.803884.
Plesńik J. The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two // rmation Processing Letters. – 1979. – Т. 8, вып. 4. – С. 199-201. – doi:10.1016/0020-0190(79)90023-1.
Takanori Akiyama, Takao Nishizeki, Nobuji Saito. NP-completeness of the Hamiltonian cycle problem for bipartite graphs // Journal of rmation Processing. – 1980-1981. – Т. 3, вып. 2. – С. 73-76.
Alon Itai, Christos Papadimitriou, Jayme Szwarcfiter. Hamilton Paths in Grid Graphs // SIAM Journal on Computing. – 1982. – Т. 4, вып. 11. – С. 676-686. – doi:10.1137/0211056.
Michael Buro. Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs // Conference on Computers and Games. – 2000. – Т. 2063. – С. 250-261. – (Lecture Notes in Computer Science). – ISBN 978-3-540-43080-3. – doi:10.1007/3-540-45579-5_17.
Norishige Chiba, Takao Nishizeki. The Hamiltonian cycle problem is linear- solvable for 4-connected planar graphs // Journal of Algorithms. – 1989. – Т. 10, вып. 2. – С. 187-211. – doi:10.1016/0196-6774(89)90012-6.
Andreas Schmid, Jens M. Schmidt. Computing Tutte Paths // Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP’18), to appear.. – 2018.
Thomason A. G. Hamiltonian cycles and uniquely edge colourable graphs // Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977). – 1978. – Т. 3. – С. 259-268. – (Annals of Discrete Mathematics). – ISBN 9780720408430. – doi:10.1016/S0167-5060(08)70511-9.
Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence // Journal of Computer and System Sciences. – 1994. – Т. 48, вып. 3. – С. 498-532. – doi:10.1016/S0022-0000(05)80063-7.

Источник