8.5 Отыскание фундаментального множества циклов в графе

Если к стягивающему дереву <V, T> графа G = <V, E> мы добавим произвольную хорду e∈E\T, то воз­никший при этом подграф C = <V, T∪{e}> содержит в точности один цикл (под циклом мы здесь будем пони­мать элементарный цикл). Обозначим этот цикл через C_e. Множество C = {C_e : e∈E \ T} называют фундамен­тальным множеством циклов графа G (относительно стягивающего дерева <V, T>). Название "фундаменталь­ное" связано с тем, что каждый цикл графа G можно достаточно просто получить из циклов множества G.

Нахождение фундаментального множества циклов имеет прикладное значение, например, при анализе электрических цепей. А именно, каждому фундаментальному циклу в графе, соответствующему данной элек­трической цепи, мы можем поставить в соответствие закон Кирхгофа для напряжений: сумма падения напря-

жений вдоль цикла равна 0. Нахождение фундаментального множества циклов позволяет выделить в математи­ческом описании цепи независимые уравнения.

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

Каждая новая вершина, встречающаяся в процессе поиска, помещается в стек, представленный таблицей СТЕК, и удаляется из стека после использования. Очевидно, что стек всегда содержит последовательность вершин от рассматриваемой в данный момент вершины v к корню.

Поэтому, если анализируемое нами ребро {v, и} замыкает цикл (т.е. WGN[v] > WGN[u] > 0 b и не нахо­дится непосредственно под верхним элементом стека), то вершина и находится в стеке и цикл, замыкаемый ребром {v, и}, представлен группой элементов стека, начиная с v и кончая вершиной и.

1 PROCEDURE цикл(у);

{переменные d, пит, СТЕК, СПИСОК, WGN - глобальные}

2 BEGIN d := d+1; СТЕК[d] := v; пит := num+1; WGN[ ] := пит;

3 FOR иеСПИСОК[у] DO

4. IF WGN[u] = 0 THEN цикл(г)

5. ELSE IF (и Ф СТЕК[d-l]) and (WGN[v] > WGN[u])

THEN {ребро {v, и} замыкает новый цикл}

6. выписать цикл с вершинами

7. СТЕК[d], СТЕК[d-l], ..., СТЕК[с], где СТЕК[с] = и

8 d := d-1 {использованная вершина v удаляется из стека}

9 END (цикл}; Основная программа:

1 BEGIN

2. FOR veV DO WGN[r] := 0; num := 0; {инициализация}

3. d := 0; СТЕК[0] := 0; {d - число элементов в стеке}

4. FOR reV DO

5 IF WGN[r] = 0 THEN цикл(у)

6 END.

Оценим вычислительную сложность алгоритма. Отметим, что общее число шагов, не считая вычисления циклов, как и во всех алгоритмах, основанных на поиске в глубину, имеет порядок 0(n+m). К этому следует добавить суммарную длину всех циклов. Эта длина не превосходит (m-n+1), что дает общую сложность алго­ритма 0(шп+п) (или O(nm), если отбросить вырожденный случай т=0).

8.6 Эйлеровы пути в графе

Эйлеров путь в графе - произвольный путь, проходящий через каждое ребро графа ровно один раз, т.е. та­кой путь Vj,..., V_m+\, что каждое ребро ееЕ появляется один раз как \Vj,V-₊j} для некоторого i. Если

Vj = V_m+\, то такой путь называется эйлеровым циклом.

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

Если в графе нет вершин нечетной степени, то каждый эйлеров путь является эйлеровым циклом.

Пусть G = <V, Е> - связный граф, представленный списками СПИСОК[г], ve V. Алгоритм нахождения эй­лерова цикла в графе построим следующим образом. Используем два стека: СТЕК1 и СТЕК2.

Выбираем произвольную вершину графа Vq и строим последовательно путь из этой вершины. Вершины

этого пути помещаем в СТЕК1, а ребра удаляем из графа. Эти действия продолжаем до тех пор, пока оказыва­ется, что путь удлинить, включив в него новую вершину, уже нельзя. Т.е. СПИСОК[у] = 0. Отметим, что тогда должно быть V = Vq , иначе это бы означало, что вершина v - нечетной степени. Таким образом из нашего гра­фа был удален цикл, а вершины этого цикла находятся в стеке СТЕК1. При этом в графе, модифицированном таким образом, степень произвольной вершины остается четной. Вершина V = v₀ переносится теперь из стека

СТЕК1 в стек СТЕК2, а процесс повторяется, начиная с вершины, верхней в СТЕК1 (если ее список не пустой). Теперь снова в СТЕК1 помещается некоторый цикл, проходящий через эту вершину, и т.д. Процесс продолжа­ется до тех пор, пока СТЕК1 не станет пустым.

Очевидно, что вершины, помещенные в СТЕК2, образуют некоторый путь, причем вершина v переносится в СТЕК2 только тогда, когда СПИСОК[у] = 0, т.е. когда все ребра, инцидентные этой вершине, представлены в СТЕКеl (парами соседних вершин). Отсюда следует, что по окончании алгоритма СТЕК2 содержит эйлеров цикл.

Алгоритм:

1. BEGIN

2. СТЕК1 := 0; СТЕК2 := 0;

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

4. СТЕК1 <= v;

5. WHILE СТЕК1 /0DO BEGIN

6. v := top(СТЕКl); {v - верхний элемент СТЕК1}

7. IF СПИСОКу] Ф 0

8. THEN BEGIN

9. u := первую вершину списка СПИСОК[у];

10. СТЕК1 <= u;

11. СПИСОК^] := СПИСОК^] \ { u }; {удалить ребро}

12. СПИСОКи] := СПИСОКи] \ { v }; {{ v, и } из графа}

13. v :=и;

14. END

15. ELSE { СПИСОКу] = 0}

16. BEGIN

17. v <= СТЕКl;

18. СТЕК2 <= v;

19 END

20. END

21. END

Мы предполагаем здесь, что каждый из списков инцидентности СПИСОКу], veV, реализован таким об­разом, что каждая вершина в этом списке содержит указатели на предыдущую и последующую вершины, а вершина и в списке СПИСОКу] содержит указатель на вершину v в списке СПИСОКи]. Это дает возможность удалить ребро {v, и} за число шагов, ограниченное константой. Тогда можно оценить вычислительную слож­ность алгоритма следующим образом.

Каждая итерация главного цикла (строка 5) либо помещает вершину в СТЕК1 и удаляет ребро из графа, либо переносит вершину из СТЕК1 в СТЕК2. Т.е. число итераций этого цикла О(т). Число же шагов в каждой итерации ограничено константой. Поэтому можно считать, что общая сложность алгоритма О(т). Алгоритм считается оптимальным. Пример.

1

4

7

Эйлеров цикл, найденный с помощью нашего алгоритма: 1, 2, 3, 4, 5, 6, 7, 2, 8, 6, 9, 7, 8, 5, 3, 1

9