Деревья

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

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

Теорема о свойствах деревьев.

Пусть – простой граф с р вершинами и q ребрами. Следующие утверждения эквивалентны

1. – дерево.

2. Любые две вершины графа соединены единственной простой цепью.

3. – связен и каждое его ребро – это мост.

4. – связен и число ребер графа G на единицу меньше числа вершин, .

5. не содержит циклов и .

6. не содержит циклов, но добавление в граф любого ребра приводит к появлению единственного цикла, который проходит через добавленное ребро.