Цикломатическое число графа. Деревья.

 

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

Прежде чем рассматривать алгоритмические задачи, связанные с циклами, введем важную характеристику графа — цикломатическое число.

Определение 1: Пусть граф имеет компонент связности. Цикломатическим числом графа называется число где — число вершин графа, — число его ребер.

Одним из свойств цикломатического числа является его монотонность. Дадим строгую формулировку этого свойства.

Теорема 1: Пусть граф является суграфом графа , тогда выполняется неравенство:

Доказательство: Очевидно, достаточно рассмотреть случай, когда граф получен из графа удалением одного из ребер. В этом случае . Если выбрасываемое ребро является перешейком, то и, следовательно,

.

Если же выбрасываемое ребро не перешеек, то и тогда

.

Теорема доказана.

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

Рис. 14

 

Добавляя к этой цепи ребро , получим цикл (например, на рис. 14а). Отмеченное ребро не есть перешеек. А на рис. 14 б) — перешеек. Таким образом, цикломатическое число связано в каком-то смысле с количеством циклов в графе.

Следствие 1: Для любого графа выполнено неравенство .

Доказательство: Пусть — некоторый граф. Очевидно (граф с теми же вершинами, что и , но без ребер) есть суграф графа . Используя теорему 1, имеем неравенство: . Но для графа справедливо соотношение , откуда следует формула:

.

Теорема 2:Следующие свойства графа эквивалентны:

1) граф связен и не имеет циклов;

2) граф связен и ;

3) граф связен и ;

4) и .

Доказательство: Заметив, что для связного графа равенство влечет равенство ; — равенство , а из условий и (без предположения о связности) вытекает, что , так как

и, следовательно, граф связен. Таким образом, свойства 2), 3) и 4) эквивалентны.

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

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

.

Откуда:

,

что противоречит следствию из теоремы 1. Теорема доказана полностью.

Определение 2: Граф называется деревом, если он обладает одним (и, следовательно, всеми остальными) из свойств 1) - 4).

Иногда при определении дерева исключается случай . По определению 2 такой граф является деревом; в ряде случаев такое определение оказывается более удобным.

Заметим, что если граф состоит из двух несвязных графов и , то справедливо соотношение:

.

Докажем теперь характеристическое свойство .

Теорема 3: Равенство эквивалентно отсутствию циклов в графе .

Доказательство: Пусть граф состоит из несвязных компонент . Тогда имеем равенство:

;

кроме того,

.

Из этих соотношений следует равенство .

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

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

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

Рассмотрим условие связности графа. Приведем теорему, дающую необходимое и достаточное условие связности графа.

Теорема 4: (о частичном дереве). Граф связен тогда и только тогда, когда он содержит некоторое дерево в качестве суграфа.

Доказательство: Очевидно, что если граф содержит частичное дерево, то он связен.

Докажем обратное. Пусть граф связен. Тогда, если , то есть дерево (см. определение 2). Если , то по теореме 3 в графе есть хотя бы один цикл. Удалив одно из ребер этого цикла, мы не нарушим связность графа и уменьшим его цикломатическое число на единицу. Через конечное число таких шагов получим связный суграф с , т. е. дерево. Теорема доказана.

Замечание: Суграф графа , являющийся деревом, называют частичным, деревом графа .