Лекция 11. Кодирование деревьев

1.

Кодирование
деревьев
Лецкия 11

2.

ДЕРЕВЬЯ
Деревом называется связный граф, не
имеющий циклов. Граф без циклов называют
лесом.
Вершину степени 1 в дереве называют
висячей вершиной или листом.
Теорема 7.1 (о листьях). Для любого дерева
с справедливы следующие утверждения:
Рис 7.1. Дерево. Вершины
D,E,F,H,J,K - листья
1) для каждой вершины дерева любая
наиболее удаленная от нее вершина есть
лист;
2) в дереве имеется не менее двух листьев.
Теорема 7.2 (о числе ребер дерева). Если в
дереве