Ориентированные деревья

Определение. Ориентированным деревом (или ордеревом) называется ориентированный граф без циклов, во все вершины которого, кроме одной, входит ровно одна дуга. Единственная вершина, из которой дуги только выходят, называется корнем дерева. Остальные вершины называются узлами дерева.

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

На рис. 5 приведены диаграммы всех неизоморфных ориентированных деревьев с тремя и четырьмя вершинами.

Утверждение. Всякое дерево можно ориентировать.

Доказательство. Выберем произвольную вершину и дерева и назначим ее корнем. Ребра, инцидентные вершине и, ориентируем от вершины и. Далее повторим эту процедуру: войдя в некоторую вершину v по дуге, ориентируем все остальные ребра, инцидентные вершине v, от вершины v. Так как дерево не содержит циклов, ориентация ребер не приведет к противоречиям.

На рис. 6 приведен пример ориентированного дерева. Вершина, выбранная корнем, обозначена двойным кружком.

Выбор корня однозначно определяет ориентацию дерева. Поэтому каждому дереву с р вершинами соответствует р ориентированных деревьев.

Висячая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой ордерева. Расстояние от корня до некоторой вершины называется уровнем вершины. Сам корень имеет уровень 0. Вершины одного уровня образуют ярус дерева.

 

Другая терминология.

Вершины, достижимые из вершины и, называются потомками вершины и. Если в дереве существует дуга , то вершина и называется отцом вершины v, а вершина v называется сыном вершины и. Сыновья одного отца называются братьями.

Замечание. При изображении ориентированных деревьев принято помещать корень наверху и все стрелки дуг ориентировать сверху вниз, что избавляет от необходимости изображать эти стрелки.

На рис. 7 показано дерево с рис. 6, изображенное в соответствии с этими правилами. Вершины дерева разбиты на 4 яруса. Нулевой ярус содержит корень дерева. В первом и втором ярусах по 4 вершины, в третьем ярусе 8 вершин.