Остовное дерево - Spanning tree

Остовное дерево (синие жирные ребра) сеточного графа

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

Приложения

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

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

Интернет и многие другие телекоммуникационные сети имеют каналы передачи, которые соединяют узлы вместе в ячеистой топологии, которая включает в себя несколько петель. Для того , чтобы избежать петель моста и петель маршрутизации , много протоколов маршрутизации , предназначенных для таких сетей, в том числе в протокол Spanning Tree Protocol , кратчайшего пути , протокол состояния канала , на основе дерева дополненной маршрутизации и т.д., требуют , чтобы каждый маршрутизатор помню остовное дерево.

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

Определения

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

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

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

Фундаментальные сокращения

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

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

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

В несвязных графах не может быть остовного дерева, и вместо этого нужно рассматривать остовные леса . Здесь есть два конкурирующих определения:

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

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

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

Формула Кэли подсчитывает количество остовных деревьев на полном графе. Есть деревья внутри , деревья внутри и деревья внутри .

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

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

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

  • Если G сама является деревом, то t ( G ) = 1 .
  • Когда G - граф циклов C n с n вершинами, то t ( G ) =  n .
  • Для полного графа с n вершинами формула Кэли дает количество остовных деревьев как n n  - 2 .
  • Если G - полный двудольный граф , то .
  • Для n- мерного графа гиперкуба количество остовных деревьев равно .

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

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

В частности, для вычисления т ( 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 / е ), где G  -  е это мультиграф получается удалением е и G / е является сокращение от G по е . Член t ( G  -  e ) в этой формуле подсчитывает остовные деревья  G, которые не используют ребро  e , а член t ( G / e ) считает остовные деревья  G, которые используют  e .

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

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

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

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

Алгоритмы

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

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

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

Оптимизация

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

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

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

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

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

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

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

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

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

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

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

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

Идея остовного дерева может быть обобщена на ориентированные мультиграфы. Принимая во внимание вершины v на направленный мультиграфе G , ориентированный связующее дерево Т с корнем V представляет собой ациклический подграф G , в котором каждая вершина, кроме V имеет полустепень 1. Это определение выполняется только тогда , когда «ветвь» Т точки в направлении против .

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

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