3.3. Алгоритмы нахождения подграфов

Циклом называется замкнутый маршрут в неориентированном графе. Для ориентированного графа определяется аналогично понятие контур - замкнутый путь.

Пример 3.3.1

Рассмотрим граф (рис.3.3.1,а), в котором каждому ребру присвоен свой номер. В графе можно выделить соответствующее ему число циклов. Для нашего примера циклами С_i являются замкнутые маршруты, образованные ребрами (рис.3.3.1,б): С₁ = {1,2,5,4}, C₂ = {5,6,7}, С₃ = {3,6,2}, С₄ = {1,2,6,7,4}.Среди этих циклов найдутся такие, которые включают в себя другие циклы. Так, цикл С₄ состоит из циклов C₁ и C₂, у которых имеется общее ребро 5, не вошедшее в цикл 4. Говорят, что цикл 4 получен линейной комбинацией циклов 1 и 2, т.е. является линейно зависимым от них.

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

Присвоим каждому ребру графа номер j, j = 1,m и поставим в соответствие каждому циклу C_i, двоичный m–разрядный ве­ктор V_i, компоненты v_ij которого определяются следующим об­разом: V_j = 0, если ребро j не входит в цикл С_i, V_j = 1 – в противном случае.

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

Для рассмотренного выше примера имеем:

Поскольку V_i отношение принадлежности ребер графа циклу C_i, a C_i – это множество ребер, то в результате применения векторной операции  получаем совокупность ребер, входящих в циклы, составляющих линейную комбинацию, за исключением общих для этих циклов ребер; на языке теории множеств это означает объединение множеств C_i, без их пересечения, что соответствует операции «симметрическая разность» для множеств.

j	1	2	3	4	5	6	7
V1	1	1	0	1	1	0	0
	
V2	0	0	0	0	1	1	1
V4	1	1	0	1	0	1	1

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

Максимальное множество линейно независимых циклов образует систему независимых циклов, мощность  этого множества называется цикломатическим числом.

3.3.2. Алгоритм построения системы независимых циклов графа

1. Строится произвольный остов графа. В исходном графе отмечаются ребра, не включенные в остов.

2. Выбирается очередное отмеченное ребро и строится цикл, содержащий это ребро и ребра остова. Рассмотренное ребро отмечается и, если есть еще не отмеченные ребра, то выполняется п.2 , иначе – п.3.

3. По формуле Эйлера  = m –n + p производится проверка числа построенных циклов (для контроля).

1)(Х2,Х4)(X4,X5)(X5,X1)(X1,X2)

2)(X3,X5) (X5,X1)(X1,X2)(X2,X3)

3) (X3,X4)(X4,X5)(X5,X1)(X1,X2) (X2,X3).