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

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

В теории графов дерево связный — это неориентированный граф , в котором любые две вершины соединены ровно одним путем , или, что то же самое, ациклический неориентированный граф. ^[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$ .
$G$ связен и граф $K3 графа$ не минором 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 п -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)$ равны ^[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.
^ Перейти обратно: ^а ^б ^с ^д Део 1974 , с. 206.
^ Перейти обратно: ^а ^б См. Харари и Самнер (1980) .
^ Перейти обратно: ^а ^б См. Симион (1991) .
^ Перейти обратно: ^а ^б См. Дасгупта (1999) .
^ Перейти обратно: ^а ^б См. Ким и Перл (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 .
^ Перейти обратно: ^а ^б ^с ^д Део 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) bei der Untersuruchung der Linearen Vertheilung galvanischer Ströme geführt wird». Архивировано 20 июля 2023 г. в Wayback Machine «Ueber die Auflösung der Gleichungen, auf welche man (О решении уравнений, к которым приводят). путем исследования линейного распределения гальванических токов), Annalen der Physik und Chemie , 72 (12): 497–508.
^ ДеБиасио, Луи; Ло, Аллан (9 октября 2019 г.). «Охватывающие деревья с небольшим количеством вершин ветвей». arXiv : 1709.04937 [ math.CO ].
^ Харари и Принс 1959 , с. 150.
^ Чен, Вай-кай (1966). «О направленных деревьях и направленных $k$ -деревьях орграфа и их порождении». SIAM Journal по прикладной математике . 14 : 550–560. дои : 10.1137/0114048 . МР 0209064 .
^ Перейти обратно: ^а ^б Козлов, Дмитрий Н. (1999). «Комплексы направленных деревьев». Журнал комбинаторной теории . Серия А. 88 (1): 112–122. дои : 10.1006/jcta.1999.2984 . МР 1713484 .
^ Тран, Нгок Май; Бак, Йоханнес; Клуппельберг, Клаудия (февраль 2024 г.), «Оценка направленного дерева на предмет экстремумов», Журнал Королевского статистического общества, серия B: Статистическая методология , arXiv : 2102.06197 , doi : 10.1093/jrsssb/qkad165
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Бендер и Уильямсон 2010 , с. 173.
^ См. Блэк, Пол Э. (4 мая 2007 г.). «к-арное дерево» . Национальный институт стандартов и технологий США. Архивировано из оригинала 8 февраля 2015 года . Проверено 8 февраля 2015 г.
^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Раздел B.5.3, Бинарные и позиционные деревья : MIT Press. п. 1174. ИСБН 9780262046305 . Архивировано из оригинала 16 июля 2023 года . Проверено 20 июля 2023 г. {{cite book}}: CS1 maint: местоположение ( ссылка )
^ Стэнли, Ричард П. (2012), Перечислительная комбинаторика, Том. Я , Кембриджские исследования по высшей математике, том. 49, Издательство Кембриджского университета, с. 573, ISBN 9781107015425
^ Дистель (2005) , Предложение 8.2.4.
^ Дистель (2005) , Предложение 8.5.2.
^ См. Ли (1996) .

Ссылки

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

[FOOTNOTEBenderWilliamson2010171-1] Бендер и Уильямсон 2010 , с. 171.

[FOOTNOTEBenderWilliamson2010172-2] Бендер и Уильямсон 2010 , с. 172.

[FOOTNOTEDeo1974206-3] Перейти обратно: ^а ^б ^с ^д Део 1974 , с. 206.

[Harary_1980-4] Перейти обратно: ^а ^б См. Харари и Самнер (1980) .

[s91-5] Перейти обратно: ^а ^б См. Симион (1991) .

[d99-6] Перейти обратно: ^а ^б См. Дасгупта (1999) .

[kp83-7] Перейти обратно: ^а ^б См. Ким и Перл (1983) .

[Williamson1985-8] Стэнли Джилл Уильямсон (1985). Комбинаторика для информатики . Публикации Courier Dover. п. 288. ИСБН 978-0-486-42076-9 .

[multi-9] Мехран Месбахи; Магнус Эгерстедт (2010). Теоретико-графовые методы в мультиагентных сетях . Издательство Принстонского университета. п. 38. ISBN 978-1-4008-3535-5 .

[DuKo2011-10] Дин-Чжу Ду; Кер-И Ко; Сяодун Ху (2011). Проектирование и анализ алгоритмов аппроксимации . Springer Science & Business Media. п. 108. ИСБН 978-1-4614-1701-9 .

[FOOTNOTEDeo1974207-11] Перейти обратно: ^а ^б ^с ^д Део 1974 , с. 207.

[GrossYellen2013-12] Джонатан Л. Гросс; Джей Йеллен; Пин Чжан (2013). Справочник по теории графов, второе издание . ЦРК Пресс. п. 116. ИСБН 978-1-4398-8018-0 .

[KorteVygen2012b-13] Бернхард Корте ; Йенс Виген (2012). Комбинаторная оптимизация: теория и алгоритмы (5-е изд.). Springer Science & Business Media. п. 28. ISBN 978-3-642-24488-9 .

[MehlhornSanders2008-14] Курт Мельхорн ; Питер Сандерс (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Springer Science & Business Media. п. 52. ИСБН 978-3-540-77978-0 . Архивировано (PDF) из оригинала 8 сентября 2015 г.

[Makinson2012-15] Дэвид Макинсон (2012). Множества, логика и математика для вычислений . Springer Science & Business Media. стр. 167–168. ISBN 978-1-4471-2499-3 .

[16] Кеннет Розен (2011). Дискретная математика и ее приложения, 7-е издание . МакГроу-Хилл Наука. п. 747. ИСБН 978-0-07-338309-5 .

[Schrijver2003-17] Александр Шрийвер (2003). Комбинаторная оптимизация: многогранники и эффективность . Спрингер. п. 34. ISBN 3-540-44389-4 .

[18] Кэли (1857) «К теории аналитических форм, называемых деревьями», Philosophical Magazine , 4-я серия, 13 : 172–176.
Однако следует упомянуть, что в 1847 году КГК фон Штаудт в своей книге Geometrie der Lage доказательство теоремы Эйлера о многогранниках, основанное на деревьях (Нюрнберг, (Германия): Bauer und Raspe, 1847) представил на страницах 20–21 . Также в 1847 году немецкий физик Густав Кирхгоф исследовал электрические цепи и обнаружил связь между количеством (n) проводов/резисторов (ветвей), количеством (m) соединений (вершин) и количеством (μ) петель ( лица) по схеме. Он доказал это соотношение с помощью аргумента, основанного на деревьях. См.: Кирхгоф, Г.Р. (1847) bei der Untersuruchung der Linearen Vertheilung galvanischer Ströme geführt wird». Архивировано 20 июля 2023 г. в Wayback Machine «Ueber die Auflösung der Gleichungen, auf welche man (О решении уравнений, к которым приводят). путем исследования линейного распределения гальванических токов), Annalen der Physik und Chemie , 72 (12): 497–508.

[19] ДеБиасио, Луи; Ло, Аллан (9 октября 2019 г.). «Охватывающие деревья с небольшим количеством вершин ветвей». arXiv : 1709.04937 [ math.CO ].

[FOOTNOTEHararyPrins1959150-20] Харари и Принс 1959 , с. 150.

[21] Чен, Вай-кай (1966). «О направленных деревьях и направленных $k$ -деревьях орграфа и их порождении». SIAM Journal по прикладной математике . 14 : 550–560. дои : 10.1137/0114048 . МР 0209064 .

[kozlov-22] Перейти обратно: ^а ^б Козлов, Дмитрий Н. (1999). «Комплексы направленных деревьев». Журнал комбинаторной теории . Серия А. 88 (1): 112–122. дои : 10.1006/jcta.1999.2984 . МР 1713484 .

[23] Тран, Нгок Май; Бак, Йоханнес; Клуппельберг, Клаудия (февраль 2024 г.), «Оценка направленного дерева на предмет экстремумов», Журнал Королевского статистического общества, серия B: Статистическая методология , arXiv : 2102.06197 , doi : 10.1093/jrsssb/qkad165

[FOOTNOTEBenderWilliamson2010173-24] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Бендер и Уильямсон 2010 , с. 173.

[25] См. Блэк, Пол Э. (4 мая 2007 г.). «к-арное дерево» . Национальный институт стандартов и технологий США. Архивировано из оригинала 8 февраля 2015 года . Проверено 8 февраля 2015 г.

[26] Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Раздел B.5.3, Бинарные и позиционные деревья : MIT Press. п. 1174. ИСБН 9780262046305 . Архивировано из оригинала 16 июля 2023 года . Проверено 20 июля 2023 г. {{cite book}}: CS1 maint: местоположение ( ссылка )

[27] Стэнли, Ричард П. (2012), Перечислительная комбинаторика, Том. Я , Кембриджские исследования по высшей математике, том. 49, Издательство Кембриджского университета, с. 573, ISBN 9781107015425

[FOOTNOTEDiestel2005Prop._8.2.4-28] Дистель (2005) , Предложение 8.2.4.

[FOOTNOTEDiestel2005Prop._8.5.2-29] Дистель (2005) , Предложение 8.5.2.

[30] См. Ли (1996) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]