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

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

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

Пусть \( G = (V, E) \) — неориентированный граф, где \( V \) — множество вершин, а \( E \) — множество рёбер. Гамильтоновым циклом называется простой цикл (без повторяющихся вершин), содержащий все вершины \( V \). Аналогично, для ориентированного графа \( G = (V, A) \) гамильтонов цикл — это ориентированный простой цикл, проходящий через все вершины.

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

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

История

Первые упоминания о задачах, связанных с обходом всех вершин графа, встречаются ещё в работах древнегреческих математиков, однако систематическое изучение началось в XIX веке. В 1857 году Уильям Гамильтон представил игру «Вокруг света» (Icosian game), в которой требовалось найти маршрут, проходящий через все 20 вершин додекаэдра и возвращающийся в исходную точку. Гамильтон продал права на игру лондонскому производителю игрушек, но коммерческого успеха она не имела.

Термин «гамильтонов цикл» был введён в 1878 году немецким математиком Германом Минковским, а затем популяризирован в трудах Артура Кэли и Уильяма Томсона (лорда Кельвина). В XX веке задача стала одной из центральных в теории графов и теории сложности вычислений.

Свойства и критерии существования

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

Теорема Дирака (1952)

Если в неориентированном графе \( G \) с \( n \) вершинами (\( n \geq 3 \)) степень каждой вершины не меньше \( n/2 \), то граф является гамильтоновым.

Теорема Оре (1960)

Если для любой пары несмежных вершин \( u \) и \( v \) в графе \( G \) с \( n \) вершинами (\( n \geq 3 \)) выполняется неравенство \( \deg(u) + \deg(v) \geq n \), то граф гамильтонов.

Теорема Бонди — Хватала (1976)

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

Необходимые условия

• Удаление \( k \) вершин из гамильтонова графа приводит к появлению не более \( k \) компонент связности.
• Гамильтонов граф не может содержать «висячих» вершин (степени 1), если \( n > 2 \).

Классификация

По типу графа

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

По структуре

• Полные графы \( K_n \) (при \( n \geq 3 \)) всегда гамильтоновы.
• Графы-циклы \( C_n \) сами являются гамильтоновыми циклами.
• Графы Петерсена — известный пример негамильтонова графа, хотя он и является полугамильтоновым.
• Турниры (полные ориентированные графы) всегда содержат гамильтонову цепь, а при \( n \geq 3 \) — и гамильтонов цикл (теорема Редеи, 1934).

Алгоритмические аспекты

Задача поиска гамильтонова цикла (или цепи) в произвольном графе является NP-полной. Это означает, что для неё не известно полиномиального алгоритма, и при этом её можно свести к любой другой NP-полной задаче (например, к задаче коммивояжёра).

Точные алгоритмы

• Перебор с возвратом (backtracking) — простейший метод, перебирающий все возможные перестановки вершин. Трудоёмкость \( O(n!) \).
• Алгоритм Хелда — Карпа (1962) — метод динамического программирования, работающий за \( O(2^n \cdot n^2) \). Позволяет находить гамильтонов цикл за экспоненциальное время, но значительно быстрее полного перебора.
• Алгоритм Робертса — Флореса — улучшенный перебор с использованием эвристик (например, правило «ближайшего соседа»).

Приближённые и эвристические методы

Для практических задач (например, в логистике) часто применяются приближённые алгоритмы:

• Жадный алгоритм — на каждом шаге выбирается ближайшая непосещённая вершина.
• Алгоритм имитации отжига — стохастический метод, моделирующий процесс охлаждения твёрдого тела.
• Генетические алгоритмы — эволюционные методы, оперирующие популяцией возможных решений.
• Метод ветвей и границ — точный, но с отсечением заведомо неперспективных вариантов.

Применение

Гамильтоновы циклы находят широкое применение в различных областях:

• Логистика и транспорт — задача коммивояжёра, где требуется найти кратчайший маршрут, проходящий через все заданные точки (города, склады) и возвращающийся в исходную. Является обобщением задачи о гамильтоновом цикле на взвешенные графы.
• Проектирование интегральных схем — размещение компонентов и трассировка соединений, где необходимо минимизировать длину проводников.
• Криптография — построение псевдослучайных последовательностей и генерация ключей на основе гамильтоновых циклов в графах.
• Биоинформатика — сборка геномов из коротких фрагментов ДНК (задача о гамильтоновом пути в графе перекрытий).
• Робототехника — планирование маршрутов для мобильных роботов, обходящих все точки интереса.
• Социальные сети — анализ связей и поиск замкнутых цепочек знакомств.

Примеры

Полный граф \( K_4 \)

Граф с четырьмя вершинами, соединёнными всеми возможными рёбрами. Любая перестановка вершин, начинающаяся и заканчивающаяся в одной точке, образует гамильтонов цикл. Например, \( 1 \to 2 \to 3 \to 4 \to 1 \).

Граф-звезда \( S_3 \)

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

Граф Петерсена

Известный негамильтонов граф с 10 вершинами и 15 рёбрами. Он не содержит гамильтонова цикла, но содержит гамильтонову цепь. Долгое время считался контрпримером к некоторым гипотезам о гамильтоновости.

Интересные факты

• Задача о гамильтоновом цикле тесно связана с проблемой P vs NP. Если бы существовал полиномиальный алгоритм её решения, то это доказало бы равенство классов P и NP, что является одной из семи «задач тысячелетия» (за решение которых Институт Клэя назначил премию в 1 млн долларов).
• В 1970-х годах советский математик Георгий Адельсон-Вельский (соавтор алгоритма АВЛ-дерева) предложил эффективный эвристический алгоритм поиска гамильтоновых циклов в случайных графах.
• В некоторых графах (например, в графе додекаэдра) существует ровно 30 различных гамильтоновых циклов, что было найдено самим Гамильтоном вручную.
• Термин «гамильтонов» иногда путают с «гамильтоновым» в физике (гамильтониан), но это разные понятия: гамильтониан — это оператор полной энергии системы, а гамильтонов цикл — чисто комбинаторный объект.

Источники

• Харари Ф. Теория графов. — М.: Мир, 1973.
• Оре О. Теория графов. — М.: Наука, 1980.
• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.
• Бонди Дж. А., Мурти У. С. Р. Теория графов. — М.: Мир, 1984.
• Дирак Г. А. Теорема о гамильтоновых графах // Proceedings of the London Mathematical Society. — 1952. — Т. 2. — С. 69–81.