ОПРЕДЕЛЕНИЕ 25.Лесомназывается неориентированный граф без циклов. Деревомназывается связный лес.
Таким образом, дерево характеризуется тремя свойствами:
- неориентированность,
- связность,
- отсутствие циклов.
Видимо, деревья это самый важный для приложений вид графов. На них базируются многие алгоритмы сортировки и поиска, базы данных и др.
Вершины дерева степени 1 (висящие вершины) называются листьями. Все логично! Какое же дерево без листьев?
Приведем два простых свойства дерева.