- Гамильтоновы графы
- Содержание
- Основные определения [ править ]
- Достаточные условия гамильтоновости графа [ править ]
- Теорема Дирака [ править ]
- Теорема Оре [ править ]
- Теорема Поша [ править ]
- Теорема Редеи-Камиона [ править ]
- Теорема Гуйя-Ури [ править ]
- Теорема Хватала [ править ]
- Задача о коммивояжере [ править ]
- Описание задачи [ править ]
- Варианты решения [ править ]
- Псевдокод [ править ]
- Алгоритм нахождения гамильтонова цикла [ править ]
- Алгоритм нахождения гамильтонова пути [ править ]
- Способы поиска гамильтонова цикла
Гамильтоновы графы
Содержание
Основные определения [ править ]
| Определение: |
| Гамильтоновым путём (англ. Hamiltonian path) называется простой путь, проходящий через каждую вершину графа ровно один раз. |
| Определение: |
| Гамильтоновым циклом (англ. Hamiltonian cycle) называют замкнутый гамильтонов путь. |
| Определение: |
| Граф называется полугамильтоновым (англ. Semihamiltonian graph), если он содержит гамильтонов путь. |
| Определение: |
| Граф называется гамильтоновым (англ. Hamiltonian graph), если он содержит гамильтонов цикл. |
Очевидно, что любой гамильтонов граф также и полугамильтонов.
Достаточные условия гамильтоновости графа [ править ]
Теорема Дирака [ править ]
Теорема Оре [ править ]
Теорема Поша [ править ]
Теорема Редеи-Камиона [ править ]
Теорема Гуйя-Ури [ править ]
Теорема Хватала [ править ]
Тогда если [math] \forall k \in \mathbb N [/math] верна импликация:
[math] d_k \leqslant k \lt n/2 \Rightarrow d_
Задача о коммивояжере [ править ]
Рассмотрим алгоритм нахождения гамильтонова цикла на примере задачи о коммивояжёре.
Описание задачи [ править ]
| Задача: |
| Задача о коммивояжере (англ. Travelling salesman problem, TSP) — задача, в которой коммивояжер должен посетить [math] N [/math] городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей? |
Варианты решения [ править ]
Задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения с экспоненциальным временем работы.
Перебор перестановок [ править ]
Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все [math] N! [/math] всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших [math]N[/math] . Сложность алгоритма [math]O(
Динамическое программирование по подмножествам (по маскам) [ править ]
Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе. Зафиксируем начальную вершину [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 \ne 0[/math] или [math]mask \ne 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>\times
Для того, чтобы восстановить сам путь, воспользуемся соотношением [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\<\begin
Это решение требует [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_
Тогда динамика перепишется следующим образом:
[math] d'[mask] = \left\<\begin
Особое внимание следует уделить выражению [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 \rangle[/math] мы смотрим на состояния
[math]\langle j, mask — 2^j \rangle[/math] , и [math]|mask| = |mask — 2^j| + 1[/math] , то состояния с большим [math]|mask|[/math] должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта. Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти).
Дальше ищем сам цикл:
Алгоритм нахождения гамильтонова цикла [ править ]
Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла. В массиве [math]d[i][mask][/math] мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает [math] true[/math] , то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.
Алгоритм нахождения гамильтонова пути [ править ]
Алгоритм нахождения гамильтонова пути легко получить, используя алгоритм нахождения гамильтонова цикла. Нужно добавить в граф еще одну вершину и ребра от нее до всех остальных вершин и из всех остальных вершин до неё. И далее запустить алгоритм поиска цикла от новой вершины. В восстановлении пути учтем, что эта вершина лишняя, и не будем записывать её в путь.
Источник
Способы поиска гамильтонова цикла
Copy raw contents
Лабораторная работа по гамильтоновым циклам, 2016 год
Задача A. Гамильтонов цикл в полном графе
Имя входного файла: fullham.in
Имя выходного файла: fullham.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дан граф из N вершин, в котором степень любой вершины не меньше N/2. Ваша задача — найти гамильтонов цикл.
Формат входных данных
На первой строке входного файла записано целое число N ( 3 ≤ N ≤ 4 000) — количество вершин в графе. На следующих N строках записана матрица смежности. Т.к. матрица смежности симметрична, а на диагонали всегда стоят нули, на i-й строке записаны _i_− 1 символ
- нули и единицы. Если j-й символ i-й строки равен единице, значит есть ребро между вершинами i и j. Гарантируется, что в графе есть гамильтонов цикл и, что степень каждой вершины не меньше N/2.
Формат выходных данных
Выведите перестановку из N чисел — номера вершин в порядке гамильтонова цикла.
fullham.in
fullham.out
Задача B. Поиск гамильтонова цикла в условиях теоремы Хватала
Имя входного файла: chvatal.in
Имя выходного файла: chvatal.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дан граф из N вершин, для которого выполняется условие теоремы Хватала, то есть, в отсортированной последовательности его степеней вершин d_k для любого k k, либо d_n−k ≥ n−k. Ваша задача — найти гамильтонов цикл.
Формат входных данных
На первой строке входного файла записано целое число N ( 3 ≤ N ≤ 100 ) — количество вершин в графе. На следующих N строках записана матрица смежности. Т.к. матрица смежности симметрична, а на диагонали всегда стоят нули, на i-й строке записаны _i_− 1 символ � нули и единицы. Если j-й символ i-й строки равен единице, значит есть ребро между вершинами i и j.
Формат выходных данных
Выведите перестановку из N чисел — номера вершин в порядке гамильтонова цикла.
chvatal.in
chvatal.out
Задача C. Интерактивная восточная сказка
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
У злого волшебника Джафара много ламп, которые он холит и лелеет, и любит очень сильно, но из каждой пары ламп он всё же может выбрать одну, которую он любит даже сильнее, чем другую.
Он захотел расставить их в ряд так, чтобы когда он будет идти вдоль этого ряда каждая следующая лампа была им более любима, чем предыдущая.
Новому слуге Джафара поручено это сделать, но. он не знает предпочтений Джафара! Про любую пару ламп можно спросить у волшебника, какую он любит больше, но нельзя излишне навязываться с вопросами (отрубание головы еще никто не отменял). Помогите слуге расположить лампы или узнать, что это невозможно (и сброситься со скалы).
Формат входных данных
Первое число, которое будет передано во входном потоке, — N ( 1 ≤ N ≤ 1000 ), количество ламп.
Затем на каждый вопрос слуги, который ваша программа выведет в выходной поток, во входном потоке будет дан ответ — слово “YES”, если лампа Y_i более любима чем X_i, и слово “NO”, если X_i более любима чем Y_i.
Заметьте, что отношение «более любима чем» не обязано быть транзитивным.
Формат выходных данных
В выходной файл вы можете выводить запросы Каждый вопрос — одна строчка с тремя числами 1, X_i, Y_i ( 1 ≤ Xi, Y_i ≤ N; X_i ≠ Yi). Вы можете задать не более 10 000вопросов.
В последней строчке выведите число 0, а затем N целых числел от 1 до N — номера ламп в порядке, в котором их надо расставить. Если же расставить лампы невозможно, выведите (N + 1)ноль.
стандартный ввод
стандартный вывод
Обязательно сбрасывайте буфер при выводе запросы: в Pascal используйте flush(output); , в C используйте fflush(stdout); , в C++ используйте cout.flush(); , в Java используйте System.out.flush(); .
Задача D. Цикл в турнире
Имя входного файла: guyaury.in
Имя выходного файла: guyaury.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Найдите гамильтонов цикл в полном ориентированном сильносвязном графе.
Формат входных данных
В первой строке входного файла содержится число n( 1 ≤ n ≤ 1000 ) — число вершин в графе.
Далее следует n строк имеющих длину, соответственно, 0, 1, 2. , n − 1. В i-й из этих строк j-й символ задает равняется 1, если ребро ведет из вершины i в вершину j, и 0, если из вершины j в вершину i.
Формат выходных данных
В выходной файл выведите номера вершин в порядке их следования в найденном гамильтоновом цикле.
Источник
