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

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

Дерево — это связный ациклический граф.[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\}.
    • В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.
  • Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
  • Несводимым называется дерево, в котором нет вершин степени 2.
  • Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.

Двоичное дерево[править | править вики-текст]

Простое бинарное дерево размера 9 и высоты 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. Дискретная математика: алгоритмы. Формула Кэли

Литература[править | править вики-текст]