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

Вершина

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

Пусть графы

с корнями

принадлежат

, а

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

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

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

, где

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

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

нет.

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

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

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

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

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

- и т.п.)

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

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