Просмотр исходного текста страницы Минимальное остовное дерево

Задача о минимальном остовном дереве (В англоязычной литературе — [[Minimum Spanning Tree|«Minimum Spanning Tree»]]), заключается в следующем:

Задан связный неориентированный граф ''G=(V,E)'', где ''V'' — множество вершин, ''|V|=n'', ''E'' — множество ребер между ними, и весовая функция <math>w: E \rightarrow Z+</math>.

Иными словами, есть ''n'' вершин <math>v_1,\ldots,v_n</math> и положительные целые веса
дуг <math>w_{ij} \equiv w(v_i,v_j)</math> между ними.
(Можно вводить веса на ребрах, как <math>w_e,\; e \in E</math>).

Чему равен наименьший возможный вес остовного дерева?
Т.е., требуется найти минимально возможное значение суммы
<math>\sum_{(i,j)\in T} w(v_i,v_j)</math>
где минимум берется по всем остовным деревьям на ''n'' вершинах, т. е. по всем
множествам ''T'' из ''(n-1)'' дуг, связывающим все ''n'' вершин в единую сеть.

Для решения этой задачи можно применять:

* [[алгоритм Прима]] ;
* алгоритм Краскала (Kruskal).

[[Category:Задачи]]
{{replicate-from-custiswiki-to-lib}}