Деревья. Лес.

Деревомназывают конечный связной граф с выделенной вершиной ( корнем ), не имеющий циклов ( рис. 12 ).

Рис. 12. Граф – дерево

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

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

Рис.13. Лес

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

Теорема 5.Граф G (X, U) является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

граф G (X, U) связан и не содержит циклов;

граф G (X, U) не содержит циклов и имеет n – 1 ребро;

граф G (X, U) связан и имеет n – 1 ребро;

граф G (X, U) не содержит циклов, но добавление ребра между несмежными вершинами приводит к появлению одного и только одного элементарного цикла;

граф G (X, U) связный, но утрачивает это свойство после удаления любого ребра;

в графе G (X, U) всякая пара вершин соединена цепью, и только одной.

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

Пусть G – неориентированный связный граф, имеющий n вершин и m ребер. Цикломатическим числом связного графа G и n вершинами и m ребрами называется число

.

Цикломатическое число дерева равно нулю.

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

Например, для полного графа ( имеющего пять вершин и ребер ) цикломатическое число равно