Дерево (теория графов) - Tree (graph theory)

Деревья
Дерево graph.svg
Помеченное дерево с 6 вершинами и 5 ребрами.
Вершины v
Края v  - 1
Хроматическое число 2, если v > 1
Таблица графиков и параметров

В теории графов , дерево представляет собой неориентированный граф , в котором любые две вершины соединены ровно один путем , или , что эквивалентно в связном ациклическом неориентированном графе. Лес неориентированный граф , в котором любые две вершины соединены не более чем одним путем, или , что эквивалентно ациклического неориентированного графа, или что то же самое в несвязное объединение деревьев.

Polytree (или направленное дерево или ориентированное дерево или одиночно соединение с сетью ) представляет собой ориентированный ациклический граф (DAG) , лежащий в основе которого неориентированный граф является деревом. Polyforest (или направлены лес или ориентированные на лес ) представляет собой ориентированный ациклический граф, лежащий в основе неориентированный граф является лесом.

Различные типы структур данных, называемые деревьями в информатике, имеют базовые графы , которые в теории графов являются деревьями, хотя такие структуры данных обычно являются корневыми деревьями . Укоренившееся дерево может быть направленным, называемым направленным корневым деревом , либо с указанием всех его ребер от корня - в этом случае это называется древовидным или внешним деревом - либо с указанием всех его ребер к корню - в этом случае его называют антидревесневым или древовидным . Само корневое дерево было определено некоторыми авторами как ориентированный граф. Корневым лесом является объединением непересекающихся корневых деревьев. Корневой лес может быть направленным, называемым направленным корневым лесом , либо так, чтобы все его края были направлены от корня в каждом корневом дереве (в этом случае это называется ветвлением или выходящим лесом), либо так , чтобы все его края были направлены к корню. в каждом корневом дереве - в этом случае оно называется « антиветвление» или « в лесу» .

Термин «дерево» был придуман в 1857 году британским математиком Артуром Кэли .

Определения

Дерево

Дерево представляет собой неориентированный граф G , который удовлетворяет любой из следующих эквивалентных условий:

Если G имеет конечное число вершин, скажем n из них, то приведенные выше утверждения также эквивалентны любому из следующих условий:

  • G связна и имеет n - 1 ребро.
  • G соединен, и каждый подграф из G включает в себя по меньшей мере одну вершину с нулем или одним падающих краев. (То есть G связна и 1-вырождена .)
  • G не имеет простых циклов и имеет n - 1 ребро.

Как и повсюду в теории графов, то нулевой порядок-граф (граф без вершин) , как правило , не рассматривается как дерево: в то время как оно бессодержательно подключен в виде графика (любые две вершины могут быть соединены с помощью пути), это не 0 -связно (или даже (−1) -связно) в алгебраической топологии, в отличие от непустых деревьев, и нарушает отношение «на одну вершину больше, чем ребер». Однако его можно рассматривать как лес, состоящий из нулевых деревьев.

Внутренняя вершина (или внутренняя вершина или ветвь вершина ) является вершиной степени , по меньшей мере 2. Аналогичным образом , внешний конец (или внешняя вершина , конечная вершина или лист ) является вершиной степени 1.

Неприводимое дерево (или последовательно уменьшаются дерево ) представляет собой дерево , в котором нет вершин степени 2 (при перечисленной последовательности A000014 в OEIS ).

лес

Лес неориентированный граф , в котором любые две вершины соединены не более одного пути. Эквивалентно лес - это неориентированный ациклический граф, все компоненты связности которого являются деревьями; другими словами, граф состоит из несвязного объединения деревьев. В качестве частных случаев граф нулевого порядка (лес, состоящий из нулевых деревьев), одно дерево и граф без ребер являются примерами лесов. Поскольку для каждого дерева V - E = 1 , мы можем легко подсчитать количество деревьев, находящихся в лесу, вычитая разницу между общим числом вершин и общим количеством ребер. TV - TE = количество деревьев в лесу .

Polytree

Polytree (или направленное дерево или ориентированное дерево или одиночно соединение с сетью ) представляет собой ориентированный ациклический граф (DAG) , лежащий в основе которого неориентированный граф является деревом. Другими словами, если мы заменим его ориентированные ребра неориентированными ребрами, мы получим неориентированный граф, который является одновременно связным и ациклическим.

Некоторые авторы ограничивают фразу «направленное дерево» случаем, когда все ребра направлены к определенной вершине или все направлены от конкретной вершины (см. Древовидность ).

Полифорест

Polyforest (или направлены лес или ориентированные на лес ) представляет собой ориентированный ациклический граф, лежащий в основе неориентированный граф является лесом. Другими словами, если мы заменим его ориентированные ребра неориентированными ребрами, мы получим неориентированный граф, который является ациклическим.

Некоторые авторы ограничивают фразу «направленный лес» случаем, когда все ребра каждого связного компонента направлены к определенной вершине или все направлены от конкретной вершины (см. Ветвление ).

Укоренившееся дерево

Корневое дерево представляет собой дерево , в котором одна вершина была назначена корень . Ребрам корневого дерева может быть назначена естественная ориентация - от корня или по направлению к нему, и в этом случае структура становится ориентированным корневым деревом . Когда направленное корневое дерево имеет ориентацию от корня, оно называется древовидным или выходящим за пределы дерева ; когда он ориентирован на корень, это называется антидревесением или внутренним деревом . Дерева порядка является частичным порядком на вершинах дерева с U < V тогда и только тогда , когда единственный путь от корня до V проходит через U . Корневое дерево T, которое является подграфом некоторого графа G, является нормальным деревом, если концы каждого T-пути в G сравнимы в этом древовидном порядке ( Diestel 2005 , p. 15). Деревья с корнями, часто с дополнительной структурой, такой как упорядочение соседей в каждой вершине, являются ключевой структурой данных в информатике; см. древовидную структуру данных .

В контексте, где деревья обычно имеют корень, дерево без назначенного корня называется свободным деревом .

Размеченное дерево представляет собой дерево , в котором каждая вершина получает уникальную метку. Вершинам помеченного дерева на n вершинах обычно присваиваются метки 1, 2, ..., n . Рекурсивное дерево является меченым корневым деревом , где вершинные метки уважают порядок дерева (то есть, если у < v для двух вершин ˙U и V , то метка ц меньше , чем ярлык V ).

В корневом дереве родительская вершина v - это вершина, соединенная с v на пути к корню; каждая вершина имеет уникального родителя, кроме корня, у которого нет родителя. Ребенок из вершины V является вершиной которой v является родителем. Восходящая из вершины V является любой вершиной , которая является либо родителем V или (рекурсивно) восходящая из родительского V . Потомок вершинного V любая вершина, либо ребенок V или (рекурсивно) потомок любого из детей против . Родственный с вершиной V является любой другой вершиной на дереве , которая имеет тот же родительскую как V . Лист является вершиной без детей. Внутренняя вершина является вершиной , которая не является листом.

Высота вершины в корневом дереве является длиной самого длинного пути вниз к листу из этой вершины. Высота дерева высота корня. Глубина вершины есть длина пути к корню ( корневой путь ). Это обычно требуется при манипулировании различными самобалансирующимися деревьями, в частности деревьями AVL . Корень имеет нулевую глубину, листья имеют нулевую высоту, а дерево только с одной вершиной (следовательно, и корень, и лист) имеют нулевую глубину и высоту. Обычно пустое дерево (дерево без вершин, если они разрешены) имеет глубину и высоту -1.

К-ичных дерево является корневое дерево , в котором каждая вершина имеет не более K детей. 2-арные деревья часто называют бинарными деревьями , а 3-арные деревья иногда называют тройными .

Заказанное дерево

Заказали дерево (или платан ) является корневым деревом , в котором порядок задаются для детей каждой вершины. Это называется «плоским деревом», потому что порядок дочерних элементов эквивалентен вложению дерева в плоскость с корнем вверху и дочерними элементами каждой вершины ниже этой вершины. Если дано вложение корневого дерева в плоскость, если зафиксировать направление дочерних элементов, скажем слева направо, то вложение задает порядок дочерних элементов. И наоборот, для упорядоченного дерева и обычного рисования корня вверху дочерние вершины в упорядоченном дереве можно рисовать слева направо, что дает по существу уникальное плоское вложение.

Характеристики

  • Каждое дерево - двудольный граф . Граф двудольный тогда и только тогда, когда он не содержит циклов нечетной длины. Поскольку дерево вообще не содержит циклов, оно двудольное.
  • Каждое дерево - это медианный граф .
  • Каждое дерево со счетным числом вершин является плоским графом .
  • Каждый связный граф G допускает остов , который является деревом , которое содержит все вершины G и ребро которого являются ребрами G .
  • Каждый связный граф со счетным числом вершин допускает нормальное остовное дерево ( Diestel 2005 , Prop. 8.2.4).
  • Существуют связные графы с несчетным числом вершин, не допускающие нормального остовного дерева ( Diestel 2005 , Prop. 8.5.2).
  • Каждое конечное дерево с n вершинами и n > 1 имеет не менее двух конечных вершин (листьев). Это минимальное количество листьев характерно для графов путей ; максимальное число n - 1 достигается только звездными графами . Количество листов - не менее максимальной степени вершины.
  • Для любых трех вершин в дереве три пути между ними имеют ровно одну общую вершину (эта вершина называется медианой этих трех вершин).
  • У каждого дерева есть центр, состоящий из одной или двух смежных вершин. Центр - это средняя вершина или две средние вершины на каждом самом длинном пути. Аналогично, каждое дерево с n вершинами имеет центроид, состоящий из одной или двух смежных вершин. В первом случае удаление вершины разбивает дерево на поддеревья с числом вершин менее n / 2. Во втором случае удаление ребра между двумя центроидными вершинами разбивает дерево на два поддерева ровно с n / 2 вершинами.

Перечисление

Маркированные деревья

Формула Кэли утверждает, что существует n n −2 деревьев на n помеченных вершинах. В классическом доказательстве используются последовательности Прюфера , которые, естественно, показывают более сильный результат: количество деревьев с вершинами 1, 2, ..., n степеней d 1 , d 2 , ..., d n соответственно является полиномиальным коэффициентом

Более общая проблема состоит в подсчете остовных деревьев в неориентированном графе , что решается теоремой о матричном дереве . (Формула Кэли является частным случаем остовных деревьев в полном графе .) Аналогичная проблема подсчета всех поддеревьев независимо от размера является # P-полной в общем случае ( Jerrum (1994) ).

Немаркированные деревья

Подсчитать количество свободных деревьев без меток - более сложная задача. Замкнутая формула для числа t ( n ) деревьев с n вершинами с точностью до изоморфизма графов неизвестна. Первые несколько значений t ( n ):

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159,… (последовательность A000055 в OEIS ).

Оттер (1948) доказал асимптотическую оценку

со значениями C и α, которые известны как приблизительно 0,534949606 ... и 2,95576528565 ... (последовательность A051491 в OEIS ), соответственно. (Здесь f ~ g означает, что lim n → ∞ f / g = 1. ) Это следствие его асимптотической оценки числа r ( n ) немаркированных корневых деревьев с n вершинами:

с D около 0,43992401257 ... и тем же α, что и выше (см. Knuth (1997) , глава 2.3.4.4 и Flajolet & Sedgewick (2009) , глава VII.5, стр. 475).

Первые несколько значений r ( n ):

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973,… (последовательность A000081 в OEIS )

Виды деревьев

  • Путь графа (или линейный граф ) состоит из п вершин , расположенных в линию, так что вершины я и я + 1 соединены ребром для я = 1, ..., п -1.
  • Звездное дерево состоит из центральной вершины называется корнем и несколько путей графов , прикрепленных к нему. Более формально дерево называется звездным, если у него ровно одна вершина степени больше 2.
  • Дерево звезды представляет собой дерево , которое состоит из одной внутренней вершины (и п -1 листьев). Другими словами, звездное дерево порядка n - это дерево порядка n с максимально возможным количеством листьев.
  • Гусеница дерево представляет собой дерево , в котором все вершины находятся в пределах расстояния 1 центрального пути подграфа.
  • Омары дерево представляет собой дерево , в котором все вершины находятся в пределах расстояния 2 центрального пути подграфа.
  • Регулярное дерево степени д есть бесконечное дерево с д ребер в каждой вершине. Они возникают как Кейли графы из свободных групп , и в теории Титс .

Смотрите также

Примечания

использованная литература

дальнейшее чтение