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

Сэр Вильям Гамильтон, строя простые циклы, содержащие каждую вершину додекаэдра, определил класс графов, носящих теперь его имя. Если в G имеется простой остовный цикл Z, то G называется гамильтоновым графом, а Z -гамильтоновым циклом. В настоящее время не известно эффективных описаний гамильтоновых графов, но известно несколько необходимых и несколько достаточных условий существования гамильтоновых циклов.

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

Теорема. Каждый гамильтонов граф двусвязен. Каждый негамильтонов двусвязный граф содержит тэта-подграф.

Легко найти тэта-подграф в негамильтоновом блоке, приведенном на рисунке

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

Теорема.Пусть G имеет р > 3 вершин. Если для всякого n, 1<n <(р—1)/2, число вершин со степенями, не превосходящими n, меньше чем n, и для нечетного р число вершин степени (р—1)/2 не превосходит (р—1)/2, то G — гамильтонов граф.

Доказательство. Предположим, что теорема неверна, и пусть G — максимальный негамильтонов граф с р вершинами, удовлетворяющий условиям теоремы. Легко видеть, что добавление любого ребра в граф, обладающий указанными в теореме свойствами, приводит к графу, который также обладает этими свойствами. Таким образом, поскольку добавление к G произвольного ребра приводит к гамильтонову графу, любые две несмежные вершины соединимы простой остовной цепью.

Покажем сначала, что всякая вершина, степень которой не меньше (р—1)/2, смежна с каждой вершиной со степенью, большей чем (р—1)/2. Допустим (не теряя общности), что deg v1> (р-1)/2 и deg vp>p/2, но вершины v1 и vp не смежны. Тогда существует простая остовная цепь v1v2. . .vp, соединяющая v1 и vp. Обозначим вершины смежные с v1 через vi1,... ,vin, где n-deg v1 и 2=i1< in Ясно, что вершина vp не может быть смежной ни с одной вершиной из G вида vt-i, поскольку тогда в G был бы гамильтонов цикл

v1v2...vij-ivpvp-1...vijv1

Далее, так как п>(р-1)/2, то р/2<degvp<р-1-n <р/2, что невозможно. Поэтому v1 и vр должны быть смежны.

Отсюда следует, что если degv>p/2 для всех вершин v, то G — гамильтонов граф. (Ниже это сформулировано в виде следствия (б).) В силу изложенного выше каждая пара вершин графа G смежна, т. е. G — полный граф. Мы пришли к противоречию, поскольку Кр — гамильтонов граф для всех р>3.

Таким образом, в G есть вершина v с degv<p/2. Обозначим через m наибольшую среди степеней всех таких вершин. Выберем такую вершину, что degv1=m. По принятому предположению число вершин со степенями, не превосходящими,tне больше чем m<ip/2, поэтому должно быть более чемtвершин со степенями, превосходящимиt, и, следовательно, не меньшими чем р/2. В результате найдется некоторая вершина, скажем vp, степени по крайней мере р/2, не смежная с Vi. Так какvuи vp не смежны, то существует остовная простая цепь v1

,...vp. Как и выше, обозначим через vi,. . ., vim вершины графа G, смежные с v1 и заметим, что вершина vр не может быть смежной ни с одной из т вершин vij —1 для 1< j<m. Но поскольку v1 и vp не смежны, a vp имеет степень не меньше р/2, то, как было показано в первой части доказательства,tдолжно быть меньше чем (р—1)/2. Так как по предположению число вершин со степенями, не превосходящимиt, меньше чемt, то хотя бы одна изtвершин uij-1, скажемv', должна иметь степень не меньше р/2. Итак, мы установили, что степени двух несмежных вершин vp и v' не меньше р/2. Полученное противоречие завершает доказательство теоремы.

Приведенное достаточное условие не является необходимым. Кубический граф G1 изображенный на рисунке, гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы. Однако условия теоремы неулучшаемы, поскольку при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа. Например, выберем р>3 и 1 < n< (р—1)/2 и образуем граф G2 с одной точкой сочленения и двумя блоками Kn+1 и Кp-nЭтот граф не гамильтонов; для него нарушается только одно условие теоремы: граф G2 содержит точноnвершин степени п. Это иллюстрируется на рисунке где р=8 и п=3. Если выбрать р=2n+1,

n> 1 и образовать граф G = Kn, n+1> то он не будет гамильтоновым; для него нарушается только одно условие теоремы: в нем (р—1)/2+1 вершин имеют степень (р—1)/2. Граф G3 = K2,3, приведенный на рисунке, иллюстрирует это для случая р=5.

Ограничивая условия теоремы Поша, получаем более простые, но менее сильные достаточные условия, найденные Оре и Дираком соответственно:

Следствие(а).Если р>3 и degu + degv> р для любой пары u и v несмежных вершин графа G, то G — гамильтонов граф.

Следствие(6).Если р>3 и deg v> р/2 для любой вершины v графа G, то G — гамильтонов граф.

Кубический гамильтонов граф G1 показанный на рисунке, имеет четыре остовных простых цикла. Наименьший кубический гамильтонов граф К4 имеет три остовных простых цикла. Эти замечания иллюстрируют теорему Смита

Теорема.В каждом кубическом гамильтоновом графе существует по крайней мере три остовных простых цикла.

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

Наименьший известный в настоящее время негамильтонов трехсвязный плоский граф, имеющий 38 вершин, был построен независимо Ледербергом, Босаком и Барнеттом; эти результаты можно найти в монографии Грюнбаума .

Кажущееся отсутствие взаимосвязи между эйлеровыми и гамильтоновыми графами иллюстрируется рис; здесь каждый

граф - это блок с 8 вершинами. Однако в следующей главе мы свяжем эйлеровы и гамильтоновы графы с помощью так называемых «реберных графов».

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