АЛГОРИТМЫПОИСКА ЦИКЛОВ В ГРАФЕ
Понятие о фундаментальных циклах
Задача построения фундаментального множества циклов тесно связана с нахождением стягивающего дерева. Теперь добавим к стягивающему дереву á V, Т ñ графа G = á V, E ñ произвольную хорду e Î Е \ Т. Тогда отметим, что возникший при этом суграф á V, Т È { e }ñ содержит в точности один цикл. Будем обозначать этот цикл через Ce. Очевидно, что Ce содержит ребро е. Множество P = { Ce | е Î Е \ Т } будем называть фундаментальным множеством циклов графа G относительно стягивающего дерева á V, Т ñ. Название “фундаментальный” связано с тем фактом, что, каждый цикл графа G можно некоторым естественным способом получить из циклов множества P.
Опишем теперь простой алгоритм нахождения множества фундаментальных циклов. Этот алгоритм основывается на поиске в глубину и имеет структуру, аналогичную рекурсивному алгоритму нахождения стягивающего дерева (алгоритм 4.1).
Каждая новая вершина, встречающаяся в процессе поиска, помещается в стек, представленный таблицей СТЕК, и удаляется из стека после использования. Очевидно, что стек всегда содержит последовательность вершин от рассматриваемой в данный момент вершины v до корня. Для построения дерева выбирается еще не посещенная смежная с v вершина. А уже посещенная и смежная с v вершина u дает нам хорду. Но она находится уже в стеке и, по определению, замыкает цикл. Тогда цикл, замыкаемый ребром { v, u }, представлен верхней группой элементов стека, начиная с v и кончая вершиной u. В этом и заключается идея поиска всех фундаментальных циклов, реализованная в следующем алгоритме.
Алгоритм 5.1. Нахождение множества элементарных циклов графа.
Исходные данные: Граф G= á V, Е ñ, представленный соответствиями G [ v ], v Î V.
Результаты: Множество фундаментальных циклов графа G
procedure ЦИКЛ (v);
(*нахождение фундаментального множества циклов для компонент связности, содержащей вершину v; переменные d, num, СТЕК, G, wgn – глобальные*)
Begin
d:= d + 1; СТЕК [ d ]:= v; num:= num + 1;
wgn [ v ]:= num;
for u Î G [ v ] do
if wgn [ u ] = 0 then ЦИКЛ (u)
Else
if (u ¹ СТЕК [ d - 1]) and (wgn [ v ] > wgn [ u ]) then
(* { v, u } замыкает новый цикл *)
(* Выписать цикл с вершинами: *)
writeln(СТЕК [ d ], СТЕК [ d - 1],..., СТЕК [ с ]) (*, где СТЕК [ с ] = u *);
d: = d - 1 (* использованная вершина v удаляется из стека (после окончания цикла for)*)
end; (* ЦИКЛ *)
begin (*главная программа*)
for v Î V do wgn [ v ]:=0; num:= 0; (* инициализация *)
d:= 0; СТЕК [0]:= 0; (* d = число элементов в стеке*)
for v Î V do
if wgn [ v ] =0 then ЦИКЛ (v)
End.
Оценим теперь вычислительную сложность этого алгоритма. Отметим сначала, что общее число шагов, не считая затрат на выписывание циклов как и во всех алгоритмах, основанных на поиске в глубину, имеет порядок O (n + m). К этому следует прибавить суммарную длину всех циклов. Эта длина не превосходит (m - n+ 1) n, что дает общую сложность алгоритма O (nm + n).
Определение всех циклов в графе
Введем для произвольных множеств A и B операцию
А Å В = (А È В)\(А Ç В).
Множество A Å B будем называть симметрической разностью множеств A и В.
Приведем без доказательства следующую важную теорему о фундаментальном множестве циклов.
Теорема 5.1. Пусть G = á V, Е ñ - связный неориентированный граф и á V, Т ñ - его стягивающее дерево. Произвольный цикл графа G можно однозначно представить как симметрическую разность некоторого числа фундаментальных циклов.
Эта теорема дает нам простой алгоритм поиска всех циклов в графе. Для этого необходимо перебрать все возможные сочетания фундаментальных циклов, имеющих хотя бы одно общее ребро. Четное количество общих ребер дает пустое ребро, а нечетное - сохраняет это ребро в результате операции. В полученном результате следует разделить так называемые “ псевдоциклы ”, состоящие из нескольких простых циклов соединенных общей вершиной и исключить повторяющиеся циклы.
Поиск эйлерова цикла
Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз, т.е. путь v1,..., vm+1 такой, что каждое ребро е Î Е появляется в последовательности v1,..., vm+1 в точности один раз. Если v1 = vm+1, то такой путь называется эйлеровым циклом. Задача существования эйлерова пути в заданном графе была решена Эйлером в 1736 г., и представленное им необходимое и достаточное условие существования такого пути (см. теорему 5.2) считается первой в истории теоремой теории графов.
Теорема 5.2. Эйлеров путь в графе существует тогда и только то гда, когда граф связный и содержит не более чем две вершины нечетной степени.
Алгоритм 5.2. Нахождение эйлерова цикла.
Исходные данные: Связный граф G= á V, E ñбез вершин нечетной степени, представленный соответствиями G [ v ], v Î V.
Результаты: Эйлеров цикл, представленный в стеке ste.
begin stack:= Æ; ste:= Æ;
v:= произвольная вершина графа; stack Ü v;
while stack ¹ Æ do begin v:= top (stack); (* v – верхний элемент стека*)
if G [ v ] ¹ Æ then begin u:= первая вершина из G [ v ]; stack Ü u;
(*удалить ребро { v, u } из графа:*)
G [ v ]:= G [ v ] \ { u };
G [ u ]:= G [ u ] \ { v };
v:= u
End
Else begin
v Ü stack; ste Ü v
end
End.
Принципы действия алгоритма можно объяснить следующим образом: пусть v0 - выбранная произвольная вершина. Главный цикл начинает строить путь из вершин четной степени с началом в v0 , причем вершины этого пути печатаются, а ребра удаляются из графа. Эти действия продолжаются вплоть до того момента, когда путь нельзя удлинить, включив в него новую вершину, т.е. когда G [ v ] = Æ. Отметим, что тогда должно быть v=v0, так как в любом другом случае это означало бы, что степень вершины 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