Пример 3.1

На рисунке 3.1. приведены все возможные 4- вершинные ордеревья. Все другие 4-вершинные деревья являются изоморфными, этим ордеревьям.

 

Рис. 3.1. 4-х вершинные ориентированные деревья

 

Ориентированное дерево T = (V, X) с n вершинами и m дугами обладает рядом свойств:

        m = n – 1. Согласно определению ордерева, для любой вершины v  V\{s} полустепень захода равна: ^– (s) = 1, следовательно,

= n – 1.

        Граф G = (V, E) ассоциированный ордереву T = (V, X), является деревом. Так как ассоциированный граф сохраняет соотношение между количеством вершин и ребер.

 Всякое n-вершинное дерево может быть ориентированно не более чем  n способами. Это можно осуществить путем выбора корневой вершины и заменой ребер дугами, направленными от корня, при этом все ребра, инцидентные корневой вершине, заменяются исходящими дугами; далее поступаем согласно определению ордерева.

        В ордереве отсутствуют простые контуры. Это следует из того, что ассоциированное ему  дерево не имеет циклов.    

        Поддерево T(v) ордерева T = (V, X), порожденное множеством вершин, достижимых из вершины v  V, является ориентированным деревом. Это непосредственно следует из определения ордерева.

Цепь из корня в лист ордерева называется ветвью.

Рис. 3.2. Диаграмма дерева (T, s)

 

Отношение односторонней связности на множестве вершин V  дерева (T, s) является отношением частичного порядка, наибольшим элементом которого будет корень дерева (s), листья дерева – минимальные элементы упорядоченного множества (T, ).  Наибольшее расстояние (длина простой цепи) от корня до листьев дерева T (определяемое самой длинной ветвью) называется высотой ордерева  h(T). Между высотой h ориентированного дерева T  и числом его листьев существует связь, выражающаяcя в том, что количество листьев ордерева не превосходит величины p^h, где  p =.  

Корневые деревья  (T, s)  изображается в виде диаграмм похожих на диаграммы Хассе для упорядоченных множеств (см. рис.3.2.).

Если      t w и t ≠ w, то t - предок w, а  w - потомок  t . Можно показать, что среди предков вершины u имеется наименьший предок (вершина) x, он называется отцом вершины u, а вершина u в свою очередь –  сыном x. Для произвольной вершины v через   обозначается v-поддерево с корнем v, остальными вершинами которого  являются все потомки вершины v.

Понятие уровня в дереве и ордереве отличаются. В ордереве корневая вершина имеет нулевой уровень, вершины, удаленные от корня на расстояние, равное k, k = 0, 1, 2, …, имеют уровень k. Из определения следует, что наибольший уровень ордерева (T, s) равен h(T). Вершины одного уровня образуют ярус ордерева.

Заметим, что, если корни двух поддеревьев несравнимы на множестве (T, ), то и никакие  две вершины этих поддеревьев несравнимы на этом множестве. Этот вывод справедлив также для любых, не пересекающихся поддеревьев. 

Пример 3.2

На рис.3.2: цепь, соединяющая вершину s с вершиной w, является ветвью; высота дерева (T, s)  h(T) = 4; для вершины v вершина t – предок, вершина u – отец, а вершина w – сын;  вершины r, w являются листьями; вершины r и u принадлежат одному ярусу.

Бинарное ориентированное дерево.

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

Утверждение 3.5. Пусть B - полное бинарное дерево высоты h, тогда оно имеет ровно 2^h листьев.

Доказательство проведем индукцией по высоте дерева h.

1. Если высота дерева  h = 0, то оно имеет единственную вершину, которая является и корнем, и листом, т.е. 2⁰ = 1. Поскольку в бинарном полном ордереве полустепень исхода любой  вершины за исключением листьев  равна 2, то число листьев ордерева с высотой h = 1 будет равно   2⁰2 = 2¹.

2. Пусть утверждение 3.5. справедливо для бинарного полного ордерева c высотой равной  h – 1, т.е. число его листьев равно 2^h-1.

3. Тогда дерево B высоты h имеет  2^h-1 2 = 2^h листьев.

Утверждение 3.5. доказано.

Теорема 3.1 о высоте бинарного ориентированного дерева с заданным числом листьев. Бинарное ориентированное дерево с q листьями имеет высоту, не меньшую чем log₂q .

            Доказательство. Пусть рассматриваемое бинарное дерево имеет высоту h. Достроим его до бинарного полного дерева. Согласно утверждению 3.5 оно имеет  2^h листьев. Тогда для числа  листьев исходного бинарного дерева справедливо неравенство q  ≤ 2^h. Следовательно, log₂q  ≤ h.

            Результат доказанной теоремы имеет важное значение в оценке сложности алгоритмов (см. раздел 3.3).