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

Граф называется гамильтоновым, если в нём имеется простой цикл, соединяющий каждую вершину графа. Сам цикл также называется гамильтоновым. Гамильтоновой называется и цепь, соединяющая все вершины графа.

В 1859 году известный ирландский математик У. Гамильтон придумал задачу «Кругосветное путешествие». Каждой вершине додекаэдра приписывается название одного города. Задача состоит в том, чтобы, переходя по рёбрам от одной вершины к другой, вернутся в исходную вершину. То есть нужно отыскать в графе простой цикл, содержащий все вершины (рис. 1.29).

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

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

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

Теорема Дирака: Если граф G- связный граф, N  3 и deg(v) N/2 для любой из вершин v, то граф G – гамильтонов. На рис. 1.30 показан граф, гамильтоновым не являющийся.

Наиболее сильная теорема о гамильтоновых графах (У.Татт,1946):

Всякий 4-связный планарный граф является гамильтоновым.

Для точного решения этой задачи можно использовать прямой перебор.