|
|
| Строка 1: |
Строка 1: |
| − | Задача о минимальном остовном дереве (В англоязычной литературе — [[Minimum Spanning Tree|«Minimum Spanning Tree»]]), заключается в следующем:
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | | + | |
| − | Задан связный неориентированный граф ''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}}
| + | |
