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

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

История

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

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

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

Пусть \(G = (V, E)\) — неориентированный или ориентированный граф, где \(V\) — множество вершин, а \(E\) — множество рёбер (или дуг).

Гамильтонов путь — это простой путь (путь, в котором все вершины различны), содержащий все вершины графа. Длина такого пути равна \(|V| - 1\).

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

Полугамильтонов граф — это граф, который содержит гамильтонов путь, но не содержит гамильтонова цикла.

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

Критерии существования гамильтонова пути

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

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

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

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

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

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

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

Условия для гамильтонова пути

Для существования гамильтонова пути (не цикла) существуют аналогичные достаточные условия. Например, если для любой пары несмежных вершин \(u\) и \(v\) выполняется \(\deg(u) + \deg(v) \ge n - 1\), то граф содержит гамильтонов путь.

Сложность задачи

Задача о гамильтоновом пути (Hamiltonian Path Problem, HPP) является NP-полной. Это означает, что для неё не известно полиномиального алгоритма решения, и если бы такой алгоритм был найден, то он бы позволил решить все задачи класса NP за полиномиальное время (что решило бы проблему равенства классов P и NP).

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

• Алгоритм Хелда — Карпа (1962): метод динамического программирования, решающий задачу за \(O(2^n n^2)\) времени. Это лучший известный точный алгоритм для общего случая.
• Метод ветвей и границ: эвристический алгоритм, отсекающий заведомо бесперспективные варианты.
• Алгоритмы на основе поиска с возвратом (backtracking): простейший способ, но крайне медленный для больших графов.

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

Применение

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

• Задача коммивояжёра (TSP): классическая задача оптимизации, в которой требуется найти кратчайший гамильтонов цикл во взвешенном графе. TSP является NP-трудной, но её частные случаи (например, с метрикой) решаются приближёнными алгоритмами.
• Планирование маршрутов: прокладка маршрутов для доставки товаров, обхода территорий, контроля оборудования.
• Проектирование интегральных схем: задача трассировки соединений на кристалле, где необходимо соединить все контакты, не пересекая запрещённые зоны.
• Криптография: некоторые криптографические протоколы основаны на сложности нахождения гамильтонова пути в графе.
• Биоинформатика: сборка геномов (реконструкция последовательности ДНК по фрагментам) может быть сведена к задаче поиска гамильтонова пути в графе де Брёйна.
• Головоломки и игры: многие логические игры (например, «ходи конём», «волк, коза и капуста» в обобщённом виде) сводятся к поиску гамильтонова пути.

Примеры

• Полный граф \(K_n\) (где каждая вершина соединена со всеми остальными) всегда содержит гамильтонов цикл при \(n \ge 3\).
• Граф-цикл \(C_n\) (кольцо) сам является гамильтоновым циклом.
• Граф Петерсена (известный контрпример) не содержит гамильтонова цикла, но содержит гамильтонов путь (является полугамильтоновым).
• Граф-звезда (одна центральная вершина, соединённая с листьями) не содержит гамильтонова пути, если число листьев больше двух, так как центральная вершина будет посещена дважды, или листья останутся непосещёнными.

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

• Задача о гамильтоновом пути является одной из 21 NP-полных задач, перечисленных в знаменитой работе Ричарда Карпа (1972).
• В 2000 году Clay Mathematics Institute включил проблему равенства классов P и NP (к которой напрямую относится задача о гамильтоновом пути) в список «Задач тысячелетия» с призом в 1 миллион долларов за решение.
• Для графов, представляющих собой правильные многогранники (платоновы тела), всегда существуют гамильтоновы циклы (теорема Гамильтона — Киркмана).
• В 2023 году группа исследователей из Китая и США предложила новый алгоритм на основе квантовых вычислений, который в некоторых частных случаях позволяет находить гамильтоновы пути быстрее, чем классические методы, однако практическая реализация пока ограничена.