Замыкание графа¶

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

¶Определение

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

В контексте гамильтоновых графов под замыканием обычно понимают замыкание по степени, введённое венгерским математиком Ласло Ловасом и независимо американским математиком Джоном Адрианом Бонди. Операция заключается в следующем: для каждой пары несмежных вершин \( u \) и \( v \), сумма степеней которых \( \deg(u) + \deg(v) \) не меньше числа вершин \( n \) графа, между ними добавляется ребро. Процесс повторяется, пока есть такие пары.

¶История

Понятие замыкания графа было предложено в 1970-х годах как инструмент для доказательства и обобщения классических теорем о гамильтоновых циклах, таких как теорема Дирака и теорема Оре. Ласло Ловас и Джон Адриан Бонди независимо друг от друга сформулировали операцию замыкания, которая позволяет свести задачу проверки гамильтоновости графа к проверке гамильтоновости его замыкания. Впоследствии замыкание стало стандартным методом в теории графов, используемым не только для гамильтоновых циклов, но и для других свойств, таких как существование гамильтонова пути, совершенных паросочетаний и факторов.

¶Свойства замыкания по степени

Замыкание графа \( G \) по степени обладает рядом важных свойств, которые делают его полезным инструментом.

¶Единственность

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

¶Сохранение гамильтоновости

Ключевое свойство замыкания по степени заключается в том, что граф \( G \) является гамильтоновым (содержит гамильтонов цикл) тогда и только тогда, когда его замыкание \( \text{cl}(G) \) является гамильтоновым. Это свойство позволяет свести проверку гамильтоновости исходного графа к проверке гамильтоновости его замыкания, которое часто имеет более простую структуру (например, может быть полным графом).

¶Монотонность

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

¶Алгоритм построения

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

Временная сложность алгоритма в худшем случае составляет \( O(n^3) \), где \( n \) — число вершин графа, так как на каждом шаге может потребоваться проверка всех пар вершин, а количество шагов может быть порядка \( O(n^2) \). Однако на практике алгоритм часто завершается быстро.

¶Применение

¶Доказательство теорем о гамильтоновых графах

Замыкание графа является центральным инструментом в доказательстве многих теорем о существовании гамильтоновых циклов. Например, теорема Бонди — Хватала утверждает, что граф является гамильтоновым тогда и только тогда, когда его замыкание является гамильтоновым. Эта теорема обобщает более ранние результаты Дирака и Оре.

¶Критерий гамильтоновости

Замыкание позволяет сформулировать простой критерий гамильтоновости: если замыкание графа \( G \) является полным графом, то \( G \) — гамильтонов. Это следует из того, что полный граф всегда гамильтонов, а свойство гамильтоновости сохраняется при замыкании.

¶Анализ свойств графов

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

¶Пример

Рассмотрим граф \( G \) с 5 вершинами, рёбра которого образуют цикл \( 1-2-3-4-5-1 \). Степени всех вершин равны 2. Сумма степеней любой пары несмежных вершин (например, 1 и 3) равна 4, что меньше числа вершин \( n = 5 \). Поэтому условие замыкания не выполняется, и замыкание \( \text{cl}(G) \) совпадает с исходным графом \( G \). Этот граф является гамильтоновым (он сам является циклом).

Рассмотрим другой граф \( H \) с 5 вершинами, где вершины 1, 2, 3, 4 образуют полный граф \( K_4 \), а вершина 5 соединена только с вершиной 1. Степени: \( \deg(1) = 4 \), \( \deg(2) = \deg(3) = \deg(4) = 3 \), \( \deg(5) = 1 \). Проверим пары несмежных вершин: (5,2): \( 1+3=4 < 5 \); (5,3): \( 1+3=4 < 5 \); (5,4): \( 1+3=4 < 5 \). Условие не выполняется, замыкание совпадает с \( H \). Граф \( H \) является гамильтоновым (например, цикл 1-2-3-4-5-1).

Теперь рассмотрим граф \( J \) с 5 вершинами, где вершины 1, 2, 3, 4 образуют цепь \( 1-2-3-4 \), а вершина 5 соединена со всеми четырьмя вершинами. Степени: \( \deg(1)=2 \), \( \deg(2)=2 \), \( \deg(3)=2 \), \( \deg(4)=2 \), \( \deg(5)=4 \). Несмежные пары: (1,3): \( 2+2=4 < 5 \); (1,4): \( 2+2=4 < 5 \); (2,4): \( 2+2=4 < 5 \). Условие не выполняется, замыкание совпадает с \( J \). Граф \( J \) является гамильтоновым (цикл 1-2-3-4-5-1).

¶Ограничения и обобщения

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

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

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

¶Источники

• Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.
• Diestel, R. (2017). Graph Theory (5th ed.). Springer.
• Харари, Ф. (2003). Теория графов. М.: УРСС.