Дерево, лес. Основные свойтсва деревьев

Свойства:

1. n – количество вершин, m – количество ребер. k – количество компонент связности.

2. Любое ребро в дереве является мостом (дерево – мин. связный граф).

3. Каждое дерево содержит, как минимум, 2 вершины с локальной степенью 1. Такие вершины – висячие.

4. Удаление висячих вершин вместе с инцидентными им ребрами не меняет свойств графа.

5. Добавление в дерево нового ребра, инцидентного двум различным вершинам, ведет к образованию цикла, который пойдет по вновь добавленному ребру.

6. Если связный граф не является деревом, то удаление из него ребер без нарушения связности ведет к образованию дерева.