logo search
DM_shpory

33. Алгоритм нахождения эйлерова цикла и его вычислительная сложность.

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

1. Начинаем с любой вершины. Проходим вдоль любого ребра до другой вершины. Запоминаем это ребро как начало цикла и удаляем его из графа.

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

3. Выполняем шаг 2 до тех пор, пока не удалим все рёбра из графа.

Исходные данные: связный граф G = V, E без вершин нечетной степени, представленный списками ЗАПИСЬ [v], v V.

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

begin

CTEK := ; СЕ := ;

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

CTEKv;

while CTEK  do

begin v:= top (CTEK); { v = верхний элемент стека }

if ЗАПИСЬ [v]  then

begin u:= первая вершина списка ЗАПИСЬ [v];

CTEKu;

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

ЗАПИСЬ [v] := ЗАПИСЬ [v] \ {u};

ЗАПИСЬ [u] := ЗАПИСЬ [u] \ {v};

v := u

end

else { ЗАПИСЬ [v] = }

begin v CTEK ; СЕ  v;

end

end

end

Принцип действия этого алгоритма можно объяснить следующим образом: пусть v0 — вершина, выбранная в третьей строке. Цикл начинает строить путь с началом в v0, причем вершины этого пути помещаются в CTEK, а ребра удаляются из графа.

Эти действия продолжаются вплоть до того момента, когда путь нельзя удлинить, включив в него новую вершину, т.е. когда ЗАПИСЬ [v] =.

Отметим, что тогда должно быть v =v0, так как в любом другом случае это означало бы, что степень вершины v нечетная.

Таким образом, из нашего графа был удален цикл, а вершины этого цикла находятся в стеке CTEK.

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

Вершина v =v0 переносится теперь из стека CTEK в стек CE, а «очередной» вершиной v становится верхний элемент стека CTEK.

Процесс повторяется, начиная с этой вершины (если ЗАПИСЬ [v] ), в результате чего вследствие четности степени всех вершин находится и помещается в стек CTEK некоторый цикл, проходящий через вершину v.

Это продолжается до того момента, пока CTEK не станет пустым.

Очевидно, что вершины, помещаемые в стек CE, образуют некоторый путь, причем вершина v переносится в стек CE только тогда, когда ЗАПИСЬ [v] =, т.е. когда все ребра, инцидентные с этой вершиной, представлены (парами соседних вершин) в одном из стеков. Отсюда легко следует, что по окончании алгоритма стек CE содержит эйлеров цикл.

Оценим теперь вычислительную сложность этого алгоритма. Для этого отметим, что каждая итерация главного цикла либо помещает вершину в стек CTEK и удаляет ребро из графа, либо переносит вершину из стека CTEK в стек CE. Таким образом, число итераций этого цикла — О(m). В свою очередь число шагов в каждой итерации ограничено константой. Здесь предполагаем, что каждый из списков инцидентности ЗАПИСЬ [v], v V, реализован таким образом, что каждая вершина в этом списке содержит указатели на предыдущую и последующую вершины, и вершина u в списке ЗАПИСЬ [v] содержит указатель на вершину v в списке ЗАПИСЬ [u]. Это дает возможность устранить ребро {u, v} за время, ограниченное константой. Из приведенных выше рассуждений можно сделать вывод, что общая сложность алгоритма есть О(m). Очевидно, что этот алгоритм оптимальный, так как уже одно выписывание эйлерова цикла требует (m) шагов.