Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Эквивалентно, древообразование - это направленное корневое дерево, у которого все края направлены от корня; существует ряд других эквивалентных характеристик. [3] [4] Каждое древообразование представляет собой направленный ациклический граф (DAG), но не каждый DAG является древовидным графом .

Эквивалентно древовидный орграф можно определить как корневой орграф, в котором путь от корня до любой другой вершины уникален. [1]

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

Термин « древообразование» происходит от французского. [5] Некоторые авторы возражают против этого на том основании, что его сложно писать по буквам. [6] В теории графов существует большое количество синонимов древовидности, в том числе ориентированное корневое дерево [2] [6] вне древовидной структуры , [7] исходящее дерево , [8] и даже ветвление , используемое для обозначения одного и того же понятия. . [8] Само корневое дерево было определено некоторыми авторами как ориентированный граф. [9] [10] [11]

Дальнейшие определения [ править ]

Более того, некоторые авторы определяют древовидность как остовное ориентированное дерево данного орграфа. [11] [12] То же самое можно сказать о некоторых его синонимах, особенно о ветвлении . [12] Другие авторы используют ветвление для обозначения леса ветвлений , причем последнее понятие определено в более широком смысле, приведенном в начале этой статьи, [13] [14], но также встречаются вариации с обоими понятиями связующего аромата. [11]

Также можно определить полезное понятие, перевернув все дуги древовидной структуры, то есть сделав так, чтобы все они указывали на корень, а не от него. Такие диграфы также обозначаются множеством терминов, таких как in-tree [15] или anti-arborescence [16] и т. Д. У. Т. Тутте различает эти два случая, используя фразы arborescence, расходящиеся от [some root] и arborescence, сходящиеся к [ какой-то корень]. [17]

Количество корневых деревьев (или ветвей) с n узлами задается последовательностью:

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

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

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

  1. ^ а б Гордон, Гэри (1989). «Жадный полином, различающий корневые древовидные образования» . Труды Американского математического общества . 107 (2): 287. DOI : 10.1090 / S0002-9939-1989-0967486-0 .
  2. ^ a b Стэнли Гилл Уильямсон (1985). Комбинаторика для компьютерных наук . Courier Dover Publications. п. 288. ISBN 978-0-486-42076-9.
  3. ^ Жан-Клод Фурнье (2013). Теория графов и приложения: с упражнениями и задачами . Джон Вили и сыновья. С. 94–95. ISBN 978-1-84821-070-7.
  4. ^ Жан Галье (2011). Дискретная математика . Springer Science & Business Media. С. 193–194. ISBN 978-1-4419-8046-5.
  5. ↑ Пер Хейдж и Фрэнк Харари (1996). Островные сети: коммуникации, родство и классификационные структуры в Океании . Издательство Кембриджского университета. п. 43. ISBN 978-0-521-55232-5.
  6. ^ a b Мехран Месбахи; Магнус Эгерштедт (2010). Теоретико-графические методы в многоагентных сетях . Издательство Принстонского университета. п. 38. ISBN 1-4008-3535-6.
  7. ^ Дин-Чжу Ду; Кер-И Ко; Сяодун Ху (2011). Разработка и анализ алгоритмов аппроксимации . Springer Science & Business Media. п. 108. ISBN 978-1-4614-1701-9.
  8. ^ a b Джонатан Л. Гросс; Джей Йеллен; Пинг Чжан (2013). Справочник по теории графов, второе издание . CRC Press. п. 116. ISBN 978-1-4398-8018-0.
  9. ^ Дэвид Макинсон (2012). Наборы, логика и математика для вычислений . Springer Science & Business Media. С. 167–168. ISBN 978-1-4471-2499-3.
  10. ^ Кеннет Розен (2011). Дискретная математика и ее приложения, 7-е издание . McGraw-Hill Science. п. 747. ISBN 978-0-07-338309-5.
  11. ^ a b c Александр Шрайвер (2003). Комбинаторная оптимизация: многогранники и эффективность . Springer. п. 34. ISBN 3-540-44389-4.
  12. ^ a b Йорген Банг-Йенсен; Григорий З. Гутин (2008). Орграфы: теория, алгоритмы и приложения . Springer. п. 339. ISBN. 978-1-84800-998-1.
  13. ^ Джеймс Эванс (1992). Алгоритмы оптимизации для сетей и графиков, второе издание . CRC Press. п. 59. ISBN 978-0-8247-8602-1.
  14. ^ Бернхард Корте; Йенс Выген (2012). Комбинаторная оптимизация: теория и алгоритмы (5-е изд.). Springer Science & Business Media. п. 18. ISBN 978-3-642-24488-9.
  15. ^ Курт Мельхорн ; Питер Сандерс (2008). Алгоритмы и структуры данных: Basic Toolbox (PDF) . Springer Science & Business Media. п. 52. ISBN  978-3-540-77978-0.
  16. ^ Бернхард Корте; Йенс Выген (2012). Комбинаторная оптимизация: теория и алгоритмы (5-е изд.). Springer Science & Business Media. п. 28. ISBN 978-3-642-24488-9.
  17. ^ Tutte, WT (2001), Теория графов , Cambridge University Press, стр. 126-127, ISBN 978-0-521-79489-3

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. «Древесность» . MathWorld .
  • Вайсштейн, Эрик В. «Дерево с корнями» . MathWorld .


  • v
  • т
  • е