Лекции_по_ДМ

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

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

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

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

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

(Дирака) Если в простом графе с n вершинами (n3) степень любой вершины больше, либо равна n/2, то граф является гамильтоновым.
Если в простом графе с n вершинами (n3) для любой пары несмежных вершин v_i, v_j выполняется условие deg(v_i)+deg(v_j)n, то граф является гамильтоновым. (Если deg(v_i)+deg(v_j)n‑1, то граф – полугамильтонов.)

Классическим примером задачи поиска гамильтоновых циклов является известная задача о коммивояжере (странствующем торговце). Коммивояжеру необходимо посетить несколько городов, расстояния между которыми известны. Нужно найти кратчайшую дорогу, проходящую через все пункты и возвращающуюся в исходный пункт. Здесь каждому городу сопоставим вершину графа, дороге между городами – ребро. Ребру приписываем заданное расстояние, которое, очевидно, можно рассматривать как функцию двух вершин f(v_i,v_j). Если вершины v_i,v_j несмежны, то f(v_i,v_j)=. Таким образом, длина гамильтонова цикла L=. Найти цикл, для которого L минимальна. Не известно до сих пор никакого эффективного алгоритма для решения этой задачи. Для конечного случая её можно решить простым перебором. Отметим, что для полного графа на n вершинах существует гамильтоновых циклов, т.е. сложность задачи очень быстро возрастает с ростом числа вершин.

Содержание