Деревья - часть 2

Вершина

$v$

называется корнем этого дерева.

Пусть графы

$T_1=(V_1,E_1), \ldots , T_k= (V_k, E_k)$

с корнями

$r_1 \in V_1, \ldots, r_k \in V_k$

принадлежат

$\mathcal{D}$

, а

$r_0$

- новая вершина, т.е.

$r_0 \notin \bigcup_{i=1}^k V_i$

. Тогда классу

$\mathcal{D}$

принадлежит также следующий граф

$T = (V, E)$

, где

$V= \{ r_0\} \cup \bigcup_{i=1}^k V_i$

$E = \{ (r_0, r_i)\ |\ i=1, \ldots , k\} \cup \bigcup_{i=1}^k E_i$

. Корнем этого дерева является вершина

$r_0$

Других графов в классе

$\mathcal{D}$

нет.

Рисунок 1.3 иллюстрирует это определение.

Рис. 1.3. Индуктивное определение ориентированных деревьев

Определения ориентированных деревьев 1.10 и 1.11 эквивалентны.

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

Дерево называется бинарным или двоичным , если у каждой его внутренней вершины имеется не более двух сыновей, причем ребра, ведущие к ним помечены двумя разными метками (обычно используются метки из пар: "левый" - "правый", 0 - 1,

$+$

$-$

- и т.п.)

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

Содержание Назад Вперед