флеров

Aлгоритм построения эйлерова цикла

Граф хранится в виде списка инциденций.

СПИСОК [v] - список вершин графа, смежных с вершиной v.

Метод.

Начинаем строить путь с началом в v, причем вершины этого пути помещаются в стек ПУТЬ, а рёбра удаляются из графа.

Это продолжается до тех пор, пока путь можно удлинить, включив в него новую вершину, т.е. СПИСОК [v] . Это случится только по достижению вершины v. Тем самым из графа удален цикл, а вершины этого цикла находятся в стеке ПУТЬ. Вершина v переносится теперь из списка ПУТЬ в стек ЦИКЛ. Процесс повторяется.

Алгоритм.

begin
CTEK: ПУТЬ ;
СТЕК: ЦИКЛ ;
v := произвольная вершина графа;
ПУТЬ := v; {Инициализация}
while ПУТЬ  do
begin v := ПУТЬ;
if СПИСОК [v] 
then
begin
u := ПЕРВАЯ ВЕРШИНА СПИСКА СПИСОК [v];
ПУТЬ := u;
СПИСОК [v] := СПИСОК [v] \ {u};
СПИСОК [u] := СПИСОК [u] \ {v};
v := u
end
else {СПИСОК [v] = }
begin v:= ПУТЬ ; ЦИКЛ := v end
end
end

Оценим вычислительную сложность алгоритма. Для этого отметим, что каждое повторение главного цикла либо помещает вершину в стек ПУТЬ и удаляет ребро из графа, либо переносит вершину из стека ПУТЬ в стек ЦИКЛ. Таким образом, число итераций этого цикла - О(m), где m - число ребер. В свою очередь число шагов в каждом повторе ограничено константой. Общая сложность алгоритма есть O(m).

Приведем пример построения эйлерова цикла с помощью описанного алгоритма.

Пример.

Пусть граф имеет следующий вид:

Построим списки смежности вершин для указанного графа:

СПИСОК [1] : 2, 3;

СПИСОК [2] : 1, 3, 7, 8;

СПИСОК [3] : 1, 2, 4, 5;

СПИСОК [4] : 3, 5;

СПИСОК [5] : 3, 4, 6, 8;

СПИСОК [6] : 5, 7, 8, 9;

СПИСОК [7] :2, 6, 8, 9;

СПИСОК [8] :2, 5, 6, 7;

СПИСОК [9] : 6,7.

Во время работы алгоритма стеки ПУТЬ и ЦИКЛ имеют следующий вид:

Прямоугольниками в стеке ПУТЬ обрамлены вершины v, при достижении которых СПИСОК [v] = . Такие вершины немедленно помещаются в стек ЦИКЛ. По исчерпании списка всех вершин (в нашем примере при достижении последней вершины 8) вершины из стека ПУТЬ последовательно выталкиваются в стек ЦИКЛ. 

Содержание