Дерево, лес. Основные свойтсва деревьев
ДОБАВИТЬ В КОНСПЕКТ
НАВИГАЦИЯ ПО СТРАНИЦЕ
Дерево – связный граф без циклов. Несвязный граф, каждая компонента которого представляет собой дерево – лес.
Свойства:
n – количество вершин, m – количество ребер. k – количество компонент связности.
Любое ребро в дереве является мостом (дерево – мин. связный граф).
Каждое дерево содержит, как минимум, 2 вершины с локальной степенью 1. Такие вершины – висячие.
Удаление висячих вершин вместе с инцидентными им ребрами не меняет свойств графа.
Добавление в дерево нового ребра, инцидентного двум различным вершинам, ведет к образованию цикла, который пойдет по вновь добавленному ребру.
Если связный граф не является деревом, то удаление из него ребер без нарушения связности ведет к образованию дерева.
