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

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

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

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

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

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


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