Персональные инструменты
 

Минимальное остовное дерево — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показано 5 промежуточных версий 3 участников)
Строка 1: Строка 1:
Задача о минимальном остовном дереве (В англоязычной литературе — ''Minimum Spanning Tree''), заключается в следующем:
+
#REDIRECT [[discopal:{{PAGENAME}}]]
 
+
Задан связный неориентированный граф ''G=(V,E)'', где ''V'' — множество вершин, ''|V|=n'', ''E'' — множество ребер между ними, и весовая функция <math>w: E \rightarrow Z+</math>.
+
 
+
Иными словами, есть ''n'' вершин <math>v_1,\ldots,v_n</math> и положительные целые веса
+
дуг <math>w_{ij} \equiv w(v_i,v_j)</math> между ними.
+
(Можно вводить веса на ребрах, как <math>w_e,\; e \in E</math>).
+
 
+
Чему равен наименьший возможный вес остовного дерева?
+
Т.е., требуется найти минимально возможное значение суммы
+
<math>\sum_{(i,j)\in T} w(v_i,v_j)</math>
+
где минимум берется по всем остовным деревьям на ''n'' вершинах, т. е. по всем
+
множествам ''T'' из ''(n-1)'' дуг, связывающим все ''n'' вершин в единую сеть.
+
 
+
Для решения этой задачи можно применять:
+
 
+
* [[алгоритм Прима]] ;
+
* алгоритм Краскала (Kruskal).
+
 
+
[[Category:Задачи]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:24, 13 июня 2011

  1. REDIRECT discopal:Минимальное остовное дерево