Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:
1. существует единственный узел, полустепень захода которого равна 0. Он называется корнем ордерева;
2. полустепень захода всех остальных узлов равна 1;
3. каждый узел достижим из корня.
Пример. На рисунке ниже приведены диаграммы всех различных ориентированных деревьев с 3 и с 4 узлами:
Теорема. Ордерево G(V, Е) с р вершинами и q дугами, обладает следующими свойствами:
1. q = p — 1;
2. если в ордереве отменить ориентацию ребер, то получится свободное дерево;
3. в ордереве нет контуров;
4. для каждого узла существует единственный путь, ведущий в этот узел из корня;
5. подграф, определяемый множеством узлов, достижимых из узла v, является ордеревом с корнем v (это ордерево называется поддеревом узла v);
6. если в свободном дереве любую вершину назначить корнем, то получится ордерево, при этом дуги будут последовательно ориентированы от корня обходом в глубину.
Концевая вершина (полустепень исхода равна 0) ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева — это расстояние от корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.
Замечание. Наряду с «растительной» применяется еще и «генеалогическая» терминология. Узлы, достижимые из узла u, называются потомками узла u (потомки образуют поддерево). Если в дереве существует дуга (u, v), то узел u называется отцом (или родителем) узла v, а узел v называется сыном узла u. Сыновья одного узла называются братьями.