Задача о минимальном остовном дереве (В англоязычной литературе — [[Minimum Spanning Tree|«Minimum Spanning Tree»]]), заключается в следующем:
Задача о минимальном остовном дереве (В англоязычной литературе — [[Minimum Spanning Tree|«Minimum Spanning Tree»]]), заключается в следующем:
−
Задан связный неориентированный граф ''G=(V,E)'', где ''V'' — множество вершин, ''|V|=n'', ''E'' — множество ребер между ними, и весовая функция <math>w: E \rightarrow Z+</math>.
+
Задан связный неориентированный граф ''G=(V,E)'', где ''V'' — множество вершин, ''|V|=n'', ''E'' — множество ребер между ними, и весовая функция <m>w: E \rightarrow Z+</m>.
−
Иными словами, есть ''n'' вершин <math>v_1,\ldots,v_n</math> и положительные целые веса
+
Иными словами, есть ''n'' вершин <m>v_1,\ldots,v_n</m> и положительные целые веса
−
дуг <math>w_{ij} \equiv w(v_i,v_j)</math> между ними.
+
дуг <m>w_{ij} \equiv w(v_i,v_j)</m> между ними.
−
(Можно вводить веса на ребрах, как <math>w_e,\; e \in E</math>).
+
(Можно вводить веса на ребрах, как <m>w_e,\; e \in E</m>).
Чему равен наименьший возможный вес остовного дерева?
Чему равен наименьший возможный вес остовного дерева?
Т.е., требуется найти минимально возможное значение суммы
Т.е., требуется найти минимально возможное значение суммы
−
<math>\sum_{(i,j)\in T} w(v_i,v_j)</math>
+
<m>\sum_{(i,j)\in T} w(v_i,v_j)</m>
где минимум берется по всем остовным деревьям на ''n'' вершинах, т. е. по всем
где минимум берется по всем остовным деревьям на ''n'' вершинах, т. е. по всем
множествам ''T'' из ''(n-1)'' дуг, связывающим все ''n'' вершин в единую сеть.
множествам ''T'' из ''(n-1)'' дуг, связывающим все ''n'' вершин в единую сеть.
Версия 18:36, 22 октября 2008
Задача о минимальном остовном дереве (В англоязычной литературе — «Minimum Spanning Tree»), заключается в следующем:
Задан связный неориентированный граф G=(V,E), где V — множество вершин, |V|=n, E — множество ребер между ними, и весовая функция .
Иными словами, есть n вершин и положительные целые веса
дуг между ними.
(Можно вводить веса на ребрах, как ).
Чему равен наименьший возможный вес остовного дерева?
Т.е., требуется найти минимально возможное значение суммы
где минимум берется по всем остовным деревьям на n вершинах, т. е. по всем
множествам T из (n-1) дуг, связывающим все n вершин в единую сеть.
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
