Деревья и их свойства. Лес

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

Определение 10.2. Любой неорграф без циклов называется лесом, или ациклическим графом.

Таким образом, компонентами связности любого леса являются деревья.

На рис. 17 показан лес, состоящий из двух деревьев.

Свойства деревьев сформулируем в виде следующей теоремы.

Теорема 10.1. Пусть G = (S, U) и = n, = m. Тогда следующие условия эквивалентны:

1) G – дерево;

2) G – связный граф и m = n - 1;

3) G – ациклический граф и m = n - 1;

4) любые две различные вершины графа соединяет единственная простая цепь;

5) G – ациклический граф, такой, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл. 

Теорема 10.2 (Кэли). Число деревьев с n занумерованными вершинами равно . 

Определение 10.3. Ориентированным деревом (ордеревом) называется

орграф G = (S, U), удовлетворяющий следующим двум условиям:

1) существует единственная вершина x_iÎ S, называемая корнем, не имеющая предшествующих вершин (т. е. );

2) любой вершине x_j, отличной от x_i, в орграфе G непосредственно предшествует ровно одна вершина (т. е. ).

Определение 10.4. У злом ордерева называется вершина, отличная от корня.

Определение 10.5. Л истом ордерева называется вершина x такая, что и

Определение 10.6. Ветвью ордерева называется путь из корня в лист.

Определение 10.7. Высотой ордерева называется длина его наибольшей ветви.

Определение 10.8. Уровнем вершины ордерева называется расстояние от корня до этой вершины.

Отметим, что корень имеет уровень 0.

Определение 10.9. Ярусом ордерева называется множество вершин одного уровня.

Замечание 10.1. Неориентированное дерево можно преобразовать в ориентированное, выбрав в качестве корня произвольную вершину. На рис. 18 корень графа – вершина x₇. 

Пример 10.1. Рассмотрим ордерево, изображëнное на рис. 18. Тогда: все вершины, кроме x₇, являются узлами ордерева; вершины x₁, x₅, x₈, x₁₀, x₁₁, x₁₂ – листами; путь x₇ ® x₆ ® x₃ ® x₂ ® x₁₀ – одна из ветвей; высота ордерева равна 5; множество вершин { x₁, x₅, x₉, x₁₀ } уровня 4 образует один из ярусов ордерева. 

Определение 10.10. Остовом неорграфа G = (S, U) называется его часть G¢ = (S¢, U¢), такая, что S¢ = S и G¢ – лес, образующий дерево на любой связной компоненте графа G.

Из определения 10.10 следует, что если G – связный неорграф, то остов G¢ является деревом, которое будем называть остовным деревом графа G.

Определение 10.11. Остовом орграфа G называется его часть G¢, такая, что ассоциированный с G¢ неорграф F(G¢) является остовом графа F(G).

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

Замечание 10.2. 1) В каждом графе существует остов, который можно получить, разрушая в каждой связной компоненте циклы, т.е. удаляя лишние рëбра.

2) Остов графа определяется неоднозначно. 

Пример 10.2. На рис. 19 изображены неорграф G и один из его остовов G¢. 

Для подсчета числа остовов в неорграфе используется матрица Кирхгофа.

Теорема 10.3 (Кирхгофа). Число остовных деревьев в связном неорграфе G порядка n ³ 2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа. 

Из определения дерева вытекает следующая теорема.

Теорема 10.4. Пусть G = (S, U) – произвольный неорграф, = n, = m, k – число компонент связности графа G. Число рëбер, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m – n + k.

Доказательство. Пусть i -я компонента связности G_i содержит n_i вершин и m_i рëбер. По условию G – связный граф. Следовательно, остов G_i ¢ графа G_i является деревом, а значит, он содержит (n_i – 1) ребро. Таким образом, для получения остова G_i ¢ из i -й компоненты связности G_i требуется удалить m_i – (n_i – 1) ребер.

Просуммируем удаляемые ребра по всем компонентам связности, учитывая, что Получим 

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

Определение 10.13. Число n* (G) = n - k называется коциклическим рангом или корангом.

Таким образом, n * (G) равно числу рëбер, входящих в любой остов графа G. Очевидно, что n (G) +n* (G) = m.

Из теоремы 10.4 непосредственно вытекают два следствия.

Следствие 10.4.1. Неорграф G является лесом тогда и только тогда, когда

n (G) =0. 

Следствие 10.4.2. Неорграф G имеет единственный цикл тогда и только тогда, когда n (G) =1. 

Пример 10.3. Найти для графа G, изображенного на рис. 19, цикломатическое число и коциклический ранг.

Решение. Граф G имеет 8 вершин, 14 ребер и 1 компоненту связности. Тогда, согласно по теореме 10.4, цикломатическое число n (G) = 14 – 8 +1 = 7, а коциклический рангn * (G) = 8 – 1 = 7.