Русская Википедия:Остовное дерево
О́стовное де́рево графа (англ. Spanning tree) — это дерево, подграф данного графа, с тем же числом вершин, что и у исходного графа. Неформально говоря, остовное дерево получается из исходного графа удалением максимального числа рёбер, входящих в циклы, но без нарушения связности графа. Остовное дерево включает в себя все <math>n</math> вершин исходного графа и содержит <math>n - 1</math> ребро.
Определение
Остовное дерево — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
Понятие остовный лес неоднозначно, под ним могут понимать один из следующих подграфов:
- любой ациклический подграф, в который входят все вершины графа, но не обязательно связный;
- в несвязном графе — подграф, состоящий из объединения остовных деревьев для каждой его компоненты связности.
Остовное дерево также иногда называют покрывающим деревом, остовом или скелетом графа. Ударение в слове «остовный» у разных авторов указывается на первый (от слова о́стов) или на второй слог.
Свойства
- Любое остовное дерево в графе с <math>n</math> вершинами содержит ровно <math>n - 1</math> ребро.
- Число остовных деревьев в полном графе на <math>n</math> вершинах равно <math>n^{n-2};</math> это утверждение называется формулой Кэли[1]:
- Число остовных деревьев в полном двудольном графе <math>K_{m,n}</math> равно <math>m^{n-1}\cdot n^{m-1}.</math>
- В общем случае, число остовных деревьев в произвольном графе может быть вычислено при помощи так называемой матричной теоремы о деревьях.
- Пусть <math>\rho</math> есть ребро в графе <math>\Gamma.</math> Обозначим через <math>\Gamma\backslash\rho</math> граф, полученный из <math>\Gamma</math> выбрасыванием ребра <math>\rho,</math> и через <math>\Gamma/\rho</math> граф, полученный из <math>\Gamma</math> стягиванием ребра <math>\rho</math> в точку. Если ребро <math>\rho</math> не является петлёй в <math>\Gamma,</math> тогда выполняется следующее соотношение, называемое удаление-плюс-стягивание[2]:
- <math>\tau(\Gamma)=\tau(\Gamma\backslash\rho)+\tau(\Gamma/\rho),</math>
- где <math>\tau(\Gamma)</math> обозначает число остовных деревьев в графе <math>\Gamma.</math>
Алгоритмы
Остовное дерево может быть построено практически любым алгоритмом обхода графа, например поиском в глубину или поиском в ширину. Оно состоит из всех пар рёбер <math>(u, v),</math> таких, что алгоритм, просматривая вершину <math>u,</math> обнаруживает в её списке смежности новую, не обнаруженную ранее вершину <math>v.</math>
Остовные деревья, построенные при обходе графа из вершины <math>s</math> алгоритмом Дейкстры, обладают тем свойством, что кратчайший путь в графе из <math>s</math> до любой другой вершины — это (он же единственный) путь из <math>s</math> до этой вершины в построенном остовном дереве.
Существует также несколько параллельных и распределённых алгоритмов нахождения остовного дерева. Как практический пример распределённого алгоритма можно привести протокол STP.
Если каждому ребру графа присвоен вес (длина, стоимость и т. п.), то нахождением оптимального остовного дерева, которое минимизирует сумму весов входящих в него рёбер, занимаются многочисленные алгоритмы нахождения минимального остовного дерева.
Задача о нахождении остовного дерева, в котором степень каждой вершины не превышает некоторой наперёд заданной константы <math>k</math>, является NP-полной[3].
Выделение остовного дерева и подсчет числа удалённых рёбер в графах электрических цепей используется для вычисления количества независимых контуров при анализе электрической цепи методом контурных токов[4].
См. также
- Матричная теорема о деревьях
- Минимальное остовное дерево
- Теорема Кэли о числе деревьев
- STP — канальный протокол.
Примечания
