Дерево (теория графов)

У этого термина существуют и другие значения, см. Дерево (значения).

Дерево — это связный ациклический граф.^[1] Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.

Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.^[2]

Формально дерево определяется как конечное множество $T$ одного или более узлов со следующими свойствами:

1. существует один корень дерева $T$
2. остальные узлы (за исключением корня) распределены среди $m\geq 0$ непересекающихся множеств $T_1, ..., T_m$, и каждое из множеств является деревом; деревья $T_1, ..., T_m$ называются поддеревьями данного корня $T$

Связанные определения

• Степень узла — количество исходящих дуг (или, иначе, количество поддеревьев узла).
• Концевой узел (лист, терминальная вершина) — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги).
• Узел ветвления — неконцевой узел.
• Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:

1. уровень корня дерева $T$ равен 0;
2. уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева $T$, содержащего данный узел.

• Дерево с отмеченной вершиной называется корневым деревом.
  • $m$-й ярус дерева $T$ — множество узлов дерева, на уровне $m$ от корня дерева.
  • частичный порядок на вершинах: $u \prec v$, если вершины $u$ и $v$ различны и вершина $u$ лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной $v$.
  • корневое поддерево с корнем $v$ — подграф $\{v\}\cup\{w\mid v<w\}$.
• Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
• Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.

Двоичное дерево

Простое бинарное дерево размера 9 и высоты 3, с корнем значения 2. Это дерево не сбалансировано и не отсортировано.

Термин двоичное дерево (оно же бинарное дерево) имеет несколько значений:

• Неориентированное дерево, в котором степени вершин не превосходят 3.
• Ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2.
• Абстрактная структура данных, используемая в программировании. На двоичном дереве основаны такие структуры данных, как двоичное дерево поиска, двоичная куча, красно-чёрное дерево, АВЛ-дерево, фибоначчиева куча и др.

N-арные деревья

N-арные деревья определяются по аналогии с двоичным деревом. Для них также есть ориентированные и неориентированные случаи, а также соответствующие абстрактные структуры данных.

• N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.
• N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.

Свойства

• Дерево не имеет кратных рёбер и петель.
• Любое дерево с $n$ вершинами содержит $n-1$ ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда $B-P=1$, где $B$ — число вершин, $P$ — число рёбер графа.
• Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственной простой цепью.
• Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
• Любое дерево является двудольным графом. Любое дерево, множество вершин которого не более чем счётное, является планарным графом.
• Для любых трёх вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.

Подсчёт деревьев

Основная статья: Теорема Кэли о числе деревьев

• Число различных деревьев, которые можно построить на $n$ нумерованных вершинах, равно $n^{n-2}$ (Теорема Кэли^[3]).
• Производящая функция

$T(z)=\sum_{n=1}^\infty T_nz^n$

для числа $T_n$ неизоморфных корневых деревьев с $n$ вершинами удовлетворяет функциональному уравнению

$T(z)=z\exp\sum_{r=1}^\infty\frac1r T(z^r)$.

• Производящая функция

$t(z)=\sum_{n=1}^\infty t_nz^n$

для числа $t_n$ неизоморфных деревьев с $n$ вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:

$t(z)=T(z)-\frac12\left(T^2(z)-T(z^2)\right).$

• При $n\to\infty$ верна следующая асимптотика

$t_n\sim C\alpha^n/n^{5/2}$

где $C$ и $\alpha$ определённые константы, $C=0,534948...$, $\alpha=2,95576...$.

Кодирование деревьев

Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой либо вершины, будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем $0$ при движении по ребру в первый раз и $1$ при движении по ребру второй раз (в обратном направлении). Если $m$ — число рёбер дерева, то через $2m$ шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из $0$ и $1$ (код дерева) длины $2m$ позволяет однозначно восстанавливать не только само дерево $D$, но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с $n$ вершинами:

$t_n\le T_n< 2^{2n}$

См. также

• Словарь терминов теории графов
• Лес непересекающихся множеств

Примечания

1. ↑ § 13. Определение дерева // Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.. — М.: Наука, Физматлит, 1990. — С. 53. — 384 с. — 22 000 экз. — ISBN 5-02-013992-0
2. ↑ Альфс Берзтисс. Глава 3. Теория графов. 3.6. Деревья // Структуры данных = A. T. Berztiss. Data structures. Theory and practice. — М.: Статистика, 1974. — С. 131. — 10 500 экз.
3. ↑ Дискретная математика: алгоритмы. Формула Кэли

Литература

• Дональд Кнут. Искусство программирования, том = The Art of Computer Programming, vol. 1. Fundamental Algorithms. — 3-е изд. — М.: Вильямс, 2006. — Т. 1. Основные алгоритмы. — 720 с. — ISBN 0-201-89683-4
• Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — 336 с.