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

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

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

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

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

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


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