Из Википедии, бесплатной энциклопедии
  (Перенаправлено из Forest (теория графов) )
Перейти к навигации Перейти к поиску
Деревья
Дерево 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. ^ Бендер и Уильямсон 2010 , стр. 171.
  2. ^ Бендер и Уильямсон 2010 , стр. 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. ^ Курт Мельхорн ; Питер Сандерс (2008). Алгоритмы и структуры данных: 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 году К.Г. фон Штаудт в своей книге Geometrie der Lage (Нюрнберг, (Германия): 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. ^ Стэнли, Ричард П. (2012), Перечислительная комбинаторика, 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) , Энглвуд, Нью-Джерси: Прентис-Холл, 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.