Деревья. Существует один простой и важный тип графов, которому разные авторы дали одинаковое название – деревья

Существует один простой и важный тип графов, которому разные авторы дали одинаковое название – деревья. Для них выполняются многие утверждения, которые не всегда выполняются для графов в общем случае. Деревья являются самым распространенным классом графов, применяемых в программировании, причем в самых разных ситуациях.

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

Ориентированное дерево представляет собой свободный от петель ориентированный граф, соотнесенный граф которого является деревом.

Если дерево имеет хотя бы одно ребро, оно имеет хотя бы две вершины со степенью . Вершины степени называются листьями. Другие вершины называются внутренними вершинами.

Если дерево изображено таким образом, что в верхней части помещена вершина, а остальные находятся ниже его, то вершина в самой верхней части называется корнем дерева. Если корень дерева определен, то дерево называется корневым деревом.

Если корень выбран, уровень вершины определяется длиной единственной цепи из корня в вершину .

Определение 2.2. Высотой дерева называется длина самой длинной цепи от корня до листа, обозначается: .