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

Задача нахождения стягивающего дерева тесно связана с задачей построения фундаментального множества циклов. Если к стягивающему дереву графа добавить произвольную хорду , то возникший при этом подграф содержит в точности один цикл, обозначаемый C_e. Очевидно, что C_e содержит ребро е. Множество - фундаментальное множество циклов графа G (относительно стягивающего дерева ).

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

Алгоритм нахождения множества фундаментальных циклов основывается на поиске в глубину и имеет структуру, аналогичную алгоритму WGD. Каждая новая вершина, встречающаяся в процессе поиска, помещается в стек и удаляется из стека после использования. Очевидно, что стек всегда содержит последовательность вершин от рассматриваемой в данный момент вершины v до корня. Поэтому же, если анализировать ребро {v,u} замыкает цикл (то есть, для отдельных элементов массива WGN соблюдаются условия WGN[v] > WGN[u] > 0 и u не находится непосредственно под верхним элементом стека), то вершина u находится в стеке и цикл, замыкаемый ребром {v,u} представлен верхней группой элементов, начиная с v и кончая u.

Cycle = proc (v,d,num:int; g:graph; STACK, WGN:array of int)

modifies d,num,T,WGN

effects 1. d = d + 1; STACK[d] = v; num = num + 1; WGN[v] = num

2. c = graph.fetch(g,v); i = circ.size(c)

3. пока i > 0

3.1. u = circ.element(c)

3.2. если (WGN[u] = 0), то Cycle(u,d,num,g,STACK,WGN),

иначе

если ((u <> STACK[d-1]) и (WGN[v] > WGN[u]), то

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

STACK[d], STACK[d-1], . . . , STACK[c], где STACK[c] = u

3.3. circ.change(c)

3.4. i = i – 1

4. d = d - 1

Рис.1.19.Процедура нахождения фундаментального множества циклов для компонента связности, содержащего вершину v.

Fcycle = proc (g:graph)

effects 1. для i = 1 до n WGN[i] = 0

2. num = 0; d = 0; STACK[0] = 0

3. для i = 1 до n выполнить

если (WGN[i] = 0), то Cycle(i,d,num,STACK,WGN)

Рис.1.20.Процедура нахождения множества элементарных циклов графа.

1.6.Нахождение компонент двусвязности

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

Двусвязность графа – очень желательный признак для некоторых приложений. Пусть вершины графа изображают узлы некоторой информационной сети, а ребра соответствуют линиям передач. Если этот граф двусвязный, то выход из строя отдельного узла w не приведет к потере соединения между любыми двумя узлами, отличными от w. Знание блоков графа также важно, так как многие графовые задачи (нахождение всех элементарных циклов, установление факта планарности графа) приводят естественным путем к аналогичным задачам для блоков данного графа. На рис.1.21 приводится пример графа, имеющего точки сочленения и блоки.

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

Идея алгоритма следующая. Начиная с некоторой вершины r, осуществляется поиск в глубину в графе с вычисляемыми для каждой вершины v двух параметров: WGN[v] и L[v]. Первый – номер вершины v в порядке, в котором вершины посещаются при поиске в глубину, начиная с вершины r. Если через обозначить дерево, соответствующее этому поиску в глубину, то другой параметр определяет наименьшее значение WGN[u], где u = v или вершина u связана хордой с вершиной v или ее произвольным потомком в D. Параметр L[v] вычисляется индуктивно относительно дерева D, если известны L[w] для всех сыновей w вершины v. Обозначив

получим

Вершина v является точкой сочленения или корнем тогда и только тогда, когда для некоторого сына u вершины v.

BL = proc (v,p,num: int; g: graph; WGN,L: array of int; T: stack)

modifies num,WGN,L,T

effects 1. num = num + 1; WGN[v] = num; L[v] = WGN[v]

2. c = graph.fetch(g,v); i = circ.size(c)

3. пока i > 0

3.1. u = circ.element(c)

3.2. если (WGN[u] = 0), то

3.2.1. stack.pop(T,v)

3.2.2. stack.pop(T,u)

3.2.3. BL(u,v,num,g,WGN,T)

3.2.4. L[v] = min(L[v], L[u])

3.2.5. если L[u] >= WGN[v], то stack.pop(T,0) /* установление границы

иначе

3.2.6. если ((u < > p) и (WGN[v] < WGN[u])), то

3.2.6.1. stack.pop(T,v)

3.2.6.2. stack.pop(T,u)

3.2.6.3. L[v] = min (L[v], WGN[u])

3.3. circ.change(c)

3.4. i = i - 1

Рис.1.22.Процедура нахождения компонент двусвязности, начиная с вершины v.

Main = proc (g: graph) returns (T: stack)

effects 1. для i = 1 до n WGN[i] = 0

2. T = stack.new( ); num = 0

3. для u = 1 до n

если (WGN[u] = 0), то BL(u,0,num,g,WGN,T)

Рис.1.23.Головная процедура нахождения компонент двусвязности графа.