Введение
Неориентированный, связный и ациклический граф
В теории графов дерево — это неориентированный граф, в котором любые две вершины соединены ровно одним путём, или, эквивалентно, связный ациклический неориентированный граф. Лес — это неориентированный граф, в котором любые две вершины соединены не более чем одним путём, или, эквивалентно, ациклический неориентированный граф, или, эквивалентно, дизъюнктное объединение деревьев. Направленное дерево, ориентированное дерево, полидерево или односвязная сеть — это направленный ациклический граф (DAG), базовый неориентированный граф которого является деревом. Полилес (или направленный лес, или ориентированный лес) — это направленный ациклический граф, базовый неориентированный граф которого является лесом. Различные виды структур данных, называемых деревьями в информатике, имеют базовые графы, являющиеся деревьями в теории графов, хотя такие структуры данных обычно являются корневыми деревьями. Корневое дерево может быть ориентированным, называемым ориентированным корневым деревом, при этом все его рёбра направлены от корня — в этом случае оно называется арборесценцией или исходящим деревом — или все его рёбра направлены к корню — в этом случае оно называется антиарборесценцией или входящим деревом. Само корневое дерево некоторыми авторами определяется как ориентированный граф. Корневой лес — это дизъюнктное объединение корневых деревьев. Корневой лес может быть ориентированным, называемым ориентированным корневым лесом, при этом все его рёбра направлены от корня в каждом корневом дереве — в этом случае он называется ветвящимся лесом — или все его рёбра направлены к корню в каждом корневом дереве — в этом случае он называется антиветвящимся лесом. Термин «дерево» был введен в 1857 году британским математиком Артуром Кейли.
Лес
Лес — это ненаправленный граф, в котором любые две вершины соединены не более чем одним путём. Эквивалентно, лес — это ненаправленный ациклический граф, все связные компоненты которого являются деревьями; иными словами, граф состоит из непересекающегося объединения деревьев. В качестве частных случаев, граф нулевого порядка (лес, состоящий из нуля деревьев), отдельное дерево и граф без рёбер являются примерами лесов. Поскольку для каждого дерева выполняется равенство 1 = V − E, мы можем легко подсчитать количество деревьев в лесу, вычислив разность между общим числом вершин и общим числом рёбер. 1 = V − E = количество деревьев в лесу.
Полидрево
Многодеревья с ветвлением 2 часто называют бинарными деревьями, а деревья с ветвлением 3 иногда называют троичными деревьями.
Заказанное дерево
Упорядоченное дерево (также известное как плоское дерево или позиционное дерево) — это корневое дерево, в котором задан порядок дочерних элементов каждой вершины. Оно называется «плоским деревом», поскольку порядок дочерних элементов эквивалентен вложению дерева в плоскость, с корнем вверху и дочерними элементами каждой вершины ниже этой вершины. Если задано вложение корневого дерева в плоскость и зафиксировано направление дочерних элементов, например, слева направо, то вложение определяет порядок дочерних элементов. И наоборот, для заданного упорядоченного дерева, при традиционном изображении корня вверху, дочерние вершины можно нарисовать слева направо, что приводит к по существу единственному плоскому вложению.
Свойства
Каждое дерево является двудольным графом. Граф является двудольным тогда и только тогда, когда он не содержит циклов нечётной длины. Поскольку дерево не содержит циклов вообще, оно является двудольным. Каждое дерево с лишь счётным числом вершин является планарным графом. Каждый связный граф G допускает остовное дерево, которое является деревом, содержащим каждую вершину G, а его рёбра являются рёбрами G. Более специфические типы остовных деревьев, существующие в каждом связном конечном графе, включают деревья поиска в глубину и деревья поиска в ширину. Обобщая существование деревьев поиска в глубину, каждый связный граф с лишь счётным числом вершин имеет дерево Тремо. Однако некоторые несчётные графы порядка не имеют такого дерева. Каждое конечное дерево с n вершинами, при n > 1, имеет по крайней мере две терминальные вершины (листья). Это минимальное число листьев характерно для путевых графов; максимальное число, n − 1, достигается только звёздными графами. Число листьев не меньше максимальной степени вершины. Для любых трёх вершин в дереве три пути между ними имеют ровно одну общую вершину. В более общем смысле, вершина в графе, принадлежащая трём кратчайшим путям между тремя вершинами, называется медианой этих вершин. Поскольку любые три вершины в дереве имеют уникальную медиану, каждое дерево является медианным графом. У каждого дерева есть центр, состоящий из одной вершины или двух смежных вершин. Центр — это средняя вершина или две средние вершины в любом самом длинном пути. Аналогично, каждое дерево с n вершинами имеет центроид, состоящий из одной вершины или двух смежных вершин. В первом случае удаление вершины разделяет дерево на поддеревья с числом вершин меньше n/2. Во втором случае удаление ребра между двумя центроидными вершинами разделяет дерево на два поддерева ровно с n/2 вершинами. Максимальные клики дерева — это именно его рёбра, что подразумевает, что класс деревьев имеет мало клик.
Обозначенные деревья
Формула Кейли утверждает, что существует n^(n-2) деревьев на n помеченных вершинах. Классическое доказательство использует последовательности Прюфера, которые естественным образом показывают более сильный результат: число деревьев с вершинами 1, 2, ..., n степеней d_1, d_2, ..., d_n соответственно, равно мультиномиальному коэффициенту.
Более общая задача — подсчет остовных деревьев в неориентированном графе, которая решается теоремой о матрице дерева. (Формула Кейли является частным случаем остовных деревьев в полном графе.) Аналогичная задача подсчета всех поддеревьев, независимо от размера, является #P-полной в общем случае.
Типы деревьев
Граф пути (или линейный граф) состоит из n вершин, расположенных в линию, так что вершины i и i + 1 соединены ребром для 1 ≤ i ≤ n – 1. Звездоподобное дерево состоит из центральной вершины, называемой корнем, и нескольких графов пути, прикрепленных к нему. Более формально, дерево является звездоподобным, если у него ровно одна вершина степени больше 2. Звездное дерево — это дерево, состоящее из одной внутренней вершины (и n – 1 листьев). Другими словами, звездное дерево порядка n — это дерево порядка n с максимально возможным количеством листьев. Гусеничное дерево — это дерево, в котором все вершины находятся на расстоянии не более 1 от центрального подграфа пути. Ома́рное дерево — это дерево, в котором все вершины находятся на расстоянии не более 2 от центрального подграфа пути. Регулярное дерево степени d — это бесконечное дерево с d ребрами, выходящими из каждой вершины. Они возникают как графы Кейли свободных групп и в теории зданий Титса. В статистической механике они известны как решетки Бетэ.