Деревья

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

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

$G=(V,E)$

называется деревом, если

в нем есть одна вершина
$r \in E$
, в которую не входят ребра; она называется корнем дерева;
в каждую из остальных вершин входит ровно по одному ребру;
все вершины достижимы из корня.

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

$G_1$

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

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

$v \in V$

, подграф дерева

$T=(V,E)$

, включающий все достижимые из

$v$

вершины и соединяющие их ребра из

$E$

, образует поддерево

$T_v$

дерева

$T$

с корнем

$v.$

. Высота вершины

$v$

- это высота дерева

$T_v$

. Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.

Рис. 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}$

, называемых деревьями. Одновременно для каждого из них определим выделенную вершину - корень.

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

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