Гамильтонов граф

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

История

Изучение гамильтоновых графов началось с задачи о коммивояжёре и с работ Гамильтона, однако систематическое исследование свойств таких графов развернулось в XX веке. В 1930-х годах венгерский математик Денеш Кёниг в своей монографии «Теория конечных и бесконечных графов» (1936) заложил основы теории графов, включая и вопросы, связанные с гамильтоновыми циклами. В 1952 году Габриэль Эндрю Дирак сформулировал достаточное условие существования гамильтонова цикла (теорема Дирака), а в 1960-х годах Ойстейн Оре и Ласло Поза предложили более общие критерии. В 1970-е годы, с развитием вычислительной техники, проблема распознавания гамильтоновых графов была доказана как NP-полная (Ричард Карп, 1972), что стимулировало поиск приближённых алгоритмов и частных критериев.

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

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

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

Связь с эйлеровыми графами

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

Классификация и примеры

Примеры гамильтоновых графов

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

Примеры негамильтоновых графов

• Граф-звезда \(K_{1,3}\) — не содержит гамильтонова цикла, так как центральная вершина имеет степень 3, а листья — степень 1, что нарушает необходимые условия.
• Графы, состоящие из двух полных подграфов, соединённых одной вершиной (например, «песочные часы») — часто не имеют гамильтонова цикла.
• Графы с мостом (ребром, удаление которого увеличивает число компонент связности) — если в графе есть мост, то он не может быть гамильтоновым, так как гамильтонов цикл не может «пересечь» мост дважды.

Условия существования гамильтонова цикла

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

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

• Граф должен быть связным (иначе невозможно пройти через все вершины одним циклом).
• Каждая вершина должна иметь степень не менее 2 (иначе цикл не сможет войти и выйти из вершины).
• Теорема (необходимое условие): Если граф гамильтонов, то удаление любого подмножества вершин \(S\) приводит к тому, что число компонент связности в полученном графе не превышает \(|S|\). Это условие не является достаточным, но часто используется для доказательства негамильтоновости.

Достаточные условия

• Теорема Дирака (1952): Если в графе с \(n \ge 3\) вершинами степень каждой вершины не менее \(n/2\), то граф является гамильтоновым.
• Теорема Оре (1960): Если для любой пары несмежных вершин \(u\) и \(v\) выполняется \(\deg(u) + \deg(v) \ge n\), то граф гамильтонов.
• Теорема Поза (1962): Если для любого \(k\) от 1 до \((n-1)/2\) число вершин степени не более \(k\) меньше \(k\), то граф гамильтонов.
• Теорема Бонди — Хватала (1976): Обобщение теоремы Оре: если замыкание графа (добавление рёбер между несмежными вершинами с суммой степеней не менее \(n\)) является полным графом, то исходный граф гамильтонов.

Критерий Хватала

Вацлав Хватал в 1972 году предложил критерий, основанный на последовательности степеней вершин. Если граф с последовательностью степеней \(d_1 \le d_2 \le \dots \le d_n\) удовлетворяет условию: для каждого \(i < n/2\) либо \(d_i > i\), либо \(d_{n-i} \ge n-i\), то граф гамильтонов. Это одно из наиболее мощных достаточных условий.

Применение

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

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

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

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

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

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

• Игра «Кругосветное путешествие» Гамильтона представляла собой деревянный додекаэдр, на вершинах которого были написаны названия городов. Требовалось найти маршрут, проходящий через каждый город ровно один раз и возвращающийся в начальный.
• Граф Петерсена (10 вершин, 15 рёбер) является одним из самых известных негамильтоновых графов. Он также не содержит гамильтонова пути, то есть является «негамильтоновым» в полном смысле.
• Проблема существования гамильтонова цикла в кубических графах (графах, где все вершины имеют степень 3) остаётся открытой: гипотеза Тейта (1880) утверждала, что любой трёхсвязный кубический планарный граф содержит гамильтонов цикл, но в 1946 году Уильям Татт опроверг её, построив контрпример (граф Татта).
• В 1970-е годы была доказана NP-полнота задачи о гамильтоновом цикле для неориентированных графов, что сделало её одной из классических задач теории сложности.

Источники

• Дирак Г. А. Теоремы о гамильтоновых графах // Математический сборник. — 1952.
• Оре О. Заметки о гамильтоновых циклах // American Mathematical Monthly. — 1960.
• Хватал В. Новые критерии гамильтоновости графов // Journal of Combinatorial Theory. — 1972.
• Карп Р. М. Сводимость комбинаторных задач // Complexity of Computer Computations. — 1972.
• Бонди Дж. А., Мурти У. С. Р. Теория графов. — М.: Мир, 1984.
• Харари Ф. Теория графов. — М.: Мир, 1973.