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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Свойства[править | править исходный текст]

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

Алгоритмы[править | править исходный текст]

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

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

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

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

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

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  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