Введение

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

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

Приложения

Несколько алгоритмов поиска пути, включая алгоритм Дейкстры и алгоритм A*, внутренне строят остовное дерево как промежуточный шаг при решении задачи. Для минимизации стоимости энергосетей, проводных соединений, трубопроводов, систем автоматического распознавания речи и т. п., часто используются алгоритмы, которые постепенно строят остовное дерево (или множество таких деревьев) как промежуточные этапы в процессе поиска минимального остовного дерева. Интернет и многие другие телекоммуникационные сети имеют каналы связи, соединяющие узлы в сетчатой топологии, включающей петли. Чтобы избежать петель мостов и маршрутизации, многие протоколы маршрутизации, разработанные для таких сетей, включая протокол Spanning Tree, Open Shortest Path First, протокол маршрутизации на основе состояния каналов, маршрутизацию на основе расширенных деревьев и т. д., требуют от каждого маршрутизатора хранения остовного дерева. Особый вид остовного дерева, дерево Сюонга, используется в топологической теории графов для поиска графовых вложений с максимальным родом. Дерево Сюонга – это остовное дерево, в котором количество связных компонент с нечетным числом ребер в оставшемся графе минимально возможно. Дерево Сюонга и соответствующее вложение с максимальным родом могут быть найдены за полиномиальное время.

Определения

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

Основные циклы

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

Основные наборы

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

Расширяющие леса

Совокупность несвязных (не связанных) деревьев описывается как лес. Охватывающим лесом в графе является подграф, который представляет собой лес с дополнительным требованием. Существует два несовместимых требования, одно из которых встречается относительно редко. Почти во всех книгах и статьях по теории графов охватывающий лес определяется как лес, охватывающий все вершины, то есть содержащий каждую вершину графа. Связный граф может иметь несвязный охватывающий лес, например, лес без рёбер, в котором каждая вершина образует отдельное дерево. Некоторые авторы теории графов определяют охватывающий лес как максимальный ациклический подграф данного графа, или, что эквивалентно, подграф, состоящий из остовного дерева в каждом связном компоненте графа. Чтобы избежать путаницы между этими двумя определениями, предлагаем называть "полным охватывающим лесом" лес с тем же количеством компонент, что и исходный граф (то есть максимальный лес), а вместо этого называть этот вид леса "максимальным охватывающим лесом" (что избыточно, поскольку максимальный лес обязательно содержит все вершины).

Подсчет пересекающих деревьев

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

Полный полином

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

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

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

Оптимизация

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

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

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

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

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

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

Идея о spanning tree может быть обобщена на ориентированные мультиграфы. Для заданной вершины v в ориентированном мультиграфе G, ориентированное spanning tree T с корнем в v — это ациклический подграф G, в котором у каждой вершины, кроме v, исходящая степень равна 1. Это определение выполняется только если "ветви" T направлены к v.