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

Теорема Бонди — Хватала — это классический результат теории графов, устанавливающий достаточное условие для того, чтобы граф являлся гамильтоновым. Теорема была независимо сформулирована и доказана Джоном Адрианом Бонди и Вацлавом Хваталом в 1976 году. Она обобщает более ранние результаты, такие как теорема Дирака и теорема Оре, и формулируется в терминах замыкания графа.

Формулировка

Пусть \( G \) — простой граф с \( n \) вершинами (\( n \ge 3 \)). Замыканием графа \( G \) называется граф \( \text{cl}(G) \), полученный из \( G \) последовательным соединением рёбрами всех несмежных пар вершин \( u \) и \( v \), для которых выполняется неравенство:

\[ \deg(u) + \deg(v) \ge n \]

Процесс повторяется до тех пор, пока не останется ни одной такой пары. Результат не зависит от порядка соединения вершин.

Теорема Бонди — Хватала утверждает: граф \( G \) является гамильтоновым тогда и только тогда, когда его замыкание \( \text{cl}(G) \) является гамильтоновым.

Из этого, в частности, следует, что если замыкание графа является полным графом \( K_n \), то исходный граф гамильтонов. Это даёт практический критерий проверки гамильтоновости.

История

Предшествующие результаты

Проблема нахождения гамильтоновых циклов — одна из старейших в теории графов. В 1952 году Габриэль Дирак доказал, что если в графе с \( n \) вершинами степень каждой вершины не меньше \( n/2 \), то граф гамильтонов. В 1960 году Ойстин Оре обобщил этот результат: если для любой пары несмежных вершин \( u, v \) выполняется \( \deg(u) + \deg(v) \ge n \), то граф гамильтонов.

Работа Бонди и Хватала

Джон Адриан Бонди (Великобритания) и Вацлав Хватал (Чехословакия, позже Канада) в 1976 году независимо друг от друга предложили концепцию замыкания графа. Они показали, что условие Оре является частным случаем более общего принципа: если в процессе добавления рёбер по указанному правилу граф становится полным, то исходный граф гамильтонов. Их работа была опубликована в журнале Discrete Mathematics (Bondy, 1976) и в Journal of Combinatorial Theory (Chvátal, 1976).

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

Основная идея

Доказательство опирается на индукцию по числу шагов замыкания. На каждом шаге добавляется ребро между вершинами \( u \) и \( v \), для которых \( \deg(u) + \deg(v) \ge n \). Если граф \( G' = G + uv \) гамильтонов, то и \( G \) гамильтонов. Для доказательства этого факта используется метод от противного: предполагается, что \( G \) не гамильтонов, но \( G' \) гамильтонов, и строится противоречие с условием на степени.

Ключевая лемма

Пусть \( G \) — не гамильтонов граф с \( n \) вершинами. Тогда существуют две несмежные вершины \( u \) и \( v \) такие, что \( \deg(u) + \deg(v) \le n-1 \). Эта лемма является переформулировкой теоремы Оре и служит основой для доказательства Бонди — Хватала.

Следствия и обобщения

Теорема Дирака

Если \( \delta(G) \ge n/2 \), то для любой пары вершин \( \deg(u) + \deg(v) \ge n \), и замыкание становится полным графом. Таким образом, теорема Дирака является частным случаем теоремы Бонди — Хватала.

Теорема Оре

Аналогично, условие Оре (\( \deg(u) + \deg(v) \ge n \) для всех несмежных пар) непосредственно приводит к полному замыканию.

Другие обобщения

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

Примеры

Пример 1: Граф, удовлетворяющий условию

Рассмотрим граф \( G \) с 5 вершинами, имеющий степени вершин: 3, 3, 2, 2, 2. Сумма степеней для любой пары несмежных вершин не менее 5? Проверим: если две вершины степени 2 не смежны, то сумма 4 < 5. Однако после добавления рёбер между парами с суммой ≥ 5 замыкание может стать полным. В данном случае замыкание — полный граф \( K_5 \), значит, \( G \) гамильтонов.

Пример 2: Граф, не удовлетворяющий условию

Граф-звезда \( K_{1,4} \) (одна вершина степени 4, четыре вершины степени 1) имеет замыкание, не являющееся полным. Действительно, для любых двух листьев сумма степеней 2 < 5, и ребро между ними не добавляется. Такой граф не гамильтонов.

Применение

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

Теорема Бонди — Хватала лежит в основе некоторых алгоритмов проверки гамильтоновости. Построение замыкания графа требует \( O(n^3) \) операций в наивной реализации, но может быть оптимизировано. Однако в общем случае задача остаётся NP-полной, и теорема даёт лишь достаточное условие.

Комбинаторная оптимизация

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

Критика и ограничения

Теорема не является необходимым условием: существуют гамильтоновы графы, замыкание которых не является полным. Например, цикл \( C_n \) при \( n \ge 5 \) гамильтонов, но его замыкание — он сам, а не полный граф. Таким образом, теорема полезна лишь для определённого класса графов с достаточно высокими степенями вершин.

Источники

• Bondy, J. A. (1976). Pancyclic graphs I. Journal of Combinatorial Theory, Series B, 20(1), 80–84.
• Chvátal, V. (1976). On Hamilton’s ideals. Journal of Combinatorial Theory, Series B, 21(1), 73–80.
• Дирак, Г. (1952). Теорема о существовании гамильтоновых циклов. Proceedings of the London Mathematical Society.
• Оре, О. (1960). Заметка о гамильтоновых цепях. American Mathematical Monthly.