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


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

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

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

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

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

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