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


Деревья


Деревья являются одним из интереснейших классов графов, используемых для представления различного рода иерахических структур.

Определение 1.10. Граф

G=(V,E)
называется деревом, если
  1. в нем есть одна вершина
    r \in E
    , в которую не входят ребра; она называется корнем дерева;
  2. в каждую из остальных вершин входит ровно по одному ребру;
  3. все вершины достижимы из корня.

На рисунке 2 показан пример дерева

G_1

С ориентированными деревьями связана богатая терминология, пришедшая из двух источников: ботаники и области семейных отношений.

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

v \in V
, подграф дерева
T=(V,E)
, включающий все достижимые из
v
вершины и соединяющие их ребра из
E
, образует поддерево
T_v
дерева
T
с корнем
v.
. Высота вершины
v
- это высота дерева
T_v
. Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.

Дерево G1

Рис. 1.2.  Дерево G1

Если из вершины

v
ведет ребро в вершину
w
, то
v
называется отцом
w
, а
w
- сыном
v
(в последнее время в ангоязычной литературе употребляется асексульная пара терминов: родитель - ребенок). Из определения дерева непосредственно следует, что у каждой вершины кроме корня имеется единственный отец. Если из вершины
v
ведет путь в вершину
w
, то
v
называется предком
w
, а
w
- потомком
v
. Вершины, у которых общий отец, называются братьями

или сестрами.

Пример 1.4. В дереве на рис. 1.2

вершина

c
является корнем, вершины
a, b, f, g, k
- листья. Путь
c,d,h,k
- одна из ветвей дерева
G_1
. Вершина
d
является отцом (родителем) вершин
e, g
и
h,
а каждая из этих вершин - ее сыном (ребенком). Между собой вершины
e, g
и
h
являются братьями (сестрами). Глубина
d
равна 1, а высота - 2. Высота всего дерева
G_1
равна 3.

Для деревьев часто удобно использовать следующее индуктивное определение.

Определение 1.11. Определим по индукции класс графов

\mathcal{D}
, называемых деревьями. Одновременно для каждого из них определим выделенную вершину - корень.
  1. Граф
    T_0=(V,E)
    , с единственной вершиной
    V=\{ v\}
    и пустым множеством ребер
    E=\emptyset
    является деревом (входит в
    \mathcal{D}
    ).


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



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