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

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

ОпределениеПравить

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

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

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

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

СвойстваПравить

  • Любое остовное дерево в графе с   вершинами содержит ровно   ребро.
  • Число остовных деревьев в полном графе на   вершинах равно  ; это утверждение называется формулой Кэли:[1]
  • Число остовных деревьев в полном двудольном графе   равно  .
  • В общем случае, число остовных деревьев в произвольном графе может быть вычислено при помощи так называемой матричной теоремы о деревьях.
  • Пусть   есть ребро в графе  . Обозначим через   граф, полученный из   выбрасыванием ребра  , и через   граф, полученный из   стягиванием ребра   в точку. Если ребро   не является петлёй в  , тогда выполняется следующее соотношение, называемое удаление-плюс-стягивание:[2]
     
где   обозначает число остовных деревьев в графе  .

АлгоритмыПравить

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

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

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

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

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

См. такжеПравить

ПримечанияПравить

  1. Martin Aigner, Günter M. Ziegler. Proofs from the book. — Springer-Verlag, 2004. — P. 173—178. — ISBN 978-3540404606.
  2. А. Петрунин. Сколько деревьев в графе (рус.) // Квант. — 2018. — № 9. — С. 9—13. — doi:10.4213/kvant20180902.
  3. Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W.H. Freeman, 1979. — С. 206. — ISBN 0-7167-1045-5.