Связующее дерево

Дерево, включающее все вершины графа.

Охватывающее дерево (синие тяжелые ребра) сеточного графа

В математической области теории графов остовное дерево T неориентированного графа G представляет собой подграф, который представляет собой дерево , включающее все вершины G. ^[1] Как правило, граф может иметь несколько остовных деревьев, но несвязный граф не будет содержать остовное дерево (см. остовные леса ниже). Если все ребра G также являются ребрами остовного дерева T группы G , то G является деревом и идентично T (т. е. дерево имеет уникальное остовное дерево и оно само) .

Приложения

Несколько алгоритмов поиска пути , включая алгоритм Дейкстры и алгоритм поиска A* , внутренне строят связующее дерево в качестве промежуточного шага в решении проблемы.

Чтобы минимизировать затраты на силовые сети, проводные соединения, трубопроводы, автоматическое распознавание речи и т. д., люди часто используют алгоритмы, которые постепенно строят связующее дерево (или множество таких деревьев) в качестве промежуточных шагов в процессе поиска минимального связующего дерева. . ^[2]

Интернет и многие другие телекоммуникационные сети имеют каналы передачи, которые соединяют узлы в ячеистой топологии , включающей несколько петель. Чтобы избежать петель моста и петель маршрутизации , многие протоколы маршрутизации, разработанные для таких сетей, включая протокол связующего дерева , протокол открытия кратчайшего пути , протокол маршрутизации по состоянию канала , маршрутизацию на основе расширенного дерева и т. д., требуют, чтобы каждый маршрутизатор помнил связующее дерево. ^[3]

Особый вид остовного дерева, дерево Сюонга , используется в топологической теории графов для поиска вложений графов с максимальным родом . Дерево Сюонга — это остовное дерево, такое, что в оставшемся графе количество компонент связности с нечетным числом ребер минимально возможно. Дерево Сюонга и связанное с ним вложение максимального рода можно найти за полиномиальное время . ^[4]

Определения

Дерево — это связный неориентированный граф без циклов . Это остовное дерево графа G , если оно охватывает G (то есть включает в себя каждую вершину G ) и является подграфом G (каждое ребро в дереве принадлежит G ). Опорное дерево связного графа G также можно определить как максимальное множество ребер графа G , не содержащее циклов, или как минимальное множество ребер, соединяющих все вершины.

Фундаментальные циклы

Добавление только одного ребра к связующему дереву создаст цикл; такой цикл называется фундаментальным циклом относительно этого дерева. Для каждого ребра, не входящего в состав остовного дерева, существует отдельный фундаментальный цикл; таким образом, существует взаимно однозначное соответствие между фундаментальными циклами и ребрами, не входящими в остовное дерево. Для связного графа с V вершинами любое остовное дерево будет иметь V  − 1 ребер, и, таким образом, граф из E ребер и одно из его остовных деревьев будут иметь E  −  V  + 1 фундаментальных циклов (количество ребер вычитается из числа ребер, включенных в остовное дерево; указывается количество ребер, не включенных в остовное дерево). Для любого данного остовного дерева набор всех E  −  V  + 1 фундаментальных циклов образует базис цикла , т. е. базис пространства циклов . ^[5]

Фундаментальные разрезы

Двойственным к понятию фундаментального цикла является понятие фундаментального разреза относительно данного остовного дерева. При удалении только одного ребра остовного дерева вершины разбиваются на два непересекающихся множества. Фундаментальный разрез определяется как набор ребер, которые необходимо удалить из графа G , чтобы выполнить то же разбиение. Таким образом, каждое остовное дерево определяет набор из V  - 1 фундаментальных разрезов, по одному на каждое ребро остовного дерева. ^[6]

Двойственность между фундаментальными разрезами и фундаментальными циклами устанавливается, если отметить, что ребра цикла, не входящие в остовное дерево, могут появляться только в разрезах других ребер цикла; и наоборот : ребра в наборе разрезов могут появляться только в тех циклах, которые содержат ребро, соответствующее этому набору разрезов. Эту двойственность также можно выразить с помощью теории матроидов , согласно которой связующее дерево является основой графического матроида , фундаментальный цикл — это уникальная схема внутри множества, образованная добавлением одного элемента к базе, а фундаментальные разрезы определяются точно так же из дуального матроида . ^[7]

Охватывающие леса

Совокупность непересекающихся (несвязанных) деревьев описывается как лес . Охватывающий лес в графе — это подграф, представляющий собой лес с дополнительным требованием. Используются два несовместимых требования, одно из которых встречается относительно редко.

• Почти во всех книгах и статьях по теории графов остовный лес определяется как лес, охватывающий все вершины, а это означает лишь то, что каждая вершина графа является вершиной леса. Связный граф может иметь несвязный остовный лес, например лес без ребер, в котором каждая вершина образует одновершинное дерево. ^{[8] [9]}

• Некоторые авторы теории графов определяют остовный лес как максимальный ациклический подграф данного графа или, что то же самое, подграф, состоящий из остовного дерева в каждом компоненте связности графа. ^[10]

Чтобы избежать путаницы между этими двумя определениями, Гросс и Йеллен (2005) предлагают термин «полный остовный лес» для остовного леса с тем же количеством компонентов, что и данный граф (т. е. максимальный лес), а Бонди и Мерти (2008) ) вместо этого назовите этот тип леса «максимальным остовным лесом» (что избыточно, поскольку максимальный лес обязательно содержит каждую вершину). ^[11]

Подсчет пролетных деревьев

Формула Кэли подсчитывает количество остовных деревьев в полном графе. Есть деревья в , деревья в и деревья в . ${\displaystyle 2^{2-2}=1}$ ${\displaystyle K_{2}}$ ${\displaystyle 3^{3-2}=3}$ ${\displaystyle K_{3}}$ ${\displaystyle 4^{4-2}=16}$ ${\displaystyle K_{4}}$

Число t ( G ) остовных деревьев связного графа является хорошо изученным инвариантом .

На конкретных графиках

В некоторых случаях легко вычислить t ( G ) напрямую:

• Если G сам по себе является деревом, то t ( G ) = 1 .
• Когда G — граф циклов C _n с n вершинами, тогда t ( G ) =  n .
• Для полного графа с n вершинами формула Кэли ^[12] дает число остовных деревьев как n ^{n  − 2} .
• Если G — полный двудольный граф , то . ^[8] ${\displaystyle K_{p,q}}$ ${\displaystyle t(G)=p^{q-1}q^{p-1}}$
• Для n -мерного графа гиперкуба , ^[13] количество остовных деревьев равно . ${\displaystyle Q_{n}}$ ${\displaystyle t(G)=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$

В произвольных графах

В более общем смысле, для любого графа G число t ( G ) можно вычислить за полиномиальное время как определитель матрицы, полученной из графа, используя теорему Кирхгофа о дереве матриц . ^[14]

В частности, для вычисления t ( G ) строится матрица Лапласа графа, квадратная матрица, в которой строки и столбцы индексируются вершинами G . Запись в строке i и столбце j представляет собой одно из трех значений:

• Степень вершины i , если i  =  j ,
• −1, если вершины i и j смежны, или
• 0, если вершины i и j отличны друг от друга, но не смежны.

Полученная матрица сингулярна , поэтому ее определитель равен нулю. Однако удаление строки и столбца для произвольно выбранной вершины приводит к уменьшению матрицы, определитель которой равен точно  t ( G ).

Удаление-сокращение

Если G — граф или мультиграф , а e — произвольное ребро G , то число t ( G ) остовных деревьев G удовлетворяет повторению удаления-сжатия t ( G ) =  t ( G  −  e ) +  t ( G / e ), где G  −  e — мультиграф, полученный удалением e , а G / e — сокращение G на e . ^[15] Термин t ( G  −  e ) в этой формуле подсчитывает остовные деревья  G , которые не используют ребро  e , а термин t ( G / e ) подсчитывает остовные деревья  G , которые используют  e .

В этой формуле, если данный граф G является мультиграфом или если сжатие приводит к соединению двух вершин друг с другом кратными ребрами, то лишние ребра не следует удалять, так как это приведет к неправильной сумме. Например, граф связей , соединяющий две вершины k ребрами, имеет k различных остовных деревьев, каждое из которых состоит из одного из этих ребер.

Полином Тутте

Полином Тутте графа можно определить как сумму по остовным деревьям графа членов, вычисленных на основе «внутренней активности» и «внешней активности» дерева. Его значение при аргументах (1,1) — это количество остовных деревьев или, в несвязном графе, количество максимальных остовных лесов. ^[16]

Полином Тутте также можно вычислить с помощью рекурсии удаления-сокращения, но его вычислительная сложность высока: для многих значений его аргументов его точное вычисление является #P-полным , а также его трудно аппроксимировать с гарантированным коэффициентом аппроксимации . Точка (1,1), в которой его можно оценить по теореме Кирхгофа, является одним из немногих исключений. ^[17]

Алгоритмы

Строительство

Единственное остовное дерево графа можно найти за линейное время с помощью поиска в глубину или поиска в ширину . Оба этих алгоритма исследуют данный граф, начиная с произвольной вершины v , перебирая соседей обнаруженных ими вершин и добавляя каждого неисследованного соседа в структуру данных, которая будет исследована позже. Они различаются тем, является ли эта структура данных стеком (в случае поиска в глубину) или очередью (в случае поиска в ширину). В любом случае можно сформировать связующее дерево, соединив каждую вершину, кроме корневой вершины v , с вершиной, из которой она была обнаружена. Это дерево известно как дерево поиска в глубину или дерево поиска в ширину в соответствии с алгоритмом исследования графа, использованным для его построения. ^[18] Деревья поиска в глубину — это особый случай класса остовных деревьев, называемых деревьями Тремо , названных в честь первооткрывателя поиска в глубину в 19 веке. ^[19]

Связующие деревья важны в параллельных и распределенных вычислениях как способ поддержания связи между набором процессоров; см., например, протокол связующего дерева, используемый устройствами канального уровня OSI , или Shout (протокол) для распределенных вычислений. Однако методы построения связующих деревьев в глубину и в ширину на последовательных компьютерах не очень подходят для параллельных и распределенных компьютеров. ^[20] Вместо этого исследователи разработали несколько более специализированных алгоритмов для поиска остовных деревьев в этих моделях вычислений. ^[21]

Оптимизация

В некоторых областях теории графов часто бывает полезно найти минимальное остовное дерево взвешенного графа . Другие задачи оптимизации остовных деревьев также были изучены, в том числе максимальное остовное дерево, минимальное дерево, охватывающее не менее k вершин, остовное дерево с наименьшим количеством ребер на вершину , остовное дерево с наибольшим количеством листьев , остовное дерево с наименьшим количеством листьев (тесно связано с проблемой гамильтоновых путей ), остовным деревом минимального диаметра и остовным деревом минимального расширения. ^{[22] [23]}

Проблемы оптимального остовного дерева также изучались для конечных наборов точек в геометрическом пространстве, таком как евклидова плоскость . Для таких входных данных связующее дерево снова является деревом, вершинами которого являются заданные точки. Качество дерева измеряется так же, как и в графе, с использованием евклидова расстояния между парами точек в качестве веса для каждого ребра. Так, например, евклидово минимальное остовное дерево — это то же самое, что минимальное остовное дерево графа в полном графе с евклидовыми весами ребер. Однако для решения задачи оптимизации нет необходимости строить этот граф; например, задачу минимального остовного дерева Евклида можно решить более эффективно за время O ( n  log  n ), построив триангуляцию Делоне и затем применив к полученной триангуляции алгоритм минимального остовного дерева с линейным планарным графом . ^[22]

Рандомизация

Опорное дерево, случайно выбранное среди всех остовных деревьев с равной вероятностью, называется равномерным остовным деревом . Алгоритм Уилсона можно использовать для создания однородных остовных деревьев за полиномиальное время путем случайного блуждания по заданному графу и стирания циклов, созданных этим блужданием. ^[24]

Альтернативной моделью случайного, но неравномерного создания остовных деревьев является случайное минимальное остовное дерево . В этой модели ребрам графа присваиваются случайные веса, а затем строится минимальное остовное дерево взвешенного графа. ^[25]

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

Поскольку граф может иметь экспоненциально много остовных деревьев, невозможно перечислить их все за полиномиальное время . Однако известны алгоритмы составления списка всех остовных деревьев за полиномиальное время для каждого дерева. ^[26]

В бесконечных графах

Каждый конечный связный граф имеет остовное дерево. Однако для бесконечных связных графов существование остовных деревьев эквивалентно аксиоме выбора . Бесконечный граф связен, если каждая пара его вершин образует пару концов конечного пути. Как и в случае с конечными графами, дерево представляет собой связный граф без конечных циклов, а остовное дерево можно определить либо как максимальный ациклический набор ребер, либо как дерево, содержащее каждую вершину. ^[27]

Деревья внутри графа могут быть частично упорядочены по отношению к их подграфам, и любая бесконечная цепочка в этом частичном порядке имеет верхнюю границу (объединение деревьев в цепочке). Лемма Цорна , одно из многих эквивалентных утверждений выбранной аксиомы, требует, чтобы частичный порядок, в котором все цепи ограничены сверху, имел максимальный элемент; в частичном порядке на деревьях графа этот максимальный элемент должен быть остовным деревом. Следовательно, если принять лемму Цорна, каждый бесконечный связный граф имеет остовное дерево. ^[27]

В другом направлении, учитывая семейство множеств , можно построить бесконечный граф, такой, что каждое остовное дерево графа соответствует функции выбора семейства множеств. Следовательно, если каждый бесконечный связный граф имеет остовное дерево, то выбранная аксиома верна. ^[28]

В направленных мультиграфах

Идею остовного дерева можно обобщить на ориентированные мультиграфы. ^[29] Учитывая вершину v в направленном мультиграфе G , ориентированное остовное дерево T с корнем в v является ациклическим подграфом G , в котором каждая вершина, отличная от v, имеет исходящую степень 1. Это определение удовлетворяется только тогда, когда «ветви» T указать на v .

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

• Алгоритм заливки
• Хорошее остовное дерево - остовное дерево для встроенного планарного графа.

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

1. "Дерево". Документация NetworkX 2.6.2 . Проверено 10 декабря 2021 г. К деревьям и древовидениям можно добавить прилагательное «охват», чтобы обозначить, что граф, если рассматривать его как лес/ветвление, состоит из одного дерева/древесности, которое включает в себя все узлы графа.
2. Грэм, РЛ; Черт, Павол (1985). «К истории проблемы минимального остовного дерева» (PDF) .
3. Борг, Анита. «Фольклор проектирования сетевых протоколов». YouTube . Исследования Майкрософт . Проверено 13 мая 2022 г.
4. Бейнеке, Лоуэлл В .; Уилсон, Робин Дж. (2009), Темы топологической теории графов , Энциклопедия математики и ее приложений, том. 128, Издательство Кембриджского университета, Кембридж, с. 36, номер домена : 10.1017/CBO9781139087223, ISBN 978-0-521-80230-7, МР  2581536
5. Кочай и Креер (2004), стр. 65–67.
6. Кочай и Креер (2004), стр. 67–69.
7. Оксли, Дж. Г. (2006), Теория матроидов, Оксфордские тексты для выпускников по математике , том. 3, Издательство Оксфордского университета, с. 141, ISBN 978-0-19-920250-8.
8. Хартсфилд, Нора; Рингель, Герхард (2003), «Жемчужины теории графов: всестороннее введение» , Courier Dover Publications, стр. 100, ISBN 978-0-486-43232-8.
9. Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы, Cambridge University Press, стр. 163, ISBN 978-0-521-45761-3.
10. Боллобас, Бела (1998), Современная теория графов, Тексты для выпускников по математике, том. 184, Спрингер, с. 350, ISBN 978-0-387-98488-9; Мельхорн, Курт (1999), LEDA: платформа для комбинаторных и геометрических вычислений, Cambridge University Press, стр. 260, ISBN 978-0-521-56329-1.
11. Гросс, Джонатан Л.; Йеллен, Джей (2005), Теория графов и ее приложения (2-е изд.), CRC Press, стр. 168, ISBN 978-1-58488-505-4; Бонди, Дж.А.; Мурти, USR (2008), Теория графов, Тексты для аспирантов по математике, том. 244, Спрингер, с. 578, ISBN 978-1-84628-970-5.
12. Айгнер, Мартин ; Циглер, Гюнтер М. (1998), Доказательства из КНИГИ , Springer-Verlag , стр. 141–146..
13. Харари, Фрэнк ; Хейс, Джон П.; Ву, Хорнг-Джых (1988), «Обзор теории графов гиперкубов», Computers & Mathematics with Applications , 15 (4): 277–289, doi : 10.1016/0898-1221(88)90213-1, hdl : 2027.42/27522 , МР  0949280.
14. Кочай, Уильям; Креер, Дональд Л. (2004), «5.8 Теорема о матричном дереве», Графики, алгоритмы и оптимизация, Дискретная математика и ее приложения, CRC Press, стр. 111–116, ISBN 978-0-203-48905-5.
15. Кочай и Креер (2004), с. 109.
16. Боллобас (1998), с. 351.
17. Голдберг, Луизиана ; Джеррум, М. (2008), «Неприближаемость полинома Тутте», Information and Computation , 206 (7): 908–929, arXiv : cs/0605140 , doi : 10.1016/j.ic.2008.04.003; Джагер, Ф.; Вертиган, ДЛ; Уэлш, DJA (1990), «О вычислительной сложности полиномов Джонса и Тутта», Mathematical Proceedings of the Cambridge Philosophical Society , 108 : 35–53, doi : 10.1017/S0305004100068936.
18. Козен, Декстер (1992), Разработка и анализ алгоритмов, Монографии по информатике, Springer, стр. 19, ISBN 978-0-387-97687-7.
19. де Фрессе, Юбер; Розенштиль, Пьер (1982), «Характеристика планарности с поиском в глубину», Теория графов (Кембридж, 1981) , Ann. Дискретная математика., вып. 13, Амстердам: Северная Голландия, стр. 75–80, MR  0671906..
20. Рейф, Джон Х. (1985), «Поиск в глубину по своей сути последователен», Information Processing Letters , 20 (5): 229–234, doi : 10.1016/0020-0190(85)90024-9, MR  0801987.
21. Галлагер, Р.Г.; Хамблет, Пенсильвания; Спира, PM (1983), «Распределенный алгоритм для связующих деревьев с минимальным весом», ACM Transactions on Programming Languages ​​and Systems , 5 (1): 66–77, doi : 10.1145/357195.357200 , заархивировано из оригинала 8 декабря, 2023 год; Газит, Гилель (1991), «Оптимальный рандомизированный параллельный алгоритм для поиска связных компонентов в графе», SIAM Journal on Computing , 20 (6): 1046–1067, doi : 10.1137/0220066, MR  1135748; Бадер, Дэвид А.; Конг, Гоцзин (2005), «Быстрый параллельный алгоритм связующего дерева для симметричных мультипроцессоров (SMP)» (PDF) , Journal of Parallel and Distributed Computing , 65 (9): 994–1006, doi : 10.1016/j.jpdc. 2005.03.011, заархивировано из оригинала (PDF) 23 сентября 2015 г..
22. Эппштейн, Дэвид (1999), «Соединительные деревья и гаечные ключи» (PDF) , в Саке, Дж.-Р. ; Уррутия, Дж. (ред.), Справочник по вычислительной геометрии , Elsevier, стр. 425–461, заархивировано (PDF) из оригинала 2 августа 2023 г..
23. Ву, Бан Е; Чао, Кун-Мао (2004), Связующие деревья и проблемы оптимизации , CRC Press, ISBN 1-58488-436-3.
24. Уилсон, Дэвид Брюс (1996), «Генерация случайных остовных деревьев быстрее, чем время покрытия», Труды двадцать восьмого ежегодного симпозиума ACM по теории вычислений (STOC 1996) , стр. 296–303, doi : 10.1145 /237814.237880, МР  1427525.
25. МакДиармид, Колин; Джонсон, Теодор; Стоун, Гарольд С. (1997), «О поиске минимального остовного дерева в сети со случайными весами» (PDF) , Случайные структуры и алгоритмы , 10 (1–2): 187–204, doi : 10.1002/(SICI) 1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y, MR  1611522.
26. Габоу, Гарольд Н .; Майерс, Юджин В. (1978), «Нахождение всех остовных деревьев ориентированных и неориентированных графов», SIAM Journal on Computing , 7 (3): 280–287, doi : 10.1137/0207024, MR  0495152
27. Серр, Жан-Пьер (2003), Деревья , Монографии Спрингера по математике, Springer, стр. 23.
28. Соукуп, Лайош (2008), «Бесконечная комбинаторика: от конечного к бесконечному», Горизонты комбинаторики , Bolyai Soc. Математика. Студ., вып. 17, Берлин: Springer, стр. 189–213, номер документа : 10.1007/978-3-540-77200-2_10, MR  2432534.. См., в частности, теорему 2.1, стр. 192–193.
29. Левин, Лайонел (2011). «Группы песочниц и остовные деревья ориентированных линейных графов». Журнал комбинаторной теории, серия А. 118 (2): 350–364. arXiv : 0906.2809 . дои : 10.1016/j.jcta.2010.04.001 . ISSN  0097-3165.