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

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

Введем для произвольных множеств А и В операцию

Множество А В будем называть симметрической разностыо множеств А и В.

Отметим, что симметрическая разность множеств А₁,..., A_к содержит независимо от расстановки скобок в точности те элементы, которые появляются в нечетном числе множеств A_i. Действительно, это нетрудно доказать индукцией по к. Для k = 1 и к = 2 это, очевидно, так. Для к > 2 наша симметрическая разность имеет вид А В, где А является симметрической разностью множеств А₁,.....,А_p и В - симметрической разностью множеств А_p+1,...,А_p+q, где p, q < к и р + q = к. Множество АВ содержит в точности те элементы, которые появляются только в одном из множеств А или В. Пользуясь индуктивным предположением, сделаем вывод, что А В является множеством тех элементов, которые появляются в нечетном числе множеств из A₁,.....,А_р и в четном числе из A_p+1,...,A_p+q, или же в нечетном числе множеств из A_p+1,..,A_p+q и в четном числе множеств из A₁,...,A_p. А это в точности множество тех элементов, которые появляются в нечетном числе множеств из A₁,...,A_k.

Из доказанного выше свойства следует что мы можем опустить скобки в симметрической разности произвольного числа множеств и писать А₁ А₂ ... А_к. Множество С ребер графа называется псевдоциклом, если каждая вершина графа (V, С) имеет четную степень. Примером псевдоцикла является пустое множество и произвольный цикл графа.

Лемма 2.7. Симметрическая разность произвольного числа псевдоциклов является псевдоциклом.

Доказательство. Очевидно, что достаточно рассмотреть случай двух псевдоциклов C₁ и С₂. Обозначим для произвольной вершины v через S₁(v) и S₂(v) множество ребер соответственно из С₁ и С₂ инцидентных с v. Множества S₁(v) и S₂(v) имеют четную мощность, четной является также мощность множества ребер из С₁ С₂, инцидентных с v, так как |S₁(v) S₂(v)| = |S₁(v)| + |S₂(v)| -2|S₁(v)∩S₂(v)|

Теперь мы можем доказать теорему о фундаментальном множестве циклов.

Теорема 2.8. Пусть G = (V,E) — связный неориентированный граф, а (V. Т) — его стягивающее дерево. Произвольный цикл графа G можно однозначно представить как симметрическую разность некоторого числа фундаментальных циклов. В общем случае произвольный псевдоцикл С графа G можно однозначно выразить как

Доказательство. Симметрическая разность (2.1), являющаяся псевдоциклом в силу предыдущей леммы, состоит из множества хорд С\Т и некоторых ветвей. Это вытекает из того факта, что каждая хорда e' є С\Т принадлежит в точности к одному фундаментальному циклу, а именно к Cе. Множество

является также в силу предыдущей леммы псевдоциклом, причем он может содержать только ветви. Однако ни один непустой псевдоцикл не может содержаться в Т, так как каждый непустой подграф без циклов содержит вершину степени 1 («висячую»). Отсюда следует, что множество (2.2) пустое, что эквивалентно равенству (2.1). Однозначность представления (2.1), легко следует из того, что цикл С_е является единственным фундаментальным циклом, содержащим хорду е (е є Е\Т)

Теорема, которую мы доказали, имеет очень простую интерпретацию в терминах линейных пространств. Пусть Е = {e₁,...., e_m} и каждому псевдоциклу C поставлен в соответствие вектор (а₁,..,а_n), где

Сумме таких векторов в предположении, что суммы координат берутся по модулю 2, соответствует симметрическая разность некоторых псевдоциклов. Лемма 2.7 утверждает, что векторы, поставленные в соответствие псевдоциклам, образуют подпространство m-мерного линейного пространства над двухэлементным полем (состоящим из 0 и 1 с операциями сложения по модулю 2 и умножения). Отметим, что произвольная линейная комбинация в пространстве над двухэлементным полем соответствует симметрической разности, так как единственным ненулевым элементом (коэффициентом) может быть только 1. В свою очередь теорема 2.8 говорит, что фундаментальные циклы определяют базис нашего подпространство.

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

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

Алгоритм 2.9. (Нахождение множества элементарных циклов графа.)

Данные: Граф G = (V, Е), представленный списками инцидентности ЗАПИСЬ[ v ]. v є V.

Результаты: Множество элементарных циклов графа G.

1. procedure ЦИКЛ (u); (* нахождение фундаментального множества циклов для компоненты связности, содержащей вершину u, переменные d, nиm, СТЕК. ЗАПИСЬ. WGN - глобальные*}
2. begin d:= d+ 1; CTEK[ d ]:= v; nиm:= nиm + 1; WGN[v]:= nиm;
3. for u є ЗАПИСЬ[ v ] do
4. if W'GN[ u ] = 0 then ЦИКЛ(u)
5. else if (u ≠ CTEK[ d - 1 ]) and (WGN[ v ] > WGN[ u ]) then (*использованная вершина v удаляется из стека *)
6. выписать цикл с вершинами
7. CTEK[ d ],CTEK[ d-1 ],...,CTEK[ c ], где СТЕК[ с ] = u;
8. d:= d — 1 (*использованная вершина v удаляется из стека *)
9. end; (*ЦИКЛ*)
10. begin (* главная программа*)
11. for v є V do WGN[ v ]:= 0: num:= 0: (*инициализация*)
12. d:= 0; СТЕК[0]:= 0; (* d =число элементов в стеке*)
13. for v є V do
14. if WGN[ v ] = 0 then ЦИКЛ(u)
15. end

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

Дата добавления: 2014-01-07