Остовное дерево

Пример решетчатого графа с 16 вершинами и один из вариантов выделения остовного дерева этого графа. Рёбра остовного дерева изображены утолщёнными синими линиями.

О́стовное де́рево графа (англ. Spanning tree) — это дерево, подграф данного графа, с тем же числом вершин, что и у исходного графа. Неформально говоря, остовное дерево получается из исходного графа удалением максимального числа рёбер, входящих в циклы, но без нарушения связности графа. Остовное дерево включает в себя все $n$ вершин исходного графа и содержит $n-1$ ребро.

Определение

Остовное дерево — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.

Понятие остовный лес неоднозначно, под ним могут понимать один из следующих подграфов:

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

Остовное дерево также иногда называют покрывающим деревом, остовом или скелетом графа. Ударение в слове «остовный» у разных авторов указывается на первый (от слова о́стов) или на второй слог.

Свойства

• Любое остовное дерево в графе с $n$ вершинами содержит ровно $n-1$ ребро.
• Число остовных деревьев в полном графе на $n$ вершинах равно $n^{n-2};$ это утверждение называется формулой Кэли:
• Число остовных деревьев в полном двудольном графе $K_{m,n}$ равно $m^{n-1}\cdot n^{m-1}.$
• В общем случае, число остовных деревьев в произвольном графе может быть вычислено при помощи так называемой матричной теоремы о деревьях.
• Пусть $\rho$ есть ребро в графе $\mathrm{\Gamma }.$ Обозначим через $\mathrm{\Gamma }\mathrm{\setminus }\rho$ граф, полученный из $\mathrm{\Gamma }$ выбрасыванием ребра $\rho ,$ и через $\mathrm{\Gamma }/\rho$ граф, полученный из $\mathrm{\Gamma }$ стягиванием ребра $\rho$ в точку. Если ребро $\rho$ не является петлёй в $\mathrm{\Gamma },$ тогда выполняется следующее соотношение, называемое удаление-плюс-стягивание:

  $\tau (\mathrm{\Gamma })=\tau (\mathrm{\Gamma }\mathrm{\setminus }\rho )+\tau (\mathrm{\Gamma }/\rho ),$

где $\tau (\mathrm{\Gamma })$ обозначает число остовных деревьев в графе $\mathrm{\Gamma }.$

Алгоритмы

Остовное дерево может быть построено практически любым алгоритмом обхода графа, например поиском в глубину или поиском в ширину. Оно состоит из всех пар рёбер $(u,v),$ таких, что алгоритм, просматривая вершину $u,$ обнаруживает в её списке смежности новую, не обнаруженную ранее вершину $v.$

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

Существует также несколько параллельных и распределённых алгоритмов нахождения остовного дерева. Как практический пример распределённого алгоритма можно привести протокол STP.

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

Задача о нахождении остовного дерева, в котором степень каждой вершины не превышает некоторой наперёд заданной константы $k$, является NP-полной.

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

См. также

• Матричная теорема о деревьях
• Минимальное остовное дерево
• Теорема Кэли о числе деревьев
• STP — канальный протокол.