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

В прошлом параграфе мы отметили три вида графов, про которые заранее
известно, что они гамильтоновы: циклы, полные графы и полные равно-дольные
двудольные графы. Два последних вида графов максимально насыщены связями и
содержат, в зависимости от порядка графа, большое число гамильтоновых
циклов. Понятно, что возникает желание найти и описать множество графов,
которые менее насыщены связями чем полные графы, но для которых можно
указать достаточно простые для проверки условия, из которых следует, что
удовлетворяющие этим условиям графы будут гамильтоновы. Ясно, что речь идет
об относительно простых для проверки достаточных условиях
«гамильтоновости» графа.

Насыщенность графа связями можно выразить через степени вершин графа. Так в
полном графе $K_n$ степень каждой его вершины $v$, которую обозначим через
$d(v)$, будет равна $n – 1$. То есть, $d(v) = n – 1$. Следовательно, нас
будут интересовать достаточные условия существования в графе гамильтоновых
циклов для случаев, когда все или некоторые вершины имеют степени меньшие $n – 1$.

Чтобы перейти к формулировкам уже найденных достаточных условий того, что
граф является гамильтоновым, отметим некоторые очевидные или легко
проверяемые факты. Так, если какой-то граф является гамильтоновым и не
является полным, то в него всегда можно добавить связь (добавить ребро,
соединяющее несмежные вершины) и граф останется гамильтоновым. Далее, если
степень вершины $v_i$, т.е. $d(v_i ) = d_i$, то вершины графа можно
пронумеровать (упорядочить) таким образом, что $1 le d_1 le d_2 le … le d_n le n – 1$
(здесь предполагается, что граф порядка n — обыкновенный
и связный). Такую упорядоченную последовательность степеней вершин будем
называть графовой или степенной последовательностью.

Несложно проверить, что не любая неубывающая последовательность натуральных
чисел $d_1 le d_2 le … le d_n $ является степенной последовательностью.
Например, неубывающая последовательность $d_1 le d_2 le … le d_n$, где
$d_1 = 1$, а $d_{n – 1} = n – 1$ не будет степенной последовательностью, так
как не существует такого графа, для которого члены последовательности были
бы степенями вершин. Действительно, для степенной последовательности из
$d_{n – 1} = n – 1$ следует, что и $d_n = n – 1$. А это значит, что, по
крайней мере, две вершины должны быть связаны ребрами со всеми остальными
вершинами. Откуда следует, что степени остальных вершин больше либо равны
двум. То есть, из $d_{n – 1} = n – 1$ следует, что в степенной
последовательности $d_1 > 1$.

Ясно, что если $d_1 le d_2 le … le d_n $ степенная последовательность
неполного $n$-графа, то добавив в этот граф одну связь (одно ребро) и
упорядочив вершины полученного нового графа по степеням вершин, мы получим
новую степенную последовательность
$1 le {d}’_1 le {d}’_2 le … le {d}’_n le n – 1$.
Покажем, что в этом случае элементы новой последовательности связаны с элементами исходной последовательности
соотношениями ${d}’_i ge d_i$, $i = 1,2,…,n$. То есть, что
последовательность ${d}’_1 le {d}’_2 le … le {d}’_n $ будет
мажорирующей для последовательности $d_1 le d_2 le … le d_n$.

Докажем вначале вспомогательное утверждение.

Лемма. Если в неубывающей последовательности
$d_1 le d_2 le … le d_n $ увеличить на единицу число $d_i$, а затем привести
последовательность к неубывающему виду ${d}’_1 le {d}’_2 le … le {d}’_n$,
переставив число $d_i + 1$ на положенное место $j$, то исходная
последовательность будет мажорироваться полученной.

Доказательство. Если $j = i$, то утверждение леммы, очевидно,
выполняется. Пусть $j ne i$ и $d_1 ,d_2 ,…d_i ,d_{i + 1} ,…,d_j ,…,d_n $ —
исходная последовательность.

Рассмотрим элементы последовательностей с номерами $s = 1,2,…,i – 1$.
Элементы с указанными номерами исходной последовательности не изменятся при
переходе к новой последовательности, следовательно, в этом случае ${d}’_s = d_s$.

Далее, каждый элемент ${d}’_s $ с номером $s = i, …, j – 1$ новой
последовательности равен элементу с номером $s + 1$ исходной
последовательности, т.е. ${d}’_s = d_{s + 1}$.
Поскольку $d_s le d_{s + 1}$, то $d_s le {d}’_s$.

Рассмотрим $j$-ый элемент ${d}’_j $. В силу упорядоченности
${d}’_j ge {d}’_{j – 1} = d_j$. То есть, ${d}’_j ge d_j$.

Элементы с номерами $s = j + 1, …, n$ новой последовательности будут
совпадать с элементами исходной последовательности, т.е. и в этом случае
${d}’_s = d_s$.

Итак, мы показали, что для всех $s = 1,2,…,n$ будет выполняться ${d}’_s ge d_s$.
Лемма доказана.

Применив доказанную лемму два раза, получим утверждение:
при добавлении ребра в граф, полученная степенная последовательность будет
мажорировать исходную степенную последовательность графа.

Наиболее просто проверяемым условием существования в графе гамильтонова
цикла является условие Дирака. Сформулируем это условие в виде теоремы.

Теорема Дирака (1952 год). Если $n ge 3$ и $d(v) ge frac{1}{2}n$
для любой вершины $v$ $n$-графа $Gamma$, то $Gamma $ — гамильтонов граф.

Более общим условием по отношению к условию Дирака является условие Оре.

Теорема Оре (1960 год). Если $n ge 3$ и $d(u) + d(v) ge n$ для
любой пары вершин $u$ и $v$ $n$-графа $Gamma $, то $Gamma $ — гамильтонов граф.

Отметим, что условие Дирака является частным случаем условий Оре.
Естественно, что условия Оре более сложно проверять, поскольку оно
сформулировано для степеней несмежных вершин.

Обобщение условий Дирака и Оре.

Теорема Поша (1962 год). Пусть $Gamma $ имеет $n ge 3$ вершин.
Если для всякого k, $1 le k

Постараемся пояснить условия Поша, учитывая, что в число вершин, обладающих
указанными выше свойствами, мы должны включить и пустое множество вершин
(т.е. 0 вершин), положив степень этого множества-вершины равной 0. Это
требование вытекает из того, что условие Дирака, формулируемое только через
степени вершин, должно быть частным случаем условия Поша. Заметим, что если
на величину степени $q$-ой вершины наложено ограничение в виде $d_q le m$, то
этому свойству, в силу упорядоченности степеней, будут удовлетворять и все
степени $d_j$, для $0 le j le q$. То есть, условию $d_q le m$ будут
удовлетворять, по крайней мере, q вершин (для $q ge 1$).

Рассмотрим условия: для всякого $k$, $1 le k k$. Нетрудно видеть, что на языке «числа вершин» это
условие можно прочесть следующим образом: «существует такое максимальное
$j$ (число вершин) из промежутка $0 le j le k – 1$, что $d_j le k$ и $d_k$
этому условию не удовлетворяет, т.е. $d_k > k$. Это полностью эквивалентно
первой части условий Поша. Ясно, что проверять условия $d_k > k$ легче.

Часть условий Поша: «для нечетного n число вершин степени
$frac{1}{2}(n – 1)$ не превосходит $frac{1}{2}(n – 1)$», назовем второй частью условий
Поша. Положив $frac{1}{2}(n – 1) = m$, эти условия можно записать следующим
образом; из $d_{r + 1} = d_{r + 2} = … = d_{r + j} = m$, $d_r m – 1$ или $d_{m – 1} ge m$. Значит, мы можем
уточнить пределы изменения r: $0 le r le m – 1$.

Ясно, что условия Дирака, следуют из условий Поша, когда число вершин,
упоминаемое в первой и второй частях последних условий равно 0.

Для доказательства, что из условий Поша, следуют условия Оре, требуются
более тонкие рассуждения либо рассмотрение доказательства самой теоремы
Поша. Мы не будем рассматривать доказательство теоремы Поша, а рассмотрим
более общие условия, для которых условия Поша являются частным случаем.

Теорема Хватала (1972 год). Обыкновенный граф $Gamma (V,R)$,
порядка $n$ имеющий степенную последовательность $d_1 le d_2 le … le d_n$
является гамильтоновым, если для всех k, $1 le k

Доказательство. Прежде всего, отметим, что если $d_k le k$, то
(как это отмечалось выше) число вершин, степень которых не превышает $k$,
равно, по крайней мере, $k$. Аналогично если $d_{n – k} ge n – k$, то число
вершин, степень которых не меньше $n – k$, равно, по крайней мере, $k + 1$
(достаточно заметить, что в последовательности $d_{n – k}, d_{n – k + 1}, …, d_n$
имеется $k + 1$ чисел). Для степенной последовательности,
удовлетворяющей условию (*), покажем, что это условие выполняется и для
любой последовательности, мажорируещей данную. Сформулируем это утверждение
в виде леммы и докажем её.

Лемма 2. Если импликация (*) верна для некоторой последовательности
степеней $gamma :d_1 le d_2 le … le d_n$, то она верна и для
неубывающей степенной последовательности ${gamma }’:{d}’_1 le {d}’_2 le … le {d}’_n$,
мажорирующей $gamma$.

Доказательство леммы 2.
Пусть ${d}’_k > k$. Тогда первый аргумент импликации (*) для
последовательности ${gamma }’$ложен, следовательно, импликация верна вне
зависимости от второго аргумента. Значит, в этом случае импликация (*) верна
и для последовательности ${gamma }’$.

Пусть ${d}’_k le k,{d}’_{n – k} ge d_{n – k} ge n – k$. Тогда оба
аргумента импликации истинны. Значит, и в этом случае импликация (*) верна
для последовательности ${gamma }’$. Значит, импликация (*), если она
выполняется для последовательности $gamma $, выполняется и для
последовательности ${gamma }’$. Лемма 2 доказана.

Вернемся к доказательству теоремы и будем доказывать её от противного. Пусть
существует простой негамильтонов граф, последовательность степеней которого
удовлетворяет условию (*). Тогда он является остовным подграфом
обыкновенного максимального негамильтонова графа ${Gamma }'(V,R)$, в
котором последовательность степеней $d_1 le d_2 le … le d_n $ также
удовлетворяет условию (*).

Пусть $u$ и $v$ — две такие несмежные вершины графа $Gamma $, что сумма $d(u) + d(v)$
является наибольшей и $d(u) le d(v)$. Из того, что $Gamma $ —
максимальный негамильтонов граф, следует, что добавление ребра, соединяющего
вершины $u$ и $v$, преобразует граф в гамильтонов.

Таким образом, в графе $Gamma $ существует гамильтонов путь
$u = u_1, u_2, u_3, u_4, …, u_n = v$,
где $u$ и $v$ — конечные вершины (см. рис.1).

Пусть $S = {ivert {u_1, u_{i + 1} } in R}$,
$T = {ivert {u_i, u_n } in R}$.
Пересечение этих двух подмножеств пусто, т.е. $S cap T = emptyset$.
Действительно, если существует $j in S cap T$, то граф
$Gamma $ будет содержать ребра ${u_1, u_{j + 1} }$ и ${u_j, u_n }$,
а тогда циклическая последовательность вершин
$u_j, u_{j – 1}, …, u_1, u_{j + 1}, u_{j + 2}, …, u_n, u_j$
образует в графе $Gamma $ гамильтонов цикл.

Рис. 1.

Так как вершина $u_n = v$ не принадлежит ни $S$, ни $T$, из этого следует, что
$S cup T subseteq {1,2,…,n – 1}$. Поэтому $d(u) + d(v) = left| S
right| + left| T right|

Так как $S cap T = emptyset $, то ни одна вершина $u_j $ с $j in S$ не
смежна с вершиной $v$. Из выбора $d(u)$ и $d(v)$ следует, что для $j in S$
справедливо неравенство $d(u_j ) le d(u)$. Таким образом, существует, по
крайней мере, $left| S right| = d(u)$ вершин, степени которых не превышают
$d(u)$. Поэтому если мы положим $k = d(u)$, то получим $d_k le k d(u) + d(v)$,
что противоречит выбору $d(u)$ и $d(v)$.

Следствия. Обыкновенный граф $Gamma (V,R)$ порядка $n ge 3$ с
последовательностью степеней $d_1

1. $1 le k le n Rightarrow d_k ge frac{1}{2}n$ (условие Дирака),
2. ${u,v} notin R Rightarrow d(u) + d(v) ge n$ (условие Оре),
3. $1 le k k$ («огрубленное» (менее
   жесткое) условие Поша — вторая часть условий Поша (см. выше) заменена требованием $d_m > m)$,
4. $j

Доказательство. Докажем эти следствия, показав, что все они влекут
за собой выполнение условия (*).

$1 Rightarrow 2$ Очевидно, что любая последовательность степеней, удовлетворяющая условию 1, удовлетворяет также условию 2.

$2 Rightarrow 3$. Пусть из условия 2 не следует условие 3. Тогда существует такое $t$,
что $1 le t

Так как $d_t le t$, то любая вершина $v_i $, для $i = 1,2,…,t$ смежна не
более чем с одной вершиной $v_j $ для $j in {t + 1,…,n}$, причем
$left| {{t + 1,…,n}} right| = n – t$. Заметим, что $n – t > t$,
поскольку $t

$3 Rightarrow 4$. Если из условия 3 не следует условия 4, то существует такое $j

$4 Rightarrow (ast)$. Если это неверно, то существует такое $t$,
что $d_t le t

Очевидно, что если какая-либо графовая последовательность $gamma $
удовлетворяет условиям теоремы (условиям (*)) или следствиям из неё, то тем
же условиям удовлетворяет любая графовая последовательность мажорирующая
последовательность $gamma$.

Проиллюстрируем доказательства следствий. Обозначим через $M_i quad (i = 1,2,3,4)$ множества $n$-графов,
удовлетворяющие условиям 1, 2, 3 и 4 соответственно. Обозначим $M_5 $ — множество $n$-графов, удовлетворяющее
условию теоремы Хватала. Тогда соотношение этих множеств можно проиллюстрировать диаграммой на рис. 2.

Рис. 2.

Замечание относительно «чувствительности» достаточных условий
существования гамильтоновых циклов в графе.

Так, ни одно из перечисленных выше достаточных условий не может определить,
что граф $C_n $ (цикл) является гамильтоновым. На рисунке 3 изображен граф
$Gamma $, полученный добавлением ребер в граф $C_8 $, который удовлетворяет
условиям теоремы Хватала и не удовлетворяет ни одному из условий 1, 2, 3 и 4.

Рис. 3.

Степенная последовательность для этого гамильтонова графа:
$2,3,3,4,5,5,5,5$. Она удовлетворяет условиям (*) (сумма 3-го и 5-го членов
последовательности равна $3 + 5 = 8)$. Если в этом графе удалить ребро
${3,7}$, получим граф со степенной последовательностью $2,3,3,4,4,4,5,5$,
которая уже не удовлетворяет условиям (*) (сумма 3-го и 5-го членов
последовательности равна $3 + 4 = 7)$.