Введение в схемы, автоматы и алгоритмы


             

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


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


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


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

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

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

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

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


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