Деревья
Деревья являются одним из интереснейших классов графов, используемых для представления различного рода иерахических структур.
Определение 1.10. Граф
называется деревом, если
- в нем есть одна вершина , в которую не входят ребра; она называется корнем дерева;
- в каждую из остальных вершин входит ровно по одному ребру;
- все вершины достижимы из корня.
На рисунке 2 показан пример дерева
С ориентированными деревьями связана богатая терминология, пришедшая из двух источников: ботаники и области семейных отношений.
Корень - это единственная вершина, в которую не входят ребра, листья - это вершины, из которых не выходят ребра. Путь из корня в лист называется ветвью дерева. Высота дерева - это максимальная из длин его ветвей. Глубина вершины - это длина пути из корня в эту вершину. Для вершины
, подграф дерева
, включающий все достижимые из
вершины и соединяющие их ребра из
, образует поддерево
дерева
с корнем
.
Высота вершины - это высота дерева
. Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.
Рис. 1.2. Дерево G1
Если из вершины
ведет ребро в вершину
, то
называется
отцом , а
-
сыном (в последнее время в ангоязычной литературе употребляется асексульная пара терминов: родитель - ребенок). Из определения дерева непосредственно следует, что у каждой вершины кроме корня имеется единственный отец. Если из вершины
ведет путь в вершину
, то
называется
предком , а
-
потомком . Вершины, у которых общий отец, называются
братьями
или сестрами.
Пример 1.4. В дереве на рис. 1.2
вершина
является корнем, вершины
- листья. Путь
- одна из ветвей дерева
. Вершина
является отцом (родителем) вершин
и
а каждая из этих вершин - ее сыном (ребенком). Между собой вершины
и
являются братьями (сестрами). Глубина
равна 1, а высота - 2. Высота всего дерева
равна 3.
Для деревьев часто удобно использовать следующее индуктивное определение.
Определение 1.11. Определим по индукции класс графов
, называемых деревьями. Одновременно для каждого из них определим выделенную вершину - корень.
- Граф , с единственной вершиной и пустым множеством ребер является деревом (входит в ).
Содержание Назад Вперед