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

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

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

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

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

Определения [ править ]

Дерево [ править ]

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

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

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

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

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

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

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

Лес [ править ]

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

Polytree [ править ]

Основная статья: Политри

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

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

Полифорест [ править ]

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

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

Дерево с корнями [ править ]

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

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

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

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

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

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

Упорядоченное дерево [ править ]

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

Свойства [ править ]

  • Каждое дерево - двудольный граф . Граф двудольный тогда и только тогда, когда он не содержит циклов нечетной длины. Поскольку дерево вообще не содержит циклов, оно двудольное.
  • Каждое дерево - это медианный граф .
  • Каждое дерево со счетным числом вершин является плоским графом .
  • Каждый связный граф 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 ) равны [23]

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 центрального пути подграфа.
  • Регулярное дерево степени д есть бесконечное дерево с д ребер в каждой вершине. Они возникают как Кейли графы из свободных групп , и в теории Титс .

См. Также [ править ]

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

Примечания [ править ]

  1. Перейти ↑ Bender & Williamson 2010 , p. 171.
  2. Перейти ↑ Bender & Williamson 2010 , p. 172.
  3. ^ a b См. Дасгупта (1999) .
  4. ^ a b c d Deo 1974 , стр. 206.
  5. ^ a b См. Harary & Sumner (1980) .
  6. ^ a b См. Simion (1991) .
  7. ^ a b См. Kim & Pearl (1983) .
  8. ^ Стэнли Гилл Уильямсон (1985). Комбинаторика для компьютерных наук . Courier Dover Publications. п. 288. ISBN 978-0-486-42076-9.
  9. ^ Мехран Месбахи; Магнус Эгерштедт (2010). Теоретико-графические методы в многоагентных сетях . Издательство Принстонского университета. п. 38. ISBN 978-1-4008-3535-5.
  10. ^ Дин-Чжу Ду; Кер-И Ко; Сяодун Ху (2011). Разработка и анализ алгоритмов аппроксимации . Springer Science & Business Media. п. 108. ISBN 978-1-4614-1701-9.
  11. ^ a b c d Deo 1974 , стр. 207.
  12. ^ Джонатан Л. Гросс; Джей Йеллен; Пинг Чжан (2013). Справочник по теории графов, второе издание . CRC Press. п. 116. ISBN 978-1-4398-8018-0.
  13. ^ Бернхард Корте; Йенс Выген (2012). Комбинаторная оптимизация: теория и алгоритмы (5-е изд.). Springer Science & Business Media. п. 28. ISBN 978-3-642-24488-9.
  14. ^ Курт Mehlhorn ; Питер Сандерс (2008). Алгоритмы и структуры данных: The Basic Toolbox (PDF) . Springer Science & Business Media. п. 52. ISBN  978-3-540-77978-0.
  15. ^ Дэвид Макинсон (2012). Наборы, логика и математика для вычислений . Springer Science & Business Media. С. 167–168. ISBN 978-1-4471-2499-3.
  16. ^ Кеннет Розен (2011). Дискретная математика и ее приложения, 7-е издание . McGraw-Hill Science. п. 747. ISBN 978-0-07-338309-5.
  17. ^ Александр Шрайвер (2003). Комбинаторная оптимизация: многогранники и эффективность . Springer. п. 34. ISBN 3-540-44389-4.
  18. ↑ Кэли (1857) «О теории аналитических форм, называемых деревьями», Philosophical Magazine , 4-я серия, 13  : 172–176.
    Однако следует упомянуть, что в 1847 году KGC von Staudt в своей книге Geometrie der Lage (Nürnberg, (Германия): Bauer und Raspe, 1847) представил доказательство теоремы Эйлера о многограннике, которая опирается на деревья на страницах 20–21 . Также в 1847 году немецкий физик Густав Кирхгофисследовали электрические цепи и обнаружили связь между количеством (n) проводов / резисторов (ветвей), количеством (m) соединений (вершин) и количеством (μ) петель (граней) в цепи. Он доказал связь с помощью аргумента, основанного на деревьях. См .: Kirchhoff, GR (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.
  19. ^ Харари и Prins 1959 , стр. 150.
  20. ^ Б с д е е г Bender & Williamson 2010 , с. 173.
  21. ↑ См. Блэк, Пол Э. (4 мая 2007 г.). "к-арное дерево" . Национальный институт стандартов и технологий США . Проверено 8 февраля 2015 года .
  22. Перейти ↑ Stanley, Richard P. (2012), Enumerative Combinatorics, Vol. I , Cambridge Studies in Advanced Mathematics, 49 , Cambridge University Press, p. 573, ISBN 9781107015425
  23. ^ См. Ли (1996) .

Ссылки [ править ]

  • Бендер, Эдвард А .; Уильямсон, С. Гилл (2010), Списки, решения и графики. Знакомство с вероятностью
  • Дасгупта, Санджой (1999), "Learning polydrees", in Proc. 15-я конференция по неопределенности в искусственном интеллекте (UAI 1999), Стокгольм, Швеция, июль – август 1999 г. (PDF) , стр. 134–141.
  • Део, Нарсинг (1974), Теория графов с приложениями к технике и информатике (PDF) , Энглвуд, Нью-Джерси: Prentice-Hall, ISBN 0-13-363473-6
  • Харари, Фрэнк ; Prins Герт (1959), "Число гомеоморфно несводимых деревьев, а также другие виды" , Acta Mathematica , 101 (1-2): 141-162, DOI : 10.1007 / BF02559543 , ISSN  0001-5962
  • Харари, Фрэнк ; Самнер, Дэвид (1980), «Дихроматическое число ориентированного дерева», Журнал комбинаторики, информации и системных наук , 5 (3): 184–187, MR  0603363.
  • Kim, Jin H .; Перл, Иудея (1983), «Вычислительная модель для причинно-следственных и диагностических рассуждений в машинах вывода», в Proc. 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-полным", Письма об обработке информации , 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.