WikiSysop: 1 версия

2008-10-23T16:48:13Z

1 версия

Новая страница

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

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

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

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

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

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

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

Минимальное остовное дерево - История изменений

WikiSysop: 1 версия