|
|
| (не показано 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}} | + | |
