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

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

Приложения

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

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

Интернет и многие другие телекоммуникационные сети имеют каналы передачи, которые соединяют узлы вместе в топологии сетки , которая включает некоторые петли. Чтобы избежать мостовых петель и петель маршрутизации , многие протоколы маршрутизации, разработанные для таких сетей, включая протокол связующего дерева , Open Shortest Path First , протокол маршрутизации на основе состояния канала , маршрутизацию на основе расширенного дерева и т. д., требуют, чтобы каждый маршрутизатор помнил связующее дерево. ^[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]

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

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

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

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

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

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

Алгоритм затопления
Хорошее остовное дерево – остовное дерево для вложенного планарного графа

Ссылки

^ "Дерево". Документация NetworkX 2.6.2 . Получено 10.12.2021 . Для деревьев и древовидных структур можно добавить прилагательное "охватывающий", чтобы обозначить, что граф, рассматриваемый как лес/ветвление, состоит из одного дерева/древовидной структуры, включающей все узлы в графе.
^ Грэм, Р. Л.; Хелл, Павол (1985). «Об истории проблемы минимального остовного дерева» (PDF) .
^ Борг, Анита. «Фольклор проектирования сетевых протоколов». YouTube . Microsoft Research . Получено 13 мая 2022 г. .
^ Бейнеке, Лоуэлл В .; Уилсон, Робин Дж. (2009), Темы топологической теории графов , Энциклопедия математики и ее приложений, т. 128, Cambridge University Press, Кембридж, стр. 36, doi :10.1017/CBO9781139087223, ISBN 978-0-521-80230-7, г-н 2581536
^ Кочай и Крехер (2004), стр. 65–67.
^ Кочай и Крехер (2004), стр. 67–69.
^ Оксли, Дж. Г. (2006), Теория матроидов, Oxford Graduate Texts in Mathematics , т. 3, Oxford University Press, стр. 141, ISBN 978-0-19-920250-8.
^ ab Hartsfield, Nora; Ringel, Gerhard (2003), Pearls in Graph Theory: A Comprehensive Introduction , Courier Dover Publications, стр. 100, ISBN 978-0-486-43232-8.
^ Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы, Cambridge University Press, стр. 163, ISBN 978-0-521-45761-3.
^ Боллобаш, Бела (1998), Современная теория графов, Graduate Texts in Mathematics, т. 184, Springer, стр. 350, ISBN 978-0-387-98488-9; Мельхорн, Курт (1999), LEDA: Платформа для комбинаторных и геометрических вычислений, Cambridge University Press, стр. 260, ISBN 978-0-521-56329-1.
^ Гросс, Джонатан Л.; Йеллен, Джей (2005), Теория графов и ее приложения (2-е изд.), CRC Press, стр. 168, ISBN 978-1-58488-505-4; Бонди, JA; Мурти, USR (2008), Теория графов, Graduate Texts in Mathematics, т. 244, Springer, стр. 578, ISBN 978-1-84628-970-5.
^ Айгнер, Мартин ; Циглер, Гюнтер М. (1998), Доказательства из КНИГИ , Springer-Verlag , стр. 141–146..
^ Харари, Фрэнк ; Хейс, Джон П.; Ву, Хорнг-Джих (1988), «Обзор теории графов гиперкуба», Компьютеры и математика с приложениями , 15 (4): 277–289, doi :10.1016/0898-1221(88)90213-1, hdl : 2027.42/27522 , MR 0949280.
^ Кокай, Уильям; Крехер, Дональд Л. (2004), «5.8 Теорема о матричном дереве», Графы, алгоритмы и оптимизация, Дискретная математика и ее приложения, CRC Press, стр. 111–116, ISBN 978-0-203-48905-5.
^ Кочай и Крехер (2004), стр. 109.
^ Боллобаш (1998), стр. 351.
^ Голдберг, Л. А.; Джеррум , М. (2008), «Неприближенность полинома Тутте», Информация и вычисления , 206 (7): 908–929, arXiv : cs/0605140 , doi : 10.1016/j.ic.2008.04.003; Jaeger, F.; Vertigan, DL; Welsh, DJA (1990), "О вычислительной сложности полиномов Джонса и Тутта", Математические труды Кембриджского философского общества , 108 : 35–53, doi :10.1017/S0305004100068936.
^ Козен, Декстер (1992), Разработка и анализ алгоритмов, Монографии по информатике, Springer, стр. 19, ISBN 978-0-387-97687-7.
^ de Fraysseix, Hubert; Rosenstiehl, Pierre (1982), "Характеристика планарности с помощью поиска в глубину", Теория графов (Кембридж, 1981) , Ann. Discrete Math., т. 13, Амстердам: Северная Голландия, стр. 75–80, MR 0671906.
^ Рейф, Джон Х. (1985), «Поиск в глубину по своей сути последователен», Information Processing Letters , 20 (5): 229–234, doi :10.1016/0020-0190(85)90024-9, MR 0801987.
^ Галлагер, РГ; Хамблет, ПА; Спира, ПМ (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) , Журнал параллельных и распределенных вычислений , 65 (9): 994–1006, doi :10.1016/j.jpdc.2005.03.011, заархивировано из оригинала (PDF) 23 сентября 2015 г..
^ ab Eppstein, David (1999), «Охватывающие деревья и остовные элементы» (PDF) , в Sack, J.-R. ; Urrutia, J. (ред.), Handbook of Computational Geometry , Elsevier, стр. 425–461, архивировано (PDF) из оригинала 2 августа 2023 г..
^ У, Банг Йе; Чао, Кунь-Мао (2004), Связующие деревья и проблемы оптимизации , CRC Press, ISBN 1-58488-436-3.
^ Уилсон, Дэвид Брюс (1996), «Генерация случайных остовных деревьев быстрее, чем время покрытия», Труды Двадцать восьмого ежегодного симпозиума ACM по теории вычислений (STOC 1996) , стр. 296–303, doi :10.1145/237814.237880, MR 1427525.
^ МакДиармид, Колин; Джонсон, Теодор; Стоун, Гарольд С. (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.
^ Габов, Гарольд Н.; Майерс , Юджин В. (1978), «Нахождение всех остовных деревьев ориентированных и неориентированных графов», SIAM Journal on Computing , 7 (3): 280–287, doi :10.1137/0207024, MR 0495152
^ ab Serre, Jean-Pierre (2003), Деревья , Springer Monographs in Mathematics, Springer, стр. 23.
^ Соукуп, Лайош (2008), «Бесконечная комбинаторика: от конечного к бесконечному», Горизонты комбинаторики , Bolyai Soc. Math. Stud., т. 17, Берлин: Springer, стр. 189–213, doi :10.1007/978-3-540-77200-2_10, MR 2432534, См. в частности теорему 2.1, стр. 192–193.
^ Левин, Лайонел (2011). «Песочные группы и остовные деревья направленных линейных графов». Журнал комбинаторной теории, серия A. 118 ( 2): 350–364. arXiv : 0906.2809 . doi : 10.1016/j.jcta.2010.04.001 . ISSN 0097-3165.