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

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

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

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

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

Определения

Дерево

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

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

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

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

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

Внутренняя вершина ( или внутренняя вершина) — это вершина степени не менее 2. Аналогично, внешняя вершина (или внешняя вершина, конечная вершина или лист) — это вершина степени 1. Вершина ветви в дереве — это вершина степени не менее 3. ^[19]

Неприводимое дерево (или дерево, редуцированное по ряду) — это дерево, в котором нет вершин степени 2 (перечисленных в последовательности A000014 в OEIS ). ^[20]

Лес

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

Полидерево

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

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

Полифорест

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

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

Корневое дерево

Корневое дерево — это дерево, в котором одна вершина обозначена как корень. ^[24] Ребрам корневого дерева можно присвоить естественную ориентацию, либо от корня, либо к нему, в этом случае структура становится направленным корневым деревом. Когда направленное корневое дерево имеет ориентацию от корня, оно называется древовидным [ ^3] или внешним деревом ; ^[11] когда оно имеет ориентацию к корню, оно называется антидревовидным или внутренним деревом . ^[11] Порядок дерева — это частичное упорядочение вершин дерева с $u < v$ тогда и только тогда, когда уникальный путь от корня до $v$ проходит через $u$ . Корневое дерево $T$ , являющееся подграфом некоторого графа $G,$ является нормальным деревом, если концы каждого $T$ -пути в $G$ сравнимы в этом порядке дерева (Diestel 2005, стр. 15). Корневые деревья, часто с дополнительной структурой, такой как упорядочение соседей в каждой вершине, являются ключевой структурой данных в информатике; см. древовидная структура данных .

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

Помеченное дерево — это дерево, в котором каждой вершине дана уникальная метка. Вершинам помеченного дерева на $n$ вершинах (для неотрицательных целых чисел $n$ ) обычно даны метки $1, 2, \dots, n$ . Рекурсивное дерево — это помеченное корневое дерево, в котором метки вершин соблюдают порядок дерева (т. е. если $u < v$ для двух вершин $u$ и $v$ , то метка $u$ меньше метки $v$ ).

В корневом дереве родитель вершины $v$ — это вершина, соединенная с $v$ на пути к корню; каждая вершина имеет уникального родителя, за исключением корня, у которого нет родителя. [ ^24] Дочерняя вершина вершины v $—$ это вершина, родительской для которой является $v .$ ^[24] Предшествующая вершина вершины $v$ — это любая вершина, которая является либо родительской для $v$ , либо (рекурсивно) предшествующей для родителя $v$ . Потомок вершины $v$ — это любая вершина, которая является либо дочерней для $v , либо$ ( рекурсивно) потомком для дочерней для $v$ . Родственная вершина вершины $v$ — это любая другая вершина на дереве, которая имеет общего родителя с $v$ . ^[24] Лист — это вершина без дочерних вершин. ^[24] Внутренняя вершина — это вершина, которая не является листом. ^[24]

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

K $-$ арное дерево (для неотрицательных целых чисел $k$ ) — это корневое дерево, в котором каждая вершина имеет не более $k$ потомков. ^[25] 2-арные деревья часто называют бинарными деревьями , в то время как 3-арные деревья иногда называют тернарными деревьями .

Упорядоченное дерево

Упорядоченное дерево (альтернативно, плоское дерево или позиционное дерево ^[26] ) — это корневое дерево, в котором порядок указан для потомков каждой вершины. ^[24]^[27] Это называется «плоским деревом», потому что порядок потомков эквивалентен вложению дерева в плоскость с корнем наверху и потомками каждой вершины ниже этой вершины. При наличии вложения корневого дерева в плоскость, если зафиксировать направление потомков, скажем, слева направо, то вложение дает порядок потомков. И наоборот, при наличии упорядоченного дерева и традиционном рисовании корня наверху, дочерние вершины в упорядоченном дереве можно нарисовать слева направо, что дает по существу уникальное плоское вложение.

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

Каждое дерево является двудольным графом . Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины. Поскольку дерево вообще не содержит циклов, оно является двудольным.
Каждое дерево со счетным числом вершин является планарным графом .
Каждый связный граф G допускает остовное дерево , которое является деревом, содержащим каждую вершину G и чьи ребра являются ребрами G. Более конкретные типы остовных деревьев, существующие в каждом связном конечном графе, включают деревья поиска в глубину и деревья поиска в ширину . Обобщая существование деревьев поиска в глубину, каждый связный граф только со счетным числом вершин имеет дерево Тремо . ^[28] Однако некоторые графы несчетного порядка не имеют такого дерева. ^[29]
Каждое конечное дерево с n вершинами, где n > 1 , имеет по крайней мере две конечные вершины (листья). Это минимальное число листьев характерно для графов-путей ; максимальное число, n − 1 , достигается только для графов-звезд . Число листьев не меньше максимальной степени вершины.
Для любых трех вершин в дереве три пути между ними имеют ровно одну общую вершину. В более общем смысле, вершина в графе, которая принадлежит трем кратчайшим путям среди трех вершин, называется медианой этих вершин. Поскольку каждые три вершины в дереве имеют уникальную медиану, каждое дерево является медианным графом .
Каждое дерево имеет центр, состоящий из одной вершины или двух смежных вершин. Центр — это средняя вершина или две средние вершины в каждом самом длинном пути. Аналогично, каждое дерево с n вершинами имеет центроид, состоящий из одной вершины или двух смежных вершин. В первом случае удаление вершины разбивает дерево на поддеревья с числом вершин менее n /2. Во втором случае удаление ребра между двумя центроидными вершинами разбивает дерево на два поддерева с числом вершин ровно n /2.
Максимальными кликами дерева являются именно его ребра, что означает, что класс деревьев имеет мало клик .

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

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

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

{n-2 \выберите d_{1}-1,d_{2}-1,\ldots ,d_{n}-1}.

Более общая задача — подсчет остовных деревьев в неориентированном графе , которая решается теоремой о матричном дереве . (Формула Кэли является частным случаем остовных деревьев в полном графе .) Похожая задача подсчета всех поддеревьев независимо от размера является #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) доказал асимптотическую оценку

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

с $C \approx 0,534949606...$ и $α \approx 2,95576528565...$ (последовательность A051491 в OEIS ). Здесь символ $~$ означает, что

\lim _{n\to \infty }{\frac {t(n)}{C\alpha ^{n}n^{-5/2}}}=1.

Это является следствием его асимптотической оценки числа $r (n)$ непомеченных корневых деревьев с $n$ вершинами:

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

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

Первые несколько значений $r (n)$ равны ^[30]

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

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

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

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

Примечания

^ Бендер и Уильямсон 2010, стр. 171.
^ Бендер и Уильямсон 2010, стр. 172.
^ abcd Deo 1974, стр. 206.
^ ab См. Харари и Самнер (1980).
^ ab См. Симион (1991).
^ ab См. Дасгупта (1999).
^ ab См. Ким и Перл (1983).
^ Стэнли Гилл Уильямсон (1985). Комбинаторика для компьютерных наук . Courier Dover Publications. стр. 288. ISBN 978-0-486-42076-9.
^ Мехран Месбахи; Магнус Эгерстедт (2010). Методы теории графов в многоагентных сетях . Princeton University Press. стр. 38. ISBN 978-1-4008-3535-5.
^ Дин-Чжу Ду; Кер-И Ко; Сяодун Ху (2011). Разработка и анализ алгоритмов аппроксимации . Springer Science & Business Media. стр. 108. ISBN 978-1-4614-1701-9.
^ abcd Deo 1974, стр. 207.
^ Джонатан Л. Гросс; Джей Йеллен; Пин Чжан (2013). Справочник по теории графов, второе издание . CRC Press. стр. 116. ISBN 978-1-4398-8018-0.
^ Бернхард Корте ; Йенс Виген (2012). Комбинаторная оптимизация: теория и алгоритмы (5-е изд.). Springer Science & Business Media. стр. 28. ISBN 978-3-642-24488-9.
^ Курт Мельхорн ; Питер Сандерс (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Springer Science & Business Media. стр. 52. ISBN 978-3-540-77978-0. Архивировано (PDF) из оригинала 2015-09-08.
^ Дэвид Макинсон (2012). Множества, логика и математика для вычислений . Springer Science & Business Media. С. 167–168. ISBN 978-1-4471-2499-3.
^ Кеннет Розен (2011). Дискретная математика и ее приложения, 7-е издание . McGraw-Hill Science. стр. 747. ISBN 978-0-07-338309-5.
^ Александр Шрийвер (2003). Комбинаторная оптимизация: многогранники и эффективность . Спрингер. п. 34. ISBN 3-540-44389-4.
^ Cayley (1857) "On the theory of the analytic forms called trees," Philosophical Magazine , 4-я серия, 13 : 172–176.
Однако следует отметить, что в 1847 году KGC von Staudt в своей книге Geometrie der Lage (Нюрнберг, (Германия): Bauer und Raspe, 1847) представил доказательство теоремы Эйлера о многограннике, которое опирается на деревья на страницах 20–21. Также в 1847 году немецкий физик Густав Кирхгоф исследовал электрические цепи и нашел связь между числом (n) проводов/резисторов (ветвей), числом (m) соединений (вершин) и числом (μ) петель (граней) в цепи. Он доказал эту связь с помощью аргумента, опирающегося на деревья. См.: Кирхгоф, Г. Р. (1847) «Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der Linearen Vertheilung galvanischer Ströme geführt wird». Архивировано 20 июля 2023 г. в Wayback Machine (О решении уравнений, к которым приводят исследования линейного распределения гальванических токов), Annalen der Physik. und Chemie , 72 (12): 497–508.
^ ДеБиазио, Луис; Ло, Аллан (2019-10-09). «Охватывающие деревья с небольшим количеством вершин ветвей». arXiv : 1709.04937 [math.CO].
^ Харари и Принс 1959, с. 150.
^ Чен, Вай-кай (1966). «О направленных деревьях и направленных $k-$ деревьях орграфа и их генерации». Журнал SIAM по прикладной математике . 14 (3): 550–560. doi :10.1137/0114048. MR 0209064.
^ ab Козлов, Дмитрий Н. (1999). "Комплексы направленных деревьев". Журнал комбинаторной теории . Серия A. 88 (1): 112–122. doi :10.1006/jcta.1999.2984. MR 1713484.
^ Тран, Нгок Май; Бак, Йоханнес; Клюппельберг, Клаудия (февраль 2024 г.), «Оценка направленного дерева для экстремальных значений», Журнал Королевского статистического общества, серия B: Статистическая методология , 86 (3): 771–792, arXiv : 2102.06197 , doi : 10.1093/jrsssb/qkad165
^ abcdefg Бендер и Уильямсон 2010, с. 173.
↑ См. Black, Paul E. (4 мая 2007 г.). "k-ary tree". Национальный институт стандартов и технологий США. Архивировано из оригинала 8 февраля 2015 г. Получено 8 февраля 2015 г.
^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Стайн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Раздел B.5.3, Двоичные и позиционные деревья : MIT Press. стр. 1174. ISBN 9780262046305. Архивировано из оригинала 16 июля 2023 г. . Получено 20 июля 2023 г. .{{cite book}}: CS1 maint: местоположение ( ссылка )
^ Стэнли, Ричард П. (2012), Перечислительная комбинаторика, т. I, Кембриджские исследования по высшей математике, т. 49, Cambridge University Press, стр. 573, ISBN 9781107015425
^ Дистель (2005), Предложение 8.2.4.
^ Дистель (2005), Предложение 8.5.2.
↑ См . Ли (1996).

Ссылки

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

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

На Викискладе есть медиафайлы по теме «Дерево (теория графов)» .

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