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

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

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

А многодерево^[3] (или же направленное дерево^[4] или же ориентированное дерево^[5][6] или же односвязная сеть^[7]) это ориентированный ациклический граф (DAG), чей базовый неориентированный граф является деревом. А полифорест (или же направленный лес или же ориентированный лес) является ориентированным ациклическим графом, базовым неориентированным графом которого является лес.

Различные виды структуры данных упоминается как деревья в Информатика имеют лежащие в основе графики которые являются деревьями в теории графов, хотя такие структуры данных обычно укоренившиеся деревья. Укоренившееся дерево может быть направлено, называемое направленное корневое дерево,^[8][9] либо сделать так, чтобы все его края были направлены от корня - в этом случае это называется древовидность^[4][10] или же вне дерева^[11][12]- или сделать так, чтобы все его края были направлены к корню - в этом случае это называется антидревесение^[13] или же в дереве.^[11][14] Само корневое дерево было определено некоторыми авторами как ориентированный граф.^[15][16][17] А укорененный лес несвязное объединение корневых деревьев. Корневой лес может быть направлен, называемый направленный укорененный лес, либо сделать так, чтобы все его края были направлены в сторону от корня в каждом корневом дереве - в этом случае это называется разветвление или же вне леса- или сделать так, чтобы все его края указывали на корень в каждом корневом дереве - в этом случае это называется анти-ветвление или же в лесу.

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

Определения

Дерево

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

• грамм является связаны и ациклический (не содержит циклов).
• грамм является ациклическим, и простой цикл образуется, если есть край добавлен к грамм.
• грамм связан, но станет отключен если какой-либо единственный край удален из грамм.
• грамм связна и 3-вершина полный график K₃ это не незначительный из грамм.
• Любые две вершины в грамм могут быть связаны уникальным простой путь.

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

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

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

An внутренняя вершина (или же внутренняя вершина или же вершина ветки) является вершиной степень не менее 2. Аналогично внешняя вершина (или же внешняя вершина, конечная вершина или же лист) - вершина степени 1.

An неприводимое дерево (или же последовательное редуцированное дерево) - дерево, в котором нет вершины степени 2 (пронумерованной в последовательности A000014 в OEIS ).^[19]

лес

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

Политри

А многодерево^[3] (или же направленное дерево^[4] или же ориентированное дерево^[5][6] или же односвязная сеть^[7]) это ориентированный ациклический граф (DAG), чей базовый неориентированный граф является деревом. Другими словами, если мы заменим его ориентированные ребра неориентированными ребрами, мы получим неориентированный граф, который является одновременно связным и ациклическим.

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

Полифорест

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

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

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

А укоренившееся дерево дерево, в котором одна вершина обозначена как корень.^[20] Ребрам корневого дерева можно присвоить естественную ориентацию, либо далеко от или же к корень, и в этом случае структура становится направленное корневое дерево. Когда направленное корневое дерево имеет ориентацию от корня, оно называется древовидность^[4] или же вне дерева;^[11] когда он ориентирован на корень, он называется антидревесение или же в дереве.^[11] В древовидный порядок это частичный заказ на вершинах дерева с ты < v тогда и только тогда, когда уникальный путь от корня до v проходит через ты. Укоренившееся дерево, которое подграф некоторого графа грамм это нормальное дерево если концы каждого края в грамм сравнимы в этом древовидном порядке, если эти концы являются вершинами дерева (Дистель 2005, п. 15). Деревья с корнями, часто с дополнительной структурой, такой как упорядочение соседей в каждой вершине, являются ключевой структурой данных в информатике; видеть древовидная структура данных.

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

А маркированное дерево дерево, в котором каждой вершине присвоена уникальная метка. Вершины помеченного дерева на п вершинам обычно присваиваются метки 1, 2, ..., п. А рекурсивное дерево является помеченным корневым деревом, в котором метки вершин соответствуют порядку дерева (т. е. если ты < v для двух вершин ты и v, то метка ты меньше, чем этикетка v).

В корневом дереве родитель вершины v это вершина, соединенная с v на дорожка в корень; каждая вершина имеет уникального родителя, кроме корня, у которого нет родителя.^[20] А ребенок вершины v вершина которого v родитель.^[20] An восходящий вершины v любая вершина, которая является либо родителем v или является (рекурсивно) восходящим элементом родительского элемента v. А потомок вершины v любая вершина, которая является дочерним элементом v или является (рекурсивно) потомком любого из потомков v. А брат или сестра к вершине v любая другая вершина на дереве, имеющая того же родителя, что и v.^[20] А лист вершина без детей.^[20] An внутренняя вершина это вершина, которая не является листом.^[20]

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

А к-арное дерево является корневым деревом, в каждой вершине которого не более k дети.^[21] 2-арные деревья часто называют бинарные деревья, а 3-арные деревья иногда называют тройные деревья.

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

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

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

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

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

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

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

${ displaystyle {n-2 select d_ {1} -1, d_ {2} -1, ldots, d_ {n} -1}.}$

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

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

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

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

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

${ displaystyle t (n) sim C alpha ^ {n} n ^ {- 5/2} quad { text {as}} n to infty,}$

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

${ displaystyle r (n) sim D alpha ^ {n} n ^ {- 3/2} quad { text {as}} n to infty,}$

с D около 0,43992401257 ... и то же самое α как указано выше (ср. Кнут (1997), гл. 2.3.4.4 и Флажолет и Седжвик (2009), гл. VII.5, стр. 475).

Первые несколько значений р(п) находятся^[23]

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

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

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

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

• Гипердерево
• Древовидная структура
• Дерево (структура данных)
• Древо решений
• Псевдолес
• Бинарное дерево без корня

Примечания

Рекомендации

• Бендер, Эдвард А .; Уильямсон, С. Гилл (2010), Списки, решения и графики. Знакомство с вероятностью
• Дасгупта, Санджой (1999), «Обучающие многодеревья», в Proc. 15-я конференция по неопределенности в искусственном интеллекте (UAI 1999), Стокгольм, Швеция, июль – август 1999 г. (PDF), стр. 134–141.
• Део, Нарсинг (1974), Теория графов с приложениями в инженерии и информатике (PDF), Энглвуд, Нью-Джерси: Прентис-Холл, ISBN  0-13-363473-6
• Харари, Фрэнк; Принс, Герт (1959), «Число гомеоморфно несводимых деревьев и других видов», Acta Mathematica, 101 (1–2): 141–162, Дои:10.1007 / BF02559543, ISSN  0001-5962
• Харари, Фрэнк; Самнер, Дэвид (1980), "Дихроматическое число ориентированного дерева", Журнал комбинаторики, информации и системных наук, 5 (3): 184–187, МИСТЕР  0603363.
• Kim, Jin H .; Перл, Иудея (1983), «Вычислительная модель для причинно-следственных и диагностических рассуждений в машинах вывода», в Proc. 8-я Международная совместная конференция по искусственному интеллекту (IJCAI 1983), Карлсруэ, Германия, август 1983 г. (PDF), стр. 190–193.
• Ли, Ганг (1996), «Поколение деревьев с корнями и свободных деревьев», РС. Диссертация, факультет компьютерных наук, Университет Виктории, Британская Колумбия, Канада (PDF), п. 9.
• Симион, Родика (1991), «Деревья с 1-факторами и ориентированные деревья», Дискретная математика, 88 (1): 93–104, Дои:10.1016 / 0012-365X (91) 90061-6, МИСТЕР  1099270.

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

• Дистель, Рейнхард (2005), Теория графов (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN  978-3-540-26183-4.
• Флажолет, Филипп; Седжвик, Роберт (2009), Аналитическая комбинаторика, Издательство Кембриджского университета, ISBN  978-0-521-89806-5
• "Дерево", Энциклопедия математики, EMS Press, 2001 [1994]
• Кнут, Дональд Э. (14 ноября 1997 г.), Искусство программирования, том 1: Основные алгоритмы (3-е изд.), Addison-Wesley Professional
• Джеррам, Марк (1994), "Подсчет деревьев в графе является # P-полным", Письма об обработке информации, 51 (3): 111–116, Дои:10.1016/0020-0190(94)00085-9, ISSN  0020-0190.
• Выдра, Ричард (1948), «Число деревьев», Анналы математики, Вторая серия, 49 (3): 583–599, Дои:10.2307/1969046, JSTOR  1969046.