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

• Степень вершины — количество инцидентных ей ребер.

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

• Узел ветвления — неконцевой узел.

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

• Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:

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

• Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.

• Несводимым называется дерево, в котором нет вершин степени 2.

• Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
• Центроид — вершина, при удалении которой размеры получившихся компонент связности не превышают ${\displaystyle {\dfrac {n}{2}}}$ (половины размера исходного дерева).

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

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

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

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

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

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

${\displaystyle T(z)=\sum _{n=1}^{\infty }T_{n}z^{n}}$

для числа ${\displaystyle T_{n}}$ неизоморфных корневых деревьев с ${\displaystyle n}$ вершинами удовлетворяет функциональному уравнению:

${\displaystyle T(z)=z\exp \sum _{r=1}^{\infty }{\frac {1}{r}}T(z^{r})}$.

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

${\displaystyle t(z)=\sum _{n=1}^{\infty }t_{n}z^{n}}$

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

${\displaystyle t(z)=T(z)-{\frac {1}{2}}\left(T^{2}(z)-T(z^{2})\right).}$

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

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

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

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

  ${\displaystyle t_{n}\leq T_{n}<2^{2n}}$

• Код Прюфера сопоставляет произвольному конечному дереву с ${\displaystyle n}$ вершинами последовательность из ${\displaystyle n-2}$ чисел от ${\displaystyle 1}$ до ${\displaystyle n}$ с возможными повторениями. Например дерево на рисунке имеет код Прюфера (4,4,4,5). Между деpевьями с помеченными вершинами и их кодами Прюфера существует взаимно однозначное соответствие. Из кода Прюфера выводится формула Кэли.

• Дерево можно задать в виде стpоки, содержащей символы, помечающие