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

Пусть T(V, E) - неориентированный граф, не содержащий циклов, петель и кратных рёбер. Если при этом T -связный граф, то он называется неориентированным деревом, если T -граф несвязный, то он называется лесом. Связные компоненты леса являются деревьями.

Так как дерево не содержит циклов, то любая цепь в нём является простой.

Теорема 3.4 (свойство 1). Любые две вершины дерева v’ и v’’ связаны единственной цепью.

ÿ Если бы были две цепи, связывающие вершины v’ и v’’, то был бы и цикл, что противоречит определению дерева. ÿ

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

Наименьшая из возможных длина простой цепи, соединяющей вершины v’ и v’’, называется расстоянием между этими вершинами.

Наглядное представление для дерева Т можно получить при помощи следующей конструкции. Выберем произвольную вершину v₀ (корень дерева) и проведём все рёбра к вершинам, находящимся на расстоянии 1 от v₀. От этих вершин проведём рёбра к вершинам, находящимся на расстоянии 2 от v₀, и т.д. Из вершины v_n,i , расположенной на расстоянии n от v₀, выходит ровно одно ребро к предшествующей вершине v_n-1,j , находящейся от v₀ на расстоянии n_-1, а также некоторое семейство рёбер к последующим вершинам v_n+1,k , находящимся на расстоянии n+1 от v₀. Ни для какой из этих вершин v_n,i не может быть рёбер, соединяющих её с вершинами v_n,l с тем же расстоянием n от v₀.

Вершина v графа F называется концевой (или висячей), если её степень равна единице, т.е. r (v)=1. Инцидентное концевой вершине ребро также называют концевым.

Теорема 3.5 (свойство 2). Если конечное дерево состоит более чем из одной вершины, то оно имеет хотя бы две концевые вершины и хотя бы одно концевое ребро.

ÿ I случай. Пусть v₀ - концевая вершина. Тогда от неё отходит одно ребро в вершину v₁. В этом случае кроме v₀ концевыми являются последнее ребро в цепи, выходящей из v₁, и одна из инцидентных ему вершин.

II случай. Пусть вершина v₀ не является концевой. Значит, от неё отходят хотя бы два ребра в вершины v_1,1 и v_1,2. Последнее ребро в цепи, выходящей из v_1,1, и одна из инцидентных ему вершин являются концевыми. Аналогично концевыми являются и последнее ребро с инцидентной ему вершиной в цепи, выходящей из v_1,2. ÿ

В дереве с корнем v₀ можно естественным образом ориентировать рёбра в направлении “от корня”. В каждую вершину ориентированного “от корня” дерева (за исключением самого корня) входит только одно ребро, следовательно, число всех входящих рёбер, т.е. всех рёбер дерева, равно числу его вершин. Исключение составляет корень: в него не входит ни одно ребро. Поэтому в конечном дереве число вершин на единицу больше числа рёбер (свойство 3): |V| = |E| + 1. (9.1)

Каждое дерево можно ориентировать, выбрав в качестве корня любую его вершину.

Цикломатическим числом (ЦЧ) конечного неориентированного графа F(V, E) называется величина

g(F) = k + |E| - |V|, (9.2)

где k - число связных компонент графа.

Пример. Для графа, изображенного на рисунке 3.3, б: g(F) = 2 + 2 - 4 = 0.

В силу соотношения (9.1) ЦЧ дерева равно нулю; ЦЧ леса - сумме ЦЧ своих связных компонент-деревьев, т.е. также равно нулю.

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

|E| > |V| - 1, (9.3)

и, значит, его ЦЧ положительно: g( F) > 0.