Изменения
→Необходимые определения
Рассмотрим связный неориентированный взвешенный [[Основные определения теории графов|граф]] <tex> G =( V, E ) </tex>, где <tex>V </tex> {{---}} множество [[Основные определения теории графов| вершин]], <tex>E </tex> {{---}} множество [[Основные определения теории графов|ребер]]. Вес ребра определяется, как функция <tex> w : E \to \mathbb{R} </tex>.
{{Определение
|neat id = 1spanning_tree
|definition =
'''Остовное дерево''' (англ. ''spanning tree'') графа <tex> G = ( V, E ) </tex> {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.}}{{Определение
|definition =
'''Минимальное остовное дерево''' (англ. ''minimum spanning tree'') графа <tex> G = ( V, E ) </tex> {{---}} это его ациклический связный подграф, в который входят все его вершины, обладающий минимальным суммарным весом ребер.
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ : Вильямс, 2-е издание, 2005, С. 644-649
[[Категория: Алгоритмы и структуры данных]][[Категория: Остовные деревья ]][[Категория: Построение остовных деревьев]]
