Определение

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

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

Необходимые и достаточные условия Гамильтонова графа неизвестны. Известны только некоторые достаточные условия.

Теорема Хватала (В.Хватал, 1972 г.)

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

Теорема Оре (О.Оре, 1960г.)

Если для любой пары и несмежных вершин графа порядка выполняется неравенство , то - гамильтонов граф.

Теорема Дирака (следствие теоремы Оре) (Г. Дирак, 1952 г.)

Если для любой вершины графа порядка выполняется неравенство , то - гамильтонов граф.

Для нахождения Гамильтонова цикла не существует эффективного алгоритма его нахождения.

Если в графе G=(V, E) порядка n фиксировать одну вершину и обход всегда начинать с нее, то всякому Гамильтонову циклу очевидным образом будет соответствовать перестановка элементов множества V. Тем самым, чтобы найти Гамильтонов цикл или убедиться в его отсутствии, нужно произвести (n-1)! перестановок. Если граф G – Гамильтонов, то проделать этот перебор в полном объеме придется только в случае крайнего невезения – когда нужная, то есть соответствующая Гамильтонову циклу перестановка окажется последней в этом процессе. Если же G – не Гамильтонов граф, то чтобы убедится в отсутствии Гамильтонова цикла, придется перебрать все

(n-1)! Перестановоки, то есть задача относится к классу NP.

Как мы уже показали – в природе почти нет эйлеровых графов и эффективный алгоритм отыскания эйлеровых циклов редко оказывается применимым на практике. С другой стороны можно показать, что почти все графы – гамильтоновы, то есть

, где

S(р) – множество всех графов с р вершинами, а Н(р) – множество гамильтоновых графов с р вершинами

Пример

Найдем в графе гамильтонов цикл, пользуясь методом программирования с отходами и деревом решений.

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