5.3. Поиск эйлерова цикла

Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз, т.е. путь v₁, ..., v_m+1 такой, что каждое ребро е  Е появляется в последовательности v₁, ..., v_m+1 в точности один раз. Если v₁ = v_m+1, то такой путь называется эйлеровым циклом. Задача существования эйлерова пути в заданном графе была решена Эйлером в 1736 г., и представленное им необходимое и достаточное условие существования такого пути (см. теорему 5.2) считается первой в истории теоремой теории графов.

Теорема 5.2. Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечетной степени.

Алгоритм 5.2. Нахождение эйлерова цикла.

Исходные данные: Связный граф G=V, E без вершин нечетной степени, представленный соответствиями  [v], v  V.

Результаты: Эйлеров цикл , представленный в стеке ste.

begin stack := ; ste := ;

v := произвольная вершина графа; stack  v;

while stack   do begin v := top(stack); (* v – верхний элемент стека*)

if  [v]   then begin u:= первая вершина из  [v]; stack  u;

(*удалить ребро {v, u} из графа:*)

 [v]:=  [v] \ {u};

 [u]:=  [u] \ {v};

v := u

end

else begin

v  stack; ste  v

end

end.

Принципы действия алгоритма можно объяснить следующим образом: пусть v₀ - выбранная произвольная вершина. Главный цикл начинает строить путь из вершин четной степени с началом в v_0, причем вершины этого пути печатаются, а ребра удаляются из графа. Эти действия продолжаются вплоть до того момента, когда путь нельзя удлинить, включив в него новую вершину, т.е. когда  [v] = . Отметим, что тогда должно быть v=v₀, так как в любом другом случае это означало бы, что степень вершины v нечетная. Таким образом, из нашего графа был удален цикл, а вершины этого цикла напечатаны.

Поскольку каждая итерация главного цикла удаляет в точности одно ребро графа, то вычислительная сложность нашего алгоритма равна числу итераций этого цикла O(m). В свою очередь число шагов в каждой итерации ограничено константой.

На рис. 5.1 представлен граф и некоторый эйлеров цикл, найденный алгоритмом 5.2.

Рис. 5.1. Граф и эйлеров цикл в этом графе (1, 2, 3, 4, 5, 6, 7, 2, 8, 6, 9, 7, 8, 5, 3, 1), найденный с помощью алгоритма 5.2

5.4. Поиск гамильтонова цикла

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

Очевидный алгоритм, который мы можем применить, это “полный перебор всех возможностей”: генерируем все n! различных последовательностей вершин и для каждой из них проверяем, определяет ли она гамильтонов путь. Применим теперь алгоритм с возвратом (см. разд. 3.4) для нахождения гамильтонова цикла в графе G = V, Е. Каждый такой цикл можно представить последовательностью v₁, v₂, ..., v_n+1, причем v₁ = v_n+1 = v₀, где v₀ - некоторая фиксированная вершина графа, а соседние вершины смежны.

Алгоритм 5.3. Нахождение всех гамильтоновых циклов в графе.

Исходные данные: Граф G = V, Е, представленный соответствиями  [v], vV.

Результаты: Список всех гамильтоновых циклов графа G.

procedure ГАМИЛЬТ (k);

(*генерирование всех гамильтоновых циклов, являющихся расширением последовательности (v [1], ..., v [k- 1]); массив dop - глобальный *)

begin

for у  [v [k-1] ] do begin

if (k = n + 1) and (у = v₀) then напечатать (v [1], ..., v [n], v₀)

else

if dop [у] then begin

v [k]:=у; dop [у]:= ложь;

ГАМИЛЬТ (k + 1);

end

dop [у]:= истина

end

end; (* ГАМИЛЬТ *)

begin (* главная программа *)

for vV do dop [v]:= истина; (* инициализация*)

v [1]:= v₀; (v₀ = произвольная фиксированная вершина графа *)

dop [v₀]:= ложь;

ГАМИЛЬТ (2)

end.

Работу этого алгоритма, так же как и произвольного алгоритма с возвратом, можно проиллюстрировать процессом поиска в некотором дереве перебора. Каждая вершина дерева естественным образом соответствует некоторой последовательности v₁, ..., v_k. Это дерево отображает перебор всех возможностей. Для алгоритма 5.3 это иллюстрируется рис. 5.2.

Рис. 5.2. Граф и дерево, иллюстрирующие алгоритм с возвратом нахождения всех гамильтоновых циклов в этом графе.

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