лекции по МОТС / ДИСКРЕТНАЯ МАТЕМАТИКА Графы

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

Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:

существует единственный узел r, полустепень захода которого равна 0, d⁺(r)=0. Он называется корнем ордерева.
полустепень захода всех остальных узлов равна 1, vV \ {r} d⁺(v)=1.
каждый узел достижим из корня, vV \ {r} .

Пример

На рис. 9.5 приведены диаграммы всех различных ориентированных деревьев с 3 узлами, а на рис. 9.6 показаны диаграммы всех различных ориентированных деревьев с 4 узлами.

Рис. 9.5. Ориентированные деревья с 3 узлами

Рис. 9.6. Ориентированные деревья с 4 узлами

ТЕОРЕМА Ордерево обладает следующими свойствами:

q = p-l;
если в ордереве отменить ориентацию ребер, то получится свободное дерево;
в ордереве нет контуров;
для каждого узла существует единственный путь, ведущий в этот узел из корня;
подграф, определяемый множеством узлов, достижимых из узла v, является ордеревом с корнем v (это ордерево называется поддеревом узла v);
если в свободном дереве любую вершину назначить корнем, то получится ордерево.

доказательство

Каждая дуга входит в какой-то узел. Из п. 2 определения 9.2.1 имеем: vV-r d⁺(v)=1, где r – корень. Следовательно, q = p — l.
Пусть G — ордерево, граф G' получен из G забыванием ориентации ребер, r - корень. Тогда v₁,v₂V G'&, следовательно, v₁,v₂ и граф G' связен. Таким образом, учитывая п. 4. теоремы 9.1.2, G' — дерево.
Следует из пункта 2.
От противного. Если бы в G существовали два пути из u в v, то в G' имелся бы цикл.
Пусть G_v — правильный подграф, определяемый множеством узлов, достижимых из v. Тогда , иначе узел v был бы достижим из какого-то узла v'  G_v и, таким образом, в G_v, а значит, и в G имелся бы контур, что противоречит пункту 3. Далее имеем: v’ G_v\{v} d⁺(v') = 1, так как G_v  G. Все вершины G_vдостижимы из v по построению. По определению 9.2.1 получаем, что G_v -ордерево.
Пусть вершина r назначена корнем и дуги последовательно ориентированы «от корня» обходом в глубину. Тогда d⁺(r) = 0 по построению; v  V - r d⁺(v) = 1, так как входящая дуга появляется при первом посещении узла; все узлы достижимы из корня, так как обход в глубину посещает все вершины связного графа. Таким образом, по определению 9.2.1 получаем ордерево. 

ЗАМЕЧАНИЕ

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

Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева - это расстояние от корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.

ЗАМЕЧАНИЕ

Наряду с «растительной» применяется еще и «генеалогическая» терминология. Узлы, достижимые из узла и, называются потомками узла и (потомки образуют поддерево). Если в дереве существует дуга (u, v), то узел и называется отцом (или родителем) узла v, a узел v называется сыном узла u. Сыновья одного узла называются братьями.

Содержание