Элементы цикломатики

Теория

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

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

Пусть с — некоторая цепь графа G. Через Е(с) обозначим множество ребер этой цепи. Для любой цепи с множество ее ребер Е(с) определяется однозначно. Обратно, если фиксировано какое-то (конечное) множество ребер {e1,...,en} графа G, то можно доказать следующий факт: если указанное выше множество ребер формирует цепь, т.е. существует такая цепь (последовательность вершин графа) v0, v1, ..., vn, что {v0, v1} = ei1, ..., {vn-1, vn} = ein, где 1 ≤ i1 ..., in ≤ n, то эта цепь при условии, что она не является циклом, определяется с точностью до порядка расположения ребер в последовательности (от v0 к vn или наоборот). Если цепь является циклом, то она определяется с точностью до порядка расположения ребер в последовательности и до выбора начальной вершины v0. Так, на рис. 5.41 множество ребер {{v1,v2}, {v2,v3}, {v3,v5}, {v5,v6}} формирует цепь v1, v2, v3, v5, v6,а также цепь v6, v5, v3, v2, v1 („инверсия" предыдущей цепи). Множество ребер {{v1,v2}, {v2,v3}, {v3,v1}}, формирует цикл v1, v2, v3, v1, а вместе с ним циклы:

v2, v3, v1, v2;     v3, v1, v2, v3;     v1, v3, v2, v1;

v3, v2, v1, v3;     v2, v1, v3, v2.

Рис. 5.41. Элементы цикломатики

Множество же ребер {{v1, v2}, {v2, v3}, {v3, v5}, {v4, v6}} не формирует никакой цепи.

* Отметим, что не любой базис может быть вычислен посредством поиска в глубину (см. граф на рис. 5.23).

Тогда, говоря неформально, если не различать цепи, состоящие из одних и тех же ребер, но проходимые в противоположных направлениях, и циклы, состоящие из одних и тех же ребер, но проходимые в противоположных направлениях и от различных начальных вершин, можно отождествить цепи (и циклы) с множествами их ребер. Эти соображения позволяют ввести операцию сложения цепей как операцию над множествами их ребер.

Для двух произвольных цепей а, и графа G их сумму определим (с учетом сделанного выше замечания) так:

a ⊕ b = E(a) Δ E(b),

т.е. сложение цепей сводится к вычислению симметрической разности множеств их ребер.

Сумма цепей, вообще говоря, не является цепью, т.е. соответствующее множество ребер в общем случае не формирует цепь. На рис. 5.41 сумма цепей v1, v3, v4, v6 и v2, v3, v4, v5, v6 не есть цепь. Алгебра, системой образующих которой служит множество всех конечных цепей данного графа G, вают алгеброй цепей неориентированного графа G. Эта алгебра является абелевой группой в силу известных свойств операции симметрической разности множеств (см. 1 и 2).

Любая абелева группа G = (М, ⊕, 0) может быть рассмотрена как линейное пространство над полем ℤ2 (полем вычетов по модулю 2). Действительно, определим умножение элемента g группы на элементы поля ℤ2: 0 ⋅ g = 0 и 1 ⋅ g = g. Выполнение аксиом линейного пространства в этом случае можно легко проверить. Обратим внимание, что в любой линейной комбинации элементов e1, ..., еk такого линейного пространства каждый коэффициент λk равен либо 0, либо 1. Тогда понятно, что нетривиальная линейная комбинация элементов e1, ..., еn, т.е. линейная комбинация, не все коэффициенты которой равны 0, есть не что иное, как сумма элементов непустого подмножества множества {e1, ..., еn}.

Применив указанное построение к алгебре цепей неориентированного графа, получим линейное пространство цепей данного графа. Его называют пространством цепей графа. Заметим, что в этом пространстве каждый элемент противоположен себе самому, так как для каждого элемента а этого пространства а ⊕ а = ∅ (в силу известных свойств операции симметрической разности).

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

Пространство циклов неориентированного графа есть тем самым линейная оболочка в пространстве цепей данного графа множества всех его конечных циклов (причем, как видно на рис. 5.42, сумма циклов в общем случае не есть цикл). Бели граф конечен, то его пространство циклов также конечно.

Теорема 5.6. Множество фундаментальных циклов, вычисляемое алгоритмом поиска в глубину в неориентированном графе G, есть базис пространства циклов этого графа.

Рис. 5.42. Множества и отношения

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

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

Докажем сначала, что в пространстве циклов сумма любых двух отличных друг от друга циклов есть либо замкнутая цепь (в частности, цикл), либо непустое множество попарно не пересекающихся (т.е. не имеющих один с другим ни общих ребер, ни общих вершин) циклов*.

*Это выражение есть, разумеется, вольность речи. Строго говоря, сумму циклов нельзя назвать множеством циклов, но ей в данном случае можно однозначно сопоставить такое множество. Так, на рис. 5.42 сумме циклов соответствуют два непересекающихся между собой цикла.

Пусть С1 и C2 — два цикла графа G. Если они не имеют ни общих вершин, ни общих ребер, то доказываемое утверждение тривиально. Предположим, что ребра

e1 = {a1, b1}, ..., en = {an, bn} -

все ребра, общие для циклов С1 и C2 (рис. 5.43). В каждом из рассматриваемых циклов для каждого i = 1,n—1 существуют цепи, соединяющие вершины bi и ai+1. Обозначим их W1i для первого и W2i для второго цикла. Также существуют цепи, в первом цикле — W10 и во втором — W20, соединяющие вершины a1 и bn. Все эти цепи таковы, что не содержат ни одного из ребер еi, i = 1,n. Поскольку ребра еi, i = 1,n, — все ребра, общие для циклов С1 и С2, то для каждого i = = 0,n—1 цепи W1i и W2i не имеют общих ребер и имеют две общие вершины (см. рис. 5.43). Это значит, что каждая сумма W1i ⊕ W2i, i = 0,n—1, есть цикл (в пространстве цепей графа G). Обозначим его .

Рис. 5.43. Элементы цикломатики

Докажем, что циклы попарно не пересекаются (т.е. не имеют попарно ни общих вершин, ни общих ребер). Действительно, цепи W1i и W2i при i ≠ j не могут иметь ни общих вершин, ни общих ребер, так как вершины а1, b1, а2, b2, ..., an, bn — это, по построению, все вершины, общие для циклов С1 и С2. В то же время (для фиксированного s ∈ {1,2}) никакие две цепи Wsi и Wsj при i ≠ j не могут иметь общих вершин и ребер, так как тогда циклы С1 или C2 не были бы простыми цепями.

Итак, циклы попарно не пересекаются. Тогда

причем в том и только в том случае, когда множество ребер {e1,..., еn} формирует цепь, написанная выше сумма есть цикл.

Аналогично рассматривается случай, когда циклы С1 и С2, не имея общих ребер, имеют общие вершины: а1, а2, ..., аn (рис. 5.44). Тогда, как можно видеть на рис. 5.44, сумма С1 ⊕ С2 будет замкнутой цепью (которая в общем случае не будет циклом).

Рис. 5.44. Элементы цикломатики

Пусть С — произвольный цикл графа, а f1, ..., fm — все его обратные ребра, и пусть F1, ..., Fm — фундаментальные циклы, содержащие ребра f1, ..., fm соответственно.

Рассмотрим суммы (в пространстве циклов):

C ⊕ F1 = C1,

C1 ⊕ F2 = C ⊕ F1 ⊕ F2 = C2,

.................................................................................

Cm-2 ⊕ Fm-1 = C ⊕ F1 ⊕ ... ⊕ Fm-1 = Cm-1.

Как было доказано выше, каждая из этих сумм есть либо замкнутая цепь, либо множество попарно не пересекающихся циклов, причем сумма Сi, 1 ≤ i ≤ n-1, содержит обратные ребра fi+1, ..., fm, и только их, так как при сложении С с F1 исчезает общее для них ребро f1, при сложении С1 с F2 — общее для них ребро f2 и т.д. Следовательно, последняя из этих сумм содержит единственное обратное ребро fm. Значит, сумма Cm-1 есть цикл. В самом деле, если бы она была непустым множеством попарно не пересекающихся циклов, то содержала бы по крайней мере два таких цикла. Поскольку в Cm-1только одно обратное ребро, то по крайней мере один из этих циклов проходил бы только по древесным ребрам, что невозможно.

Аналогично, предполагая, что Cm-1 есть замкнутая цепь, не являющаяся циклом, получим (с учетом следствия 5.1), что такая цепь представима в виде суммы по крайней мере двух циклов, не имеющих общих ребер. Тогда один из этих циклов содержит только древесные ребра, что невозможно.

Итак, сумма Cm-1 есть цикл, содержащий только одно обратное ребро. В силу взаимно однозначного соответствия между множеством обратных ребер и множеством фундаментальных циклов цикл Cm-1 совпадает с фундаментальным циклом Fm:

Cm-1 = Fm,

или

C ⊕ F1 ⊕ F2 ⊕ ... ⊕ Fm-1 = Fm,

откуда (поскольку каждый элемент пространства циклов противоположен сам себе)

C = F1 ⊕ F2 ⊕ ... ⊕ Fm.

Таким образом, произвольный цикл С представляется в виде некоторой линейной комбинации фундаментальных циклов. ▶

Из доказанной теоремы следует, что число фундаментальных циклов, находимое алгоритмом поиска в глубину, разно размерности линейного пространства циклов и не зависит от выбора начальной вершины, поскольку все базисы конечномерного линейного пространства состоят из одного и того же числа векторов [IV]. Это число называют циклическим рангом неориентированного графа. Разность числа всех ребер графа и его циклического ранга называется коциклическим рангом неориентированного графа. Таким образом, циклический ранг неориентированного графа — это число обратных ребер при поиске в глубину из любой вершины, а коциклический ранг — число древесных ребер при поиске в глубину из той же вершины.

Выведем формулу, связывающую циклический ранг ν, число ребер m, число вершин n и число компонент связности k произвольного неориентированного графа G.

Обозначим через μ коциклический ранг графа G. Тогда, поскольку в неориентированном дереве число ребер на единицу меньше числа вершин, получим

ν = m - μ = m - ((n1 - 1) + ... + (nk - 1)) = m - n + k,

где ni — число вершин в i-й компоненте связности графа G.

Итак,

ν = m — n + k.

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

Циклический ранг неориентированного графа показывает „степень цикличности" этого графа: чем больше циклический ранг, тем больше в графе циклов. Лес, в частности дерево, имеет нулевой циклический ранг (нуль-мерное пространство циклов).

Пример 5.16. Рассмотрим неориентированные графы, изображенные на рис. 5.41. Предположим, что в списках смежности вершины упорядочены по возрастанию номеров. На рис. 5.41 показаны результаты поиска в глубину из двух разных вершин: v1 в графе G1 и v4 в графе G2- Древесные ребра в графах выделены. По результатам поиска циклический ранг равен 4, а коциклический ранг — 5. В графе G1 фундаментальными являются циклы*

С1: v6v5v4v6,

С2: v5v3v4v5,

С3: v4v3v2v4,

С4: v3v1v2v3.

Циклы пронумерованы в порядке обнаружения.

Для графа G2 фундаментальными будут циклы

D1: v3v2v1v3,

D2: v3v4v2v1v3,

D3: v5v4v2v1,v3,v5,

D4: v6v4v2v1v3v5v6.

Разложение одного и того же цикла С

v2v3v5v6,v4,v2

по двум указанным базисам будет следующим (рис. 5.45):

С = С1 ⊕ С2 ⊕ С3, C = D1 ⊕ D4. #

Можно доказать, что изоморфные неориентированные графы имеют изоморфные линейные пространства циклов, однако обратное в общем случае неверно. Более того, в изоморфных графах должны совпадать „тонкие" структуры циклов: любое утверждение о циклах, истинное в одном графе, останется истинным в изоморфном ему графе.

*Записывая циклы (которые, по определению, есть последовательности вершин), мы, ради наглядности, пишем между вершинами значок непосредственной достижимости.

Рис. 5.45. Элементы цикломатики

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

Пример 5.17. Рассмотрим графы, представленные на рис. 5.46. Заметим, что у этих графов одинаковое количество вершин и ребер, а также одинаковые степени всех вершин. Поэтому гипотеза об их изоморфности представляется правдоподобной. Однако для доказательства изоморфизма графов необходимо явно указать биекцию множества вершин одного графа на множество вершин второго, при которой сохраняется отношение смежности. Поиск такой биекции весьма трудоемок, так как может потребовать полного перебора всех возможных вариантов. Для доказательства неизоморфности достаточно показать принципиальную невозможность установления требуемой биекции. Используем для этого анализ циклов.

Проведем поиск в глубину в каждом из графов. Если количество обратных ребер окажется различным, неизоморфность графов будет доказана. Для определенности в каждом из графов начнем поиск с вершины v1 и будем считать, что списки смежности каждой вершины упорядочены по возрастанию номеров вершин. На рис. 5.46 в графах выделены древесные ребра, полученные при поиске в глубину. В каждом из графов оказалось по шесть обратных ребер, и, следовательно, вывод о неизоморфности сделать нельзя.

Рис. 5.46. Элементы цикломатики

Различие можно увидеть в „тонких" стуктурах циклов. Заметим, что в графе G1 имеются четыре цикла длины 3:

v1v2v4v1,    v1v3v4v1,

v7v8v9v7,    v8v9v10v8.

В графе G1 таких циклов также четыре:

v1v2v4v1,    v1v2v3v1,

v7v8v9v7,    v8v9v10v8.

Однако количество циклов длины 4 в графах различно. В графе G1 таких циклов шесть:

v1v2v4v3v1,    v1v2v5v3v1.

v2v4v3v5v2,    v9v7v8v10v9.

v9v7v6v10v9,    v7v8v10v6v7.

а в графе G2 — всего два:

v1v3v2v4v1,    v8v10v9v7v8.

Следовательно, графы неизоморфны. #

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

Заметим, что в общем случае все циклы графа можно получить, рассматривая различные линейные комбинации над ℤ2 фундаментальных циклов. При этом следует учесть, что результатом сложения может быть множество ребер, образующих несколько непересекающихся циклов.