Древовидность (теория графов)
В теории графов древовидность ориентированный — это граф , в котором существует вершина r (называемая корнем ) такая, что для любой другой вершины v существует ровно один направленный путь от v к r (обратите внимание, что корень r уникален). [1] Таким образом, древовидность — это форма направленного графа корневого дерева , понимаемая здесь как неориентированный граф . [2] [3] Древовидность — это также направленное корневое дерево , у которого все ребра направлены от корня; существует ряд других эквивалентных характеристик. [4] [5]
Каждое древовидное дерево представляет собой ориентированный ациклический граф (DAG), но не каждое DAG является древовидным.
Определение
[ редактировать ]Термин «древесность» происходит от французского языка. [6] Некоторые авторы возражают против этого на том основании, что его сложно писать. [7] В теории графов существует большое количество синонимов древовидности, включая направленное корневое дерево , [3] [7] вне дерева , [8] вне дерева , [9] и даже ветвление используется для обозначения одной и той же концепции. [9] Само корневое дерево некоторыми авторами определяется как ориентированный граф. [10] [11] [12]
Дальнейшие определения
[ редактировать ]Более того, некоторые авторы определяют древовидность как связующее ориентированное дерево данного орграфа. [12] [13] То же самое можно сказать и о некоторых его синонимах, особенно о ветвлении . [13] Другие авторы используют ветвление для обозначения леса древесных пород, причем последнее понятие определяется в более широком смысле, данном в начале этой статьи: [14] [15] но также встречаются вариации с обоими понятиями охватывающего аромата. [12]
Также возможно определить полезное понятие, перевернув все края древовидного дерева, т. е. направив их все в направлении корня, а не от него. Такие орграфы также обозначаются различными терминами, например, внутридеревьевыми. [16] золото анти-дерево . [17] У.Т.Татте различает эти два случая, используя фразы древовидность, расходящаяся от [некоторый корень] и древовидность, сходящаяся к [некоторый корень]. [18]
Количество корневых деревьев (или древостоев) с n узлами определяется последовательностью:
- 0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, ... (последовательность A000081 в OEIS ).
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Дарий Гринберг (2 августа 2023 г.). «Введение в теорию графов (текст по математике 530 весной 2022 года в Университете Дрекселя)» (PDF) . Дарий Гринберг, Мюнхенский университет Людвига-Максимилиана . п. 187 . Проверено 2 июля 2024 г.
Теорема 5.6.5, утверждение A4: Для каждой вершины v ∈ V мультиорграф D имеет единственный путь из r в v.
- ^ Гордон, Гэри (1989). «Гридоидный полином, который отличает корневые деревья» . Труды Американского математического общества . 107 (2): 287–298. дои : 10.1090/S0002-9939-1989-0967486-0 .
- ↑ Перейти обратно: Перейти обратно: а б Стэнли Джилл Уильямсон (1985). Комбинаторика для информатики . Публикации Курьера Дувра. п. 288. ИСБН 978-0-486-42076-9 .
- ^ Жан-Клод Фурнье (2013). Теория графов и приложения: с упражнениями и задачами . Джон Уайли и сыновья. стр. 94–95. ISBN 978-1-84821-070-7 .
- ^ Жан Галье (2011). Дискретная математика . Springer Science & Business Media. стр. 193–194. ISBN 978-1-4419-8046-5 .
- ^ Пер Хаге и Фрэнк Харари (1996). Сети островов: структуры связи, родства и классификации в Океании . Издательство Кембриджского университета. п. 43. ИСБН 978-0-521-55232-5 .
- ↑ Перейти обратно: Перейти обратно: а б Мехран Месбахи; Магнус Эгерстедт (2010). Теоретико-графовые методы в мультиагентных сетях . Издательство Принстонского университета. п. 38. ISBN 978-1-4008-3535-5 .
- ^ Дин-Чжу Ду; Кер-И Ко; Сяодун Ху (2011). Проектирование и анализ алгоритмов аппроксимации . Springer Science & Business Media. п. 108. ИСБН 978-1-4614-1701-9 .
- ↑ Перейти обратно: Перейти обратно: а б Джонатан Л. Гросс; Джей Йеллен; Пин Чжан (2013). Справочник по теории графов, второе издание . ЦРК Пресс. п. 116. ИСБН 978-1-4398-8018-0 .
- ^ Дэвид Макинсон (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 .
- ↑ Перейти обратно: Перейти обратно: а б Йорген Банг-Йенсен; Григорий З. Гутин (2008). Орграфы: теория, алгоритмы и приложения . Спрингер. п. 339. ИСБН 978-1-84800-998-1 .
- ^ Джеймс Эванс (1992). Алгоритмы оптимизации сетей и графов, второе издание . ЦРК Пресс. п. 59. ИСБН 978-0-8247-8602-1 .
- ^ Бернхард Корте ; Йенс Виген (2012). Комбинаторная оптимизация: теория и алгоритмы (5-е изд.). Springer Science & Business Media. п. 18. ISBN 978-3-642-24488-9 .
- ^ Курт Мельхорн ; Питер Сандерс (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Springer Science & Business Media. п. 52. ИСБН 978-3-540-77978-0 .
- ^ Бернхард Корте ; Йенс Виген (2012). Комбинаторная оптимизация: теория и алгоритмы (5-е изд.). Springer Science & Business Media. п. 28. ISBN 978-3-642-24488-9 .
- ^ Тутт, WT (2001), Теория графов , Издательство Кембриджского университета, стр. 126–127, ISBN 978-0-521-79489-3