logo
ЭУМКД_ДиВМ3

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

(Spanning tree)

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

Любое остовное дерево в графе с вершинами содержит ребро.

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

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

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4