О́стовное де́рево графа (англ. Spanning tree) — это дерево, подграф данного графа, с тем же числом вершин, что и у исходного графа. Неформально говоря, остовное дерево получается из исходного графа удалением максимального числа рёбер, входящих в циклы, но без нарушения связности графа. Остовное дерево включает в себя все вершин исходного графа и содержит ребро.
Определение Остовное дерево — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
Понятие остовный лес неоднозначно, под ним могут понимать один из следующих подграфов: любой ациклический подграф, в который входят все вершины графа, но не обязательно связный; в несвязном графе — подграф, состоящий из объединения остовных деревьев для каждой его компоненты связности.
Остовное дерево также иногда называют покрывающим деревом, остовом или скелетом графа. Ударение в слове «остовный» у разных авторов указывается на первый (от слова о́стов) или на второй слог.
Свойства Любое остовное дерево в графе с вершинами содержит ровно ребро. Число остовных деревьев в полном графе на вершинах равно это утверждение называется формулой Кэли: Число остовных деревьев в полном двудольном графе равно В общем случае, число остовных деревьев в произвольном графе может быть вычислено при помощи так называемой матричной теоремы о деревьях. Пусть есть ребро в графе Обозначим через граф, полученный из выбрасыванием ребра и через граф, полученный из стягиванием ребра в точку. Если ребро не является петлёй в тогда выполняется следующее соотношение, называемое удаление-плюс-стягивание:
где обозначает число остовных деревьев в графе
Алгоритмы Остовное дерево может быть построено практически любым алгоритмом обхода графа, например поиском в глубину или поиском в ширину. Оно состоит из всех пар рёбер таких, что алгоритм, просматривая вершину обнаруживает в её списке смежности новую, не обнаруженную ранее вершину
Остовные деревья, построенные при обходе графа из вершины алгоритмом Дейкстры, обладают тем свойством, что кратчайший путь в графе из до любой другой вершины — это (он же единственный) путь из до этой вершины в построенном остовном дереве.
Существует также несколько параллельных и распределённых алгоритмов нахождения остовного дерева. Как практический пример распределённого алгоритма можно привести протокол STP.
Если каждому ребру графа присвоен вес (длина, стоимость и т. п.), то нахождением оптимального остовного дерева, которое минимизирует сумму весов входящих в него рёбер, занимаются многочисленные алгоритмы нахождения минимального остовного дерева.
Задача о нахождении остовного дерева, в котором степень каждой вершины не превышает некоторой наперёд заданной константы , является NP-полной.
Выделение остовного дерева и подсчет числа удалённых рёбер в графах электрических цепей используется для вычисления количества независимых контуров при анализе электрической цепи методом контурных токов.
См. также Матричная теорема о деревьях Минимальное остовное дерево Теорема Кэли о числе деревьев STP — канальный протокол.
Примечания
Категория:Теория графов *