Деревья

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

Определение 1.10. Граф

называется деревом, если

в нем есть одна вершина
, в которую не входят ребра; она называется корнем дерева;
в каждую из остальных вершин входит ровно по одному ребру;
все вершины достижимы из корня.

На рисунке 2 показан пример дерева

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

Корень - это единственная вершина, в которую не входят ребра, листья - это вершины, из которых не выходят ребра. Путь из корня в лист называется ветвью дерева. Высота дерева - это максимальная из длин его ветвей. Глубина вершины - это длина пути из корня в эту вершину. Для вершины

, подграф дерева

, включающий все достижимые из

вершины и соединяющие их ребра из

, образует поддерево

дерева

с корнем

. Высота вершины

- это высота дерева

. Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.

Рис. 1.2. Дерево G1

Если из вершины

ведет ребро в вершину

, то

называется отцом

, а

- сыном

(в последнее время в ангоязычной литературе употребляется асексульная пара терминов: родитель - ребенок). Из определения дерева непосредственно следует, что у каждой вершины кроме корня имеется единственный отец. Если из вершины

ведет путь в вершину

, то

называется предком

, а

- потомком

. Вершины, у которых общий отец, называются братьями

или сестрами.

Пример 1.4. В дереве на рис. 1.2

вершина