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

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

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

Связанные определения Степень вершины — количество инцидентных ей ребер. Концевой узел (лист, терминальная вершина) — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги). Узел ветвления — неконцевой узел. Дерево с отмеченной вершиной называется корневым деревом. -й ярус дерева  — множество узлов дерева, на уровне от корня дерева. частичный порядок на вершинах: , если вершины и различны и вершина лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной . корневое поддерево с корнем  — подграф . В контексте, где дерево предполагается имеющим корень, дерево без выделенного корня называется свободным. Уровень узла — длина пути от корня до узла. Можно определить рекурсивно: уровень корня дерева равен 0; уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева , содержащего данный узел.

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

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

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

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

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

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

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

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

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

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

для числа неизоморфных деревьев с вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:

При верна следующая асимптотика

где и определённые константы, , .

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

Код Прюфера сопоставляет произвольному конечному дереву с вершинами последовательность из чисел от до с возможными повторениями. Например дерево на рисунке имеет код Прюфера (4,4,4,5). Между деpевьями с помеченными вершинами и их кодами Прюфера существует взаимно однозначное соответствие. Из кода Прюфера выводится формула Кэли. Дерево можно задать в виде стpоки, содержащей символы, помечающие вершины деpева, а также открывающие и закрывающие кpуглые скобки. Между деpевьями и их линейными скобочными записями существует взаимно однозначное соответствие.

См. также Глоссарий теории графов Лес непересекающихся множеств Список структур данных (деревья)

Примечания

Литература

Категория:Теория графов Категория:Деревья (структуры данных) *