В математической области теории графов остовное дерево 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]
Совокупность непересекающихся (несвязанных) деревьев описывается как лес . Охватывающий лес в графе — это подграф, представляющий собой лес с дополнительным требованием. Используются два несовместимых требования, одно из которых встречается относительно редко.
Чтобы избежать путаницы между этими двумя определениями, Гросс и Йеллен (2005) предлагают термин «полный остовный лес» для остовного леса с тем же количеством компонентов, что и данный граф (т. е. максимальный лес), а Бонди и Мерти (2008) ) вместо этого назовите этот тип леса «максимальным остовным лесом» (что избыточно, поскольку максимальный лес обязательно содержит каждую вершину). [11]
Число t ( G ) остовных деревьев связного графа является хорошо изученным инвариантом .
В некоторых случаях легко вычислить t ( G ) напрямую:
В более общем смысле, для любого графа G число t ( G ) можно вычислить за полиномиальное время как определитель матрицы, полученной из графа, используя теорему Кирхгофа о дереве матриц . [14]
В частности, для вычисления t ( G ) строится матрица Лапласа графа, квадратная матрица, в которой строки и столбцы индексируются вершинами G . Запись в строке 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 .
К деревьям и древовидениям можно добавить прилагательное «охват», чтобы обозначить, что граф, если рассматривать его как лес/ветвление, состоит из одного дерева/древесности, которое включает в себя все узлы графа.