Jump to content

Дерево (теория графов)

(Перенаправлено из упорядоченного дерева )
Деревья
Размеченное дерево с 6 вершинами и 5 ребрами.
Вершины v
Края v  − 1
Хроматическое число 2, если v > 1
Таблица графиков и параметров

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

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

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

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

Определения

[ редактировать ]

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

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

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

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

( Внутренняя вершина или внутренняя вершина) — это вершина степени не ниже 2. Аналогично, внешняя вершина (или внешняя вершина, конечная вершина или лист) — это вершина степени 1. Вершина ветвления в дереве — это вершина степени минимум 3. [19]

Неприводимое дерево (или сокращенное в ряд дерево) — это дерево, в котором нет вершины степени 2 (нумерованной в последовательности A000014 в OEIS ). [20]

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

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

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

Полифорест

[ редактировать ]

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

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

Укорененное дерево

[ редактировать ]

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

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

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

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

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

k -арное дерево (для неотрицательных целых чисел k ) — это корневое дерево, в котором каждая вершина имеет не более k детей. [25] 2-арные деревья часто называют бинарными деревьями , а 3-арные деревья иногда называют троичными деревьями .

Заказанное дерево

[ редактировать ]

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

Характеристики

[ редактировать ]
  • Каждое дерево представляет собой двудольный граф . Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины. Поскольку дерево вообще не содержит циклов, оно двудольное.
  • Каждое дерево, имеющее лишь счетное число вершин, является плоским графом .
  • Каждый связный граф G допускает остовное дерево , которое представляет собой дерево, содержащее каждую вершину и ребра которого являются ребрами G. G Более конкретные типы охватывающих деревьев, существующие в каждом связном конечном графе, включают деревья поиска в глубину и деревья поиска в ширину . Обобщая существование деревьев поиска в глубину, каждый связный граф со счетным числом вершин имеет дерево Тремо . [28] Однако некоторые графы несчетного порядка . не имеют такого дерева [29]
  • Каждое конечное дерево с n вершинами, n > 1 , имеет как минимум две конечные вершины (листья). Это минимальное количество листьев характерно для графов путей ; максимальное число n − 1 достигается только с помощью звездчатых графов . Количество листьев не меньше максимальной степени вершины.
  • Для любых трёх вершин дерева три пути между ними имеют ровно одну общую вершину. В более общем смысле вершина графа, принадлежащая трем кратчайшим путям среди трех вершин, называется медианой этих вершин. Поскольку каждые три вершины дерева имеют уникальную медиану, каждое дерево является медианным графом .
  • Каждое дерево имеет центр , состоящий из одной вершины или двух соседних вершин. Центром является средняя вершина или две средние вершины на каждом самом длинном пути. Аналогично, каждое n -вершинное дерево имеет центроид, состоящий из одной вершины или двух соседних вершин. В первом случае удаление вершины разбивает дерево на поддеревья, содержащие менее n /2 вершин. Во втором случае удаление ребра между двумя центроидальными вершинами разбивает дерево на два поддерева ровно по n /2 вершин.
  • Максимальными кликами дерева являются именно его ребра, а это означает, что в классе деревьев мало клик .

Перечисление

[ редактировать ]

Маркированные деревья

[ редактировать ]

Формула Кэли утверждает, что существует 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 ). Здесь символ ~ означает, что

Это следствие его асимптотической оценки числа r ( n ) немаркированных корневых деревьев с n вершинами:

с D ≈ 0,43992401257... и тем же α , что и выше (см. Knuth (1997) , глава 2.3.4.4 и Flajolet & Sedgewick (2009) , глава VII.5, стр. 475).

Первые несколько значений r ( n ) равны [30]

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

Виды деревьев

[ редактировать ]
  • Граф путей (или линейный граф ) состоит из n вершин, расположенных в линию, так что вершины i и i + 1 соединены ребром для i = 1, …, n – 1 .
  • Звездообразное дерево состоит из центральной вершины, называемой корнем , и нескольких прикрепленных к ней графов путей. Более формально, дерево называется звездообразным, если оно имеет ровно одну вершину степени выше 2.
  • Звездное дерево — это дерево, состоящее из одной внутренней вершины (и n — 1 листьев). Другими словами, звездное дерево порядка n — это дерево порядка n с максимально возможным количеством листьев.
  • Гусеничное дерево — это дерево, в котором все вершины находятся на расстоянии 1 от центрального подграфа путей.
  • Дерево лобстера — это дерево, в котором все вершины находятся на расстоянии 2 от центрального подграфа путей.
  • Регулярное дерево степени d — это бесконечное дерево с d ребрами в каждой вершине. Они возникают как графы Кэли и свободных групп в теории зданий Титса . В статистической механике они известны как решетки Бете .

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Бендер и Уильямсон 2010 , с. 171.
  2. ^ Бендер и Уильямсон 2010 , с. 172.
  3. ^ Перейти обратно: а б с д Део 1974 , с. 206.
  4. ^ Перейти обратно: а б См. Харари и Самнер (1980) .
  5. ^ Перейти обратно: а б См. Симион (1991) .
  6. ^ Перейти обратно: а б См. Дасгупта (1999) .
  7. ^ Перейти обратно: а б См. Ким и Перл (1983) .
  8. ^ Стэнли Джилл Уильямсон (1985). Комбинаторика для информатики . Публикации Courier Dover. п. 288. ИСБН  978-0-486-42076-9 .
  9. ^ Мехран Месбахи; Магнус Эгерстедт (2010). Теоретико-графовые методы в мультиагентных сетях . Издательство Принстонского университета. п. 38. ISBN  978-1-4008-3535-5 .
  10. ^ Дин-Чжу Ду; Кер-И Ко; Сяодун Ху (2011). Проектирование и анализ алгоритмов аппроксимации . Springer Science & Business Media. п. 108. ИСБН  978-1-4614-1701-9 .
  11. ^ Перейти обратно: а б с д Део 1974 , с. 207.
  12. ^ Джонатан Л. Гросс; Джей Йеллен; Пин Чжан (2013). Справочник по теории графов, второе издание . ЦРК Пресс. п. 116. ИСБН  978-1-4398-8018-0 .
  13. ^ Бернхард Корте ; Йенс Виген (2012). Комбинаторная оптимизация: теория и алгоритмы (5-е изд.). Springer Science & Business Media. п. 28. ISBN  978-3-642-24488-9 .
  14. ^ Курт Мельхорн ; Питер Сандерс (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Springer Science & Business Media. п. 52. ИСБН  978-3-540-77978-0 . Архивировано (PDF) из оригинала 8 сентября 2015 г.
  15. ^ Дэвид Макинсон (2012). Множества, логика и математика для вычислений . Springer Science & Business Media. стр. 167–168. ISBN  978-1-4471-2499-3 .
  16. ^ Кеннет Розен (2011). Дискретная математика и ее приложения, 7-е издание . МакГроу-Хилл Наука. п. 747. ИСБН  978-0-07-338309-5 .
  17. ^ Александр Шрийвер (2003). Комбинаторная оптимизация: многогранники и эффективность . Спрингер. п. 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) соединений (вершин) и количеством (μ) петель ( лица) по схеме. Он доказал это соотношение с помощью аргумента, основанного на деревьях. См.: Кирхгоф, Г.Р. (1847) bei der Untersuruchung der Linearen Vertheilung galvanischer Ströme geführt wird». Архивировано 20 июля 2023 г. в Wayback Machine «Ueber die Auflösung der Gleichungen, auf welche man (О решении уравнений, к которым приводят). путем исследования линейного распределения гальванических токов), Annalen der Physik und Chemie , 72 (12): 497–508.
  19. ^ ДеБиасио, Луи; Ло, Аллан (9 октября 2019 г.). «Охватывающие деревья с небольшим количеством вершин ветвей». arXiv : 1709.04937 [ math.CO ].
  20. ^ Харари и Принс 1959 , с. 150.
  21. ^ Чен, Вай-кай (1966). «О направленных деревьях и направленных k -деревьях орграфа и их порождении». SIAM Journal по прикладной математике . 14 : 550–560. дои : 10.1137/0114048 . МР   0209064 .
  22. ^ Перейти обратно: а б Козлов, Дмитрий Н. (1999). «Комплексы направленных деревьев». Журнал комбинаторной теории . Серия А. 88 (1): 112–122. дои : 10.1006/jcta.1999.2984 . МР   1713484 .
  23. ^ Тран, Нгок Май; Бак, Йоханнес; Клуппельберг, Клаудия (февраль 2024 г.), «Оценка направленного дерева на предмет экстремумов», Журнал Королевского статистического общества, серия B: Статистическая методология , arXiv : 2102.06197 , doi : 10.1093/jrsssb/qkad165
  24. ^ Перейти обратно: а б с д и ж г Бендер и Уильямсон 2010 , с. 173.
  25. ^ См. Блэк, Пол Э. (4 мая 2007 г.). «к-арное дерево» . Национальный институт стандартов и технологий США. Архивировано из оригинала 8 февраля 2015 года . Проверено 8 февраля 2015 г.
  26. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Раздел B.5.3, Бинарные и позиционные деревья : MIT Press. п. 1174. ИСБН  9780262046305 . Архивировано из оригинала 16 июля 2023 года . Проверено 20 июля 2023 г. {{cite book}}: CS1 maint: местоположение ( ссылка )
  27. ^ Стэнли, Ричард П. (2012), Перечислительная комбинаторика, Том. Я , Кембриджские исследования по высшей математике, том. 49, Издательство Кембриджского университета, с. 573, ISBN  9781107015425
  28. ^ Дистель (2005) , Предложение 8.2.4.
  29. ^ Дистель (2005) , Предложение 8.5.2.
  30. ^ См. Ли (1996) .

Дальнейшее чтение

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: fb5f3273785e44d02176d10739d6560f__1721819280
URL1:https://arc.ask3.ru/arc/aa/fb/0f/fb5f3273785e44d02176d10739d6560f.html
Заголовок, (Title) документа по адресу, URL1:
Tree (graph theory) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)