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

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

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

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

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

Определения

Дерево

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

$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$ мы можем легко подсчитать количество деревьев в лесу, вычитая разницу между общим количеством вершин и общим количеством ребер. $TV - TE =$ количество деревьев в лесу.

Политри

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

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

Полифорест

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

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

Укорененное дерево

Корневое дерево — это дерево, в котором одна вершина назначена корнем. ^[21] Ребрам корневого дерева можно присвоить естественную ориентацию либо от корня, либо к нему, и в этом случае структура становится направленным корневым деревом. Когда направленное корневое дерево имеет ориентацию от корня, оно называется древовидным [ ^4] или внешним деревом ; ^[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$ на пути к корню; каждая вершина имеет уникального родителя, за исключением того, что у корня нет родителя. ^[21] Дочерним элементом вершины $v$ является вершина, родительской вершиной которой является $v .$ ^[21] Асцендент вершины $v — это любая вершина,$ $которая$ является либо родительской вершиной $v$ , либо (рекурсивно) является восходящей родительской вершиной v . Потомком вершины $v$ является любая вершина, которая является либо дочерним элементом вершины $v$ , либо (рекурсивно) потомком дочернего элемента $v$ . Родственным братом вершины $v$ является любая другая вершина в дереве, имеющая общего родителя с $v$ . ^[21] Лист — это вершина, не имеющая дочерних элементов . ^[21]Внутренняя вершина — это вершина, которая не является листом. ^[21]

Высота вершины корневого дерева — это длина самого длинного пути вниз к листу из этой вершины. Высота дерева равна высоте корня . Глубина вершины — это длина пути к ее корню ( корневой путь ). Это ^{[ необходимо разъяснение (Это ___?) ]} обычно требуется при манипулировании различными самобалансирующими деревьями, в частности деревьями AVL . Корень имеет нулевую глубину, листья имеют нулевую высоту, а дерево только с одной вершиной (следовательно, и корень, и лист) имеет глубину ^{[ необходимы пояснения (мы определили только глубину вершины, а не глубину дерева. ) ]} и нулевая высота. Традиционно пустое дерево (дерево без вершин, если таковые разрешены) имеет глубину и высоту -1.

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

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

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

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

Каждое дерево представляет собой двудольный граф . Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины. Поскольку дерево вообще не содержит циклов, оно двудольное.
Каждое дерево, имеющее лишь счетное число вершин, является плоским графом .
Каждый связный граф G допускает остовное дерево , которое представляет собой дерево, содержащее каждую вершину G и ребра которого являются ребрами G. Более конкретные типы охватывающих деревьев, существующие в каждом связном конечном графе, включают деревья поиска в глубину и деревья поиска в ширину . Обобщая существование деревьев поиска в глубину, каждый связный граф со счетным числом вершин имеет дерево Тремо . ^[25] Однако некоторые графы несчетного порядка не имеют такого дерева. ^[26]
Каждое конечное дерево с 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 \choose 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)$ равны ^[27]

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.
^ ab См. Дасгупта (1999).
^ abcd Deo 1974, с. 206.
^ ab См. Харари и Самнер (1980).
^ ab См. Симион (1991).
^ ab См. Ким и Перл (1983).
^ Стэнли Гилл Уильямсон (1985). Комбинаторика для информатики . Публикации Courier Dover. п. 288. ИСБН 978-0-486-42076-9.
^ Мехран Месбахи; Магнус Эгерстедт (2010). Теоретико-графовые методы в мультиагентных сетях . Издательство Принстонского университета. п. 38. ISBN 978-1-4008-3535-5.
^ Дин-Чжу Ду; Кер-И Ко; Сяодун Ху (2011). Проектирование и анализ алгоритмов аппроксимации . Springer Science & Business Media. п. 108. ИСБН 978-1-4614-1701-9.
^ abcd Deo 1974, с. 207.
^ Джонатан Л. Гросс; Джей Йеллен; Пин Чжан (2013). Справочник по теории графов, второе издание . ЦРК Пресс. п. 116. ИСБН 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. ИСБН 978-3-540-77978-0. Архивировано (PDF) из оригинала 8 сентября 2015 г.
^ Дэвид Макинсон (2012). Множества, логика и математика для вычислений . Springer Science & Business Media. стр. 167–168. ISBN 978-1-4471-2499-3.
^ Кеннет Розен (2011). Дискретная математика и ее приложения, 7-е издание . МакГроу-Хилл Наука. п. 747. ИСБН 978-0-07-338309-5.
^ Александр Шрийвер (2003). Комбинаторная оптимизация: многогранники и эффективность . Спрингер. п. 34. ISBN 3-540-44389-4.
^ Кэли (1857) «К теории аналитических форм, называемых деревьями», Philosophical Magazine , 4-я серия, 13 : 172–176.
Однако следует упомянуть, что в 1847 году КГК фон Штаудт в своей книге 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» (О решении уравнений, к которым приводят исследования линейного распределения гальванических токов). ), Annalen der Physik und Chemie , 72 (12): 497–508.
^ ДеБиасио, Луи; Ло, Аллан (9 октября 2019 г.). «Охватывающие деревья с небольшим количеством вершин ветвей». arXiv : 1709.04937 [math.CO].
^ Харари и Принс 1959, с. 150.
^ abcdefg Бендер и Уильямсон 2010, с. 173.
↑ См. Блэк, Пол Э. (4 мая 2007 г.). «к-арное дерево». Национальный институт стандартов и технологий США . Проверено 8 февраля 2015 г.
^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Раздел B.5.3, Бинарные и позиционные деревья : MIT Press. п. 1174. ИСБН 9780262046305. Проверено 20 июля 2023 г.{{cite book}}: CS1 maint: местоположение ( ссылка )
^ Стэнли, Ричард П. (2012), Перечислительная комбинаторика, Vol. Я, Кембриджские исследования по высшей математике, том. 49, Издательство Кембриджского университета, с. 573, ISBN 9781107015425
^ Дистель (2005), Предложение 8.2.4.
^ Дистель (2005), Предложение 8.5.2.
^ См. Ли (1996).

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

Викискладе есть медиафайлы, связанные с деревом (теорией графов) .

Дистель, Рейнхард (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-полный», Information Processing Letters , 51 (3): 111–116, doi : 10.1016/0020-0190(94)00085-9, ISSN 0020- 0190.
Оттер, Ричард (1948), «Число деревьев», Анналы математики , вторая серия, 49 (3): 583–599, doi : 10.2307/1969046, JSTOR 1969046.