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

Материал из Википедии — свободной энциклопедии

В теории графов, дерево — связный неориентированный граф, не содержащий циклов.

Содержание

1 Связанные определения
2 Двоичное дерево
3 N-арные деревья
4 Свойства
5 Подсчёт деревьев
6 Кодировка деревьев
7 См. также

[править] Связанные определения

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