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

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

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

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

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

Свойства

• Любое остовное дерево в графе с $n$ вершинами содержит ровно $n - 1$ ребро.
• Число остовных деревьев в полном графе на $n$ вершинах выражается знаменитой формулой Кэли:^[2]

  $\! n^{n-2}$

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

Алгоритмы

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

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

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

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

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

См. также

• Минимальное остовное дерево
• Spanning Tree Protocol

Примечания

1. ↑ «Остовный» в словарях русского языка
2. ↑ Martin Aigner, Günter M. Ziegler. Proofs from the book. — Springer-Verlag, 2004. — P. 173—178. — ISBN 978-3540404606
3. ↑ Garey, Michael R. & Johnson, David S. (1979), «Computers and Intractability: A Guide to the Theory of NP-Completeness», W.H. Freeman, сс. 206, ISBN 0-7167-1045-5