3.5. Дерево. Остов

Деревом называется конечный связный граф без циклов. Из свойств отсутствия циклов и связности следует, что у дерева количество компонент связности p=1 и цикломатическое число =0, т.е.

= m - n+1=0,

отсюда следует, что

m=n-1, (3.3)

т. е. число ребер в дереве на единицу меньше числа вершин.

Ниже на рис. 3.7 приведены примеры деревьев.

11