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

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

Определение

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

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

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

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

Свойства

• Любое остовное дерево в графе с ${\displaystyle n}$ вершинами содержит ровно ${\displaystyle n-1}$ ребро.
• Число остовных деревьев в полном графе на ${\displaystyle n}$ вершинах равно ${\displaystyle n^{n-2};}$ это утверждение называется формулой Кэли^[1]:
• Число остовных деревьев в полном двудольном графе ${\displaystyle K_{m,n}}$ равно ${\displaystyle m^{n-1}\cdot n^{m-1}.}$
• В общем случае, число остовных деревьев в произвольном графе может быть вычислено при помощи так называемой матричной теоремы о деревьях.
• Пусть ${\displaystyle \rho }$ есть ребро в графе ${\displaystyle \Gamma .}$ Обозначим через ${\displaystyle \Gamma \backslash \rho }$ граф, полученный из ${\displaystyle \Gamma }$ выбрасыванием ребра ${\displaystyle \rho ,}$ и через ${\displaystyle \Gamma /\rho }$ граф, полученный из ${\displaystyle \Gamma }$ стягиванием ребра ${\displaystyle \rho }$ в точку. Если ребро ${\displaystyle \rho }$ не является петлёй в ${\displaystyle \Gamma ,}$ тогда выполняется следующее соотношение, называемое удаление-плюс-стягивание^[2]:

  ${\displaystyle \tau (\Gamma )=\tau (\Gamma \backslash \rho )+\tau (\Gamma /\rho ),}$

где ${\displaystyle \tau (\Gamma )}$ обозначает число остовных деревьев в графе ${\displaystyle \Gamma .}$

Алгоритмы

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

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

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

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

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

Выделение остовного дерева и подсчет числа удалённых рёбер в графах электрических цепей используется для вычисления количества независимых контуров при анализе электрической цепи методом контурных токов^[4].

См. также

• Матричная теорема о деревьях
• Минимальное остовное дерево
• Теорема Кэли о числе деревьев
• STP — канальный протокол.

Примечания

Эта страница в последний раз была отредактирована 15 октября 2023 в 10:55.