Минимальное остовное дерево

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

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

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

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

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

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

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.