Дерево (граф)

В теории графов, дерево — связный (ориентированный или неориентированный) граф, не содержащий циклов (для любой вершины есть один и только один способ добраться до любой другой вершины). Древовидная структура — тип организации, в котором каждый объект связан с хотя бы одним другим.

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

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

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

• Степень узла — количество поддеревьев узла
• Концевой узел (лист) — узел со степенью нуль.
• Узел ветвления — неконцевой узел.
• Уровень узла определяется рекурсивным образом:

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

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

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

Пример дерева

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

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

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

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

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

Свойства

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

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

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

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

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

$T(z)=x\exp\sum_{r=1}^\infty\frac1r T(x^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 и α определённые константы, C = 0,534948..., α = 2,95576....

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

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

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

См. также

• Граф
• Ориентированный граф
• Двоичное дерево
• Словарь терминов теории графов
• Лес непересекающихся множеств

Книги

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