2
	1	3,9,5,4,11,	6,7,8,14,	15
		12,16	17,13

10

Рис. 6.17

Построенный конденсат полезно проанализировать на предмет нахождения циклов – их там быть ни в коем случае не должно. Если обнаружился цикл, значит, есть множество взаимодостижимых укрупненных вершин, и, следовательно, входящие в наименование этих укрупненных вершин конденсата вершины исходного графа должны были войти в одну компоненту. Например, если была допущена ошибка при решении задачи на рис. 6.17 и найдены только два цикла {1,2,3} и {4,5,6,7}, то конденсат выглядел бы так (рис. 6.18, слева), как видно в нем присутствует цикл, чего быть не должно. Это сигнал ошибки. При правильном решении конденсат выглядит иначе (рис. 6.18, справа).

1,2,3	4,5,6,7	1,2,3,4,5,6,7

Рис. 6.18

6.4.Цикломатика графов

6.4.1. Ациклические графы

Ациклическим графом называется граф, не содержащий циклов.

Деревом называется связный граф, не содержащий циклов. Несвязный граф, состоящий из нескольких деревьев, иногда на-

зывают лесом.

160

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

Теорема 6.3. Если граф G является деревом, то число его ребер (т) и число его вершин (п) связаны соотношением т = п – 1.

На самом деле, верно и обратное утверждение, которое является частью более общей теоремы о свойствах деревьев.

Теорема 6.4. Следующие условия равносильны:

•граф G является деревом;

•число ребер (т) и число вершин в графе (п) связаны соотношением т = п – 1;

•любые две вершины в графе могут быть связаны (простым) путем, и этот путь единствен;

•граф G связен и не содержит циклов.

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

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

Рис. 6.19

161

6.4.2. Базисные циклы и цикломатическое число

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

ся остовным деревом или остовом, или каркасом графа G.

Строго говоря, подграф G1 = (V1,U1) графа G = (V,U) называется

остовным деревом, если G1 – дерево и V1 = V.

Теорема 6.5. Любой (конечный) связный граф G = (V,U) содержит хотя бы одно остовное дерево G1 = (V,U1).

	2	3
1	8	4
	7	5

6

Исходный граф

2	3		2	3
1	8	4	1	8	4
7	5		7	5
	6			6
Остов – вариант 1			Остов – вариант 2
			Рис. 6.20

Как видно из рис. 6.20, выделенные остовы, если их рассматривать отдельно от остальных ребер, представляют собой деревья, в

162

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

ным.

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

Поскольку для каждой i-й компоненты на ni вершинах число ребер в соответствующем остовном дереве равно ni–1, то на k компонентах c общим количеством вершин, равным n (n – сумма всех ni) сумма ребер в остовном лесе составит (n – k). Значит, из имеющихся m ребер нужно будет удалить m – (n – k) = m – n + k ребер.

Значит, для произвольного графа цикломатическое число определяется по формуле (6.1) и является неотрицательным целым числом:

γ(G)= m – n + k.

(6.1)

Таким образом, цикломатическое число дает меру связности графа: цикломатическое число дерева равно нулю, а цикломатическое число простого цикла равно единице.

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

Задача 6.3. Построить матрицу базисных циклов для графа на рис. 6.20 при условии, что остов выбран, как в варианте 1.

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

163