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

10.04.2022

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

Лес — множество деревьев.

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

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

  • Степень вершины — количество инцидентных ей ребер.
  • Концевой узел (лист, терминальная вершина) — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги).
  • Узел ветвления — неконцевой узел.
  • Дерево с отмеченной вершиной называется корневым деревом.
    • m {displaystyle m} -й ярус дерева T {displaystyle T} — множество узлов дерева, на уровне m {displaystyle m} от корня дерева.
    • частичный порядок на вершинах: u ≺ v {displaystyle uprec v} , если вершины u {displaystyle u} и v {displaystyle v} различны и вершина u {displaystyle u} лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной v {displaystyle v} .
    • корневое поддерево с корнем v {displaystyle v} — подграф { v } ∪ { w ∣ v < w } {displaystyle {v}cup {wmid v<w}} .
    • В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным.
  • Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:
  • уровень корня дерева T {displaystyle T} равен 0;
  • уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева T {displaystyle T} , содержащего данный узел.
    • Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
    • Несводимым называется дерево, в котором нет вершин степени 2.
    • Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
    • Центроид — вершина, при удалении которой размеры получившихся компонент связности не превышают n 2 {displaystyle {dfrac {n}{2}}} (половины размера исходного дерева)

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

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

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

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

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

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

    Свойства

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

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

    • Число различных деревьев, которые можно построить на n {displaystyle n} нумерованных вершинах, равно n n − 2 {displaystyle n^{n-2}} (Теорема Кэли).
    • Производящая функция
    T ( z ) = ∑ n = 1 ∞ T n z n {displaystyle T(z)=sum _{n=1}^{infty }T_{n}z^{n}} для числа T n {displaystyle T_{n}} неизоморфных корневых деревьев с n {displaystyle n} вершинами удовлетворяет функциональному уравнению T ( z ) = z exp ⁡ ∑ r = 1 ∞ 1 r T ( z r ) {displaystyle T(z)=zexp sum _{r=1}^{infty }{frac {1}{r}}T(z^{r})} .
    • Производящая функция
    t ( z ) = ∑ n = 1 ∞ t n z n {displaystyle t(z)=sum _{n=1}^{infty }t_{n}z^{n}} для числа t n {displaystyle t_{n}} неизоморфных деревьев с n {displaystyle n} вершинами можно представить с помощью перечисляющего ряда для корневых деревьев: t ( z ) = T ( z ) − 1 2 ( T 2 ( z ) − T ( z 2 ) ) . {displaystyle t(z)=T(z)-{frac {1}{2}}left(T^{2}(z)-T(z^{2}) ight).}
    • При n → ∞ {displaystyle n o infty } верна следующая асимптотика
    t n ∼ C α n / n 5 / 2 {displaystyle t_{n}sim Calpha ^{n}/n^{5/2}} где C {displaystyle C} и α {displaystyle alpha } определённые константы, C = 0 , 534948... {displaystyle C=0,534948...} , α = 2 , 95576... {displaystyle alpha =2,95576...} .

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

    • Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой либо вершины будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем 0 {displaystyle 0} при движении по ребру в первый раз и 1 {displaystyle 1} при движении по ребру второй раз (в обратном направлении). Если m {displaystyle m} — число рёбер дерева, то через 2 m {displaystyle 2m} шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из 0 {displaystyle 0} и 1 {displaystyle 1} (код дерева) длины 2 m {displaystyle 2m} позволяет однозначно восстанавливать не только само дерево D {displaystyle D} , но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с n {displaystyle n} вершинами: t n ≤ T n < 2 2 n {displaystyle t_{n}leq T_{n}<2^{2n}}
    • Код Прюфера сопоставляет произвольному конечному дереву с n {displaystyle n} вершинами последовательность из n − 2 {displaystyle n-2} чисел от 1 {displaystyle 1} до n {displaystyle n} с возможными повторениями. Например дерево на рисунке имеет код Прюфера (4,4,4,5). Между деpевьями с помеченными вершинами и их кодами Прюфера существует взаимно однозначное соответствие. Из кода Прюфера выводится формула Кэли.
    • Дерево можно задать в виде стpоки, содержащей символы, помечающие вершины деpева, а также открывающие и закрывающие кpуглые скобки. Между деpевьями и их линейными скобочными записями существует взаимно однозначное соответствие.