Остовное дерево графа состоит из минимального подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам.
Остовное дерево — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
Понятие остовный лес неоднозначно, под ним могут понимать один из следующих подграфов:
Остовное дерево также иногда называют покрывающим деревом, остовом или скелетом графа. Ударение в слове «остовный» у разных авторов указывается на первый[1] (от слова о́стов) или на второй слог.
Остовное дерево может быть построено практически любым алгоритмом обхода графа, например поиском в глубину или поиском в ширину. Оно состоит из всех пар рёбер , таких, что алгоритм, просматривая вершину , обнаруживает в её списке смежности новую, не обнаруженную ранее вершину .
Остовные деревья, построенные при обходе графа алгоритмом Дейкстры, начиная из вершины , обладают тем свойством, что кратчайший путь в графе из до любой другой вершины — это (единственный) путь из до этой вершины в построенном остовном дереве.
Существует также несколько параллельных и распределённых алгоритмов нахождения остовного дерева. Как практический пример распределённого алгоритма можно привести протокол STP.
Если каждому ребру графа присвоен вес (длина, стоимость и т. п.), то нахождением оптимального остовного дерева, которое минимизирует сумму весов входящих в него рёбер, занимаются многочисленные алгоритмы нахождения минимального остовного дерева[4].
Задача о нахождении остовного дерева, в котором степень каждой вершины не превышает некоторой наперёд заданной константы , является NP-полной.[5]
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .