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


Деревья - часть 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,

    +
    -
    - и т.п.)

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




    Начало  Назад  Вперед



    Книжный магазин