3.4 Деревья

 

Деревом называется конечный связный граф без циклов. Лесом из k деревьев называется граф без циклов, у которого число связности равно k, k>1.

 

Теорема. Для  конечного графа {M, N, T) следующие 3 утверждения эквивалентны:

1) (M, N, T) – дерево, т. е. связный граф без циклов.

2) (M, N, T) не содержит циклов и |N|=|M|-1.

3) (M, N, T) связен и |N|=|M|-1.