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

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:24:46Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

WikiSysop: 1 версия

2008-10-23T16:48:13Z

1 версия

StasFomin: обновление данных

2008-10-22T15:36:14Z

обновление данных

WikiSysop: 1 версия

2008-08-04T09:55:52Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2006-04-20T19:08:13Z

реплицировано из внутренней CustisWiki

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

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

Задан связный неориентированный граф ''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}}

StasFomin в 16:22, 19 апреля 2006

2006-04-19T16:22:56Z

BenderBot: реплицировано из внутренней CustisWiki

2005-12-08T04:42:09Z

реплицировано из внутренней CustisWiki

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

← Предыдущая		Версия 16:22, 19 апреля 2006
Строка 1:		Строка 1:
−	Задача о минимальном остовном дереве (В англоязычной литературе — ''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'' — множество ребер между ними, и весовая функция <math>w: E \rightarrow Z+</math>.

← Предыдущая		Версия 04:42, 8 декабря 2005
(не показана 1 промежуточная версия 1 участника)
Строка 1:		Строка 1:
−	Задача о минимальном остовном дереве (В англоязычной литературе — [[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'' — множество ребер между ними, и весовая функция <math>w: E \rightarrow Z+</math>.

@@ Строка 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}}

← Предыдущая	Версия 16:48, 23 октября 2008
(нет различий)