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

Материал из свободной русской энциклопедии «Традиция»
(перенаправлено с «Minimum Spanning Tree»)
Перейти к: навигация, поиск

Задача о минимальном остовном дереве (В англоязычной литературе — «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 вершин в единую сеть.

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


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