Некоторые свойства гамильтоновых графов

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

Теорема 9. Пусть элементарный связный граф имеет п вершин и п>3. Если в этом графе для степени любой вершины, А выполняется неравенство <7 (А)> —, то он обладает гамильтоновым циклом.

Доказательство. К графу G добавим к новых вершин и каждую из них соединим с каждой вершиной графа G. Получим новый граф G'. Ясно, что если выбрать к достаточно большим, то граф G' будет гамильтоновым. Предположим теперь, что к — минимальное из чисел, при котором в графе G' появляется гамильтонов цикл. Наша цель состоит в том, чтобы доказать, что к=0. Предположим противное, что к>0, и пусть Р — одна из добавленных вершин. Рассмотрим гамильтонов цикл в графе G' (он существует по предположению и содержит точку Р).

Рядом с вершиной Р могут находиться только вершины из графа G, обозначим их через А и В.

Вершины А и В не могут быть смежны, так как в противном случае мы могли бы не использовать вершину Р, а это противоречит предположению о минимальности к. Так как по условию теоремы степень каждой вершины А больше 1, то в гамильтоновом цикле найдется вершина А' из G, смежная А. Обозначим через С вершину, непосредственно следующую за А'.

Докажем, что вершины В и С не смежны. Действительно, если предположить противное, то наряду с рассматриваемым гамильтоновым циклом будет существовать еще один гамильтонов цикл,.

в котором участок от В до А'обращен в противоположное направление и не участвует точка Р. Т. е. мы опять приходим в противоречие с предположением о минимальности к.

Итак, за точкой А', смежной вершине А, непосредственно следует вершина С, обязательно не смежная вершине В. Т. е. в графе G' число вершин, не смежных В, не меньше числа вершин, смежных А.

Следовательно, число вершин в G', не смежных В, равно по п, ^.

меньшей мере — + к . С другой стороны, число вершин в.

G', смежных В, тоже равно, по меньшей мере, ^-+ к . А так как одна и та же вершина не может быть одновременно смежной и не смежной вершине В, то общее число вершин графа G' не меньше п + 2к . Но граф G' имеет всего п + к вершин. Из равенства п + 2к = п + к следует противоречие с предположением о том, что к>0. Итак к=0, и граф G обладает гамильтоновым циклом. Теорема доказана.

Следствие. Пусть элементарный связный граф имеет п вершин и п>3. Если в этом графе для любой пары вершин, А и В выполняется неравенство а (А) + а (В)>п, то он обладает гамильтоновым циклом.

Теорема 10. Если при п>3 элементарный связный граф имеет п вершин и для любой его пары вершин, А и В выполняется неравенство С (А) + О (В) >п-, то он обладает гамильтоновой цепью.

Доказательство. Добавим вершину Р к графу G и соединим ее ребрами со всеми другими вершинами. В результате получим граф G', имеющий п +1 вершину. Степени вершин (всех, кроме вершины Р) увеличились на 1, поэтому для любых двух вершин А и В

(отличных от Р) справедливо неравенство гг (А) + а (В) >(и-1) + 1 + 1 = и + 1. С другой стороны, о{Р) = п, а о (А)> для любой вершины А. Следовательно (У (А) + сг (Р) > п + 1. Итак для любой пары вершин А и В графа G' имеет место неравенство О (А) + а (В) > и + 1. Поэтому, в силу следствия из теоремы 9, граф G' обладает гамильтоновым циклом.

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

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

Из теоремы 9 следует, что любой полный граф является гамильтоновым. Если занумеровать вершины полного графа с п вершинами числами от 1 до л, то любая перестановка чисел 1, 2, …, п определяет искомую последовательность вершин в гамильтоновой цепи. Добавляя к этой цепи ребро между первой и последней вершиной (при п>3), получим гамильтонов цикл.