Арборесценция (теория графов) - Arborescence (graph theory)

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

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

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

Определение

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

Дальнейшие определения

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

Также можно определить полезное понятие, изменив все дуги древовидной структуры, то есть сделав так, чтобы все они указывали на корень, а не от него. Такие орграфы также обозначаются различными терминами, такими как в дереве[15] или же антидревесение[16] и т.п. В. Т. Тутте различает эти два случая, используя фразы древовидность расходится с [некоторый корень] и древовидность сходится к [какой-то корень].[17]

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

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

Смотрите также

Рекомендации

  1. ^ а б Гордон, Гэри (1989). «Жадный полином, различающий корневые древовидные образования». Труды Американского математического общества. 107 (2): 287. Дои:10.1090 / S0002-9939-1989-0967486-0.
  2. ^ а б Стэнли Гилл Уильямсон (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. ^ Per Hage и Фрэнк Харари (1996). Островные сети: коммуникационные, родственные и классификационные структуры в Океании. Издательство Кембриджского университета. п. 43. ISBN  978-0-521-55232-5.
  6. ^ а б Мехран Месбахи; Магнус Эгерштедт (2010). Теоретико-графические методы в многоагентных сетях. Издательство Принстонского университета. п. 38. ISBN  1-4008-3535-6.
  7. ^ Дин-Чжу Ду; Кер-И Ко; Сяодун Ху (2011). Разработка и анализ алгоритмов аппроксимации. Springer Science & Business Media. п. 108. ISBN  978-1-4614-1701-9.
  8. ^ а б Джонатан Л. Гросс; Джей Йеллен; Пинг Чжан (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. ^ а б c Александр Шрайвер (2003). Комбинаторная оптимизация: многогранники и эффективность. Springer. п. 34. ISBN  3-540-44389-4.
  12. ^ а б Йорген Банг-Йенсен; Григорий З. Гутин (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). Алгоритмы и структуры данных: базовый набор инструментов (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. ^ Тутте, W.T. (2001), Теория графов, Cambridge University Press, стр. 126–127, ISBN  978-0-521-79489-3

внешняя ссылка