Цикломатическое число графа. Построение Остовного дерева связного графа.

Остовным деревом связного графа G (V, E) называется любой его подграф, содержащий все вершины G иявляющийся деревом.

На рисунке приведены два графа G и по одному из их остовных деревьев T.

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

Теорема. Цикломатическое числом графа G(V,E) не зависит от последовательности удаления ребер и имеет место формула:

=| E || - | V|+k (G),

где k(G) - число компонент связности.

Определение. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графаG и являющийся деревом.

Пусть G связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G) – 1 ребер. Таким образом, любое остовное дерево графа G есть результат удаления из G ровно m(G)-(n(G)-1)=m(G)-n(G)+1 ребер.

Определение. Число m(G)-n(G)+1 называется цикломатическим числом связного графа G и обозначается через v(G).

Замечание. Понятие остовного дерева и цикломатического числа аналогичным образом определяется и для произвольного связного псевдографа G.

Покажем существование остовного дерева для произвольного связного псевдографа G=(V,X), описав алгоритм его выделения.

Шаг 1. Выбираем в G произвольную вершину u1, которая образует подграф G1 псевдографа G, являющийся деревом. Полагаем i=1.

Шаг 2. Если i=n, где n=n(G), то задача решена, и Gi – искомое остовное дерево псевдографа G. В противном случае переходим к шагу 3.

Шаг 3. Пусть уже построено дерево Gi, являющееся подграфом псевдографа G и содержащий некоторые вершины u1, …, ui, где 1didn-1. Строим граф Gi+1, добавляя к графу Gi новую вершину ui+1О V, смежную в G с некоторой вершиной uj графа Gi, и новое ребро (ui+1, uj) (в силу связности G и того обстоятельства, что i < n, указанная вершина ui+1 обязательно найдется). Согласно утверждению граф Gi+1 также является деревом. Присваиваем i:=i+1 и переходим к шагу 2.

Пример 87.

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

Решение.

На рисунке 40 приведена последовательность графов Gi, i=1, 2, 3, 4, 5, получаемых в результате выполнения алгоритма.

При этом в силу того, что n(G)=5, G5 - остовное дерево графа G.

Замечание. Остовное дерево связного графа может быть выделено, вообще говоря, не единственным способом.

Общее число остовных деревьев связного графа может оказаться весьма большим. Например, для полного графа с n вершинами оно равно n^n-2.

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

Определение. Число ребер, удаленных при построении остовного леса произвольного графа G, называется цикломатическим числом (или цикломатическим рангом) графа G и обозначается через g (G) = m – n + k.

Пример 88.

Циклический ранг дерева равен нулю, а циклический ранг циклического графа равен единице.

Определение. Коциклическим рангом графа G называется число ребер в его остовном дереве.

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

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