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

Если граф имеет простой цикл, содержащий все вершины графа (по одному ра­зу), то такой цикл называется гамилътоновым циклом, а граф называется гамилъ-тоновым графом.

Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамиль-тоновым может быть только связный граф.

ЗАМЕЧАНИЕ -

Любой граф G можно превратить в гамильтонов, добавив достаточное количество вер­шин. Для этого, например, достаточно к вершинам vi,..., v_p графа G добавить вершины ui,...,u_p и множество ребер {(vi,Ui)} U {(ui,v_i+i)}.

р/2, то граф G является

ТЕОРЕМА (Дирак) Если в графе G(V, E) Vw б V d(v) гамилътоновым.

доказательство

От противного. Пусть G — не гамильтонов. Добавим к G минимальное количе­ство новых вершин i^fi,...,u_n, соединяя их со всеми вершинами G так, чтобы G' : = G + hi + • • • + и_п был гамильтоновым.

Пусть v,ui,w,...,v — гамильтонов цикл в графе G' ', причем г; е G, hi e G' , mi ^ G. Такая пара вершин v и mi в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда w 6 G, w g {ui,...,u_n}, иначе вершина и_г была бы не нужна. Более того; вершина v несмежна с вершиной w, иначе вершина Uj была бы не нужна.

Далее, если в цикле v, ui, го, . . . , v', w', . . . , v есть вершина w', смежная с вершиной w, то вершина v' несмежна с вершиной v, так как иначе можно было бы постро­ить гамильтонов цикл v,v',...,w,w'...v без вершины и\, взяв последователь­ность вершин w,...,v' в обратном порядке. Отсюда следует, что число вершин графа G', не смежных с v, не менее числа вершин, смежных с w. Но для любой вершины w графа G d(w) > р/2 + п по построению, в том числе d(v) ^ р/2 + п. Общее число вершин (смежных и не смежных с v) составляет п + р — 1. Таким образом, имеем:

Следовательно, 0 ^ п + 1, что противоречит тому, что п> 0.