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

Пример.

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

Выведем еще два достаточных признака гамильтоновых графов.

Рассмотрим граф $$G$$ с $$m\ge3$$ вершинами. Пронумеруем их произвольным образом и выпишем их последовательность:

При этом может случиться, что некоторые две соседние вершины, например, $$v_{k}$$ и $$v_{k+1}$$, не связаны ребром. Будем говорить, что в данной последовательности имеется "разрыв" между вершинами $$v_{k}$$ и $$v_{k+1}$$.

Очевидно, в последовательности $$v_{1},v_{2}\dts v_{i-1},v_{i}$$ не возникнут другие разрывы, если ее записать в обратном порядке, а именно: $$v_{i},v_{i-1} ,\ldots$$, $$v_{2},v_{1}$$.

Пусть для определенности разрыв в последовательности (5.1) имеет место между вершинами $$v_{0}$$ и $$v_{1}$$. Положим теперь, что $$v_{i}$$ — вершина графа $$G$$, связанная ребром с $$v_{0}$$. Число таких вершин $$v_{i}$$ равно $$\rho(v_{0}).$$

Пытаясь ликвидировать разрыв в последовательности (5.1) между $$v_{0}$$ и $$v_{1}$$, запишем ее в измененном порядке:

При этом число разрывов уменьшится на единицу в том случае, если между вершинами $$v_{1}$$ и $$v_{i+1}$$ не возникнет новый разрыв.

Вершину $$v_{i}$$ среди $$m-1$$ вершин, не совпадающих с $$v_{0}$$, можно всегда найти, так, чтобы между $$v_{1}$$ и $$v_{i+1}$$ не возник новый разрыв, если справедливо неравенство

$$\rho (v_{0} ) \ge (m-1)-\rho (v_{1}) }$$

(справа в этом неравенстве читаем число разрывов, которые могут произойти при всевозможных перестановках последовательности (5.1)).

Но вершины $$v_{0}$$ и $$v_{1}$$ были выбраны произвольно; можно было рассмотреть разрыв между другими соседними вершинами $$v_{k}$$ и $$v_{k+1}$$ в последовательности (5.1), можно было даже выбрать вершины $$v_{u}$$ и $$v_{v}$$ графа $$G$$, не стоящие рядом в последовательности (5.1). Лишь бы соблюдалось неравенство

Заметим, что неравенство (5.3) симметрично относительно $$v_{u}$$ и $$v_{v}$$. Его можно записать в виде

И тогда в последовательности (5.1) удастся ликвидировать все разрывы. А это означает, что в графе $$G$$ найдется гамильтонов путь.

Покажем, что если для любой пары вершин $$v_{u}$$ и $$v_{v}$$ графа $$G$$ с $$m$$ вершинами справедливо неравенство

то граф $$G$$ обладает гамильтоновым циклом. Это один из достаточных признаков того, что данный граф является гамильтоновым.

Рассмотрим гамильтонов путь, связывающий вершины $$v_{u}$$ и $$v_{v}$$ графа $$G$$.

Пример.

Пусть $$x$$ — одна из вершин графа $$G$$, связанная ребром с вершиной $$v_{u}$$. Тогда в силу неравенства (5.5), хотя бы для одной из таких вершин $$x$$ найдется в гамильтоновом пути смежная с ней вершина $$v_{w}$$, такая, которая связана ребром с $$v_{v}$$.

Добавляя к гамильтонову пути ребра $$(v_{u},x), (v_{w},v_{v})$$ и выбрасывая из него ребро $$(v_{w},x)$$, получаем гамильтонов цикл, что и требовалось.

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

Формулируется этот признак так:

Граф $$G$$ с $$m$$ вершинами имеет гамильтонов цикл, если для произвольной его вершины

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

Проведенное доказательство справедливости достаточных признаков гамильтоновых графов было косвенным — мы не строили для данного произвольного графа, удовлетворяющего неравенству (5.5) или неравенству (5.6), гамильтоновых циклов.

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

Поиск необходимого и достаточного условия для того, чтобы граф был гамильтоновым, стал одной из главных нерешенных задач теории графов! О гамильтоновых графах, в сущности, известно очень мало. Большинство известных теорем имеет вид "если граф $$G$$ имеет достаточное число ребер, то граф $$G$$ является гамильтоновым графом". Вероятно, самой знаменитой из этих теорем является следующая теорема, принадлежащая Г.Э.Дираку и потому известная как теорема Дирака.

Теорема (Дирак, 1952) Если в простом графе с $$n\ge 3$$ вершинами $$\rho (v)\ge n/2$$ для любой вершины $$v$$, то граф $$G$$ является гамильтоновым.

Замечание Существует несколько доказательств этой широко известной теоремы, здесь мы приводим доказательство Д.Дж.Ньюмана.

Доказательство Добавим к нашему графу $$k$$ новых вершин, соединяя каждую из них с каждой вершиной из $$G$$. Будем предполагать, что $$k$$ — наименьшее число вершин, необходимых для того, чтобы полученный граф $$G'$$ стал гамильтоновым. Затем, считая, что $$k\succ 0$$, придем к противоречию.

Пусть $$v\to p\to w\to \ldots \to v$$ гамильтонов цикл в графе $$G'$$, где $$v,w$$ — вершины из $$G$$, а $$p$$ — одна из новых вершин. Тогда $$w$$ не является смежной с $$v$$, так как в противном случае мы могли бы не использовать вершину $$p$$, что противоречит минимальности $$k$$. Более того, вершина, скажем, $$w'$$, смежная вершине $$w$$, не может непосредственно следовать за вершиной $$v'$$, смежной вершине $$v$$, потому что тогда мы могли бы заменить $$v\to p\to w\to \ldots \to v' \to w' \to \ldots \to v$$ на $$v\to v' \to \ldots \to w\to w' \to \ldots \to v$$, перевернув часть цикла, заключенную между $$w$$ и $$v'$$. Отсюда следует, что число вершин графа $$G'$$, не являющихся смежными с $$w$$, не меньше числа вершин, смежных с $$v$$ (то есть равно, по меньшей мере, $$n/2+k$$ ); с другой стороны, очевидно, что число вершин графа $$G'$$, смежных с $$w$$, тоже равно, по меньшей мере, $$n/2+k$$. А так как ни одна вершина графа $$G'$$ не может быть одновременно смежной и не смежной вершине $$w$$, то общее число вершин графа $$G'$$, равное $$n+k$$, не меньше, чем $$n+2k$$. Это и есть искомое противоречие.