3.5.2. Построение остова минимального веса
Решение этой задачи имеет большое значение в создании вычислительных сетей, в организации грузоперевозок или ремонтных работ на транспортной сети..
Основная идея состоит в следующем: если есть некоторый фрагмент остова G’=<X’; r’`> и ребро минимального веса l(хi;хj), одна из концевых вершин которого хi принадлежит фрагменту G’, то включить в фрагмент вторую вершину ребра хj и само ребро l(хi;хj). Процедуру продолжать до включения во фрагмент (n-1) ребра графа, где n-число вершин. Эта идея реализуется двумя алгоритмами: Дейкстра и Краскала.
Алгоритм Дейкстра:
шаг 1: определить начальную вершину остова x0;
шаг2: выбрать ребро минимального веса, смежное с начальной вершиной и сформировать фрагмент G’=<X’; r’`>, включив вторую концевую вершину в подмножество Х’;
шаг3: выбрать ребро минимального веса, смежное вершинам фрагмента и не являющееся петлей:
а) если вторая концевая вершина не принадлежит фрагменту,
то включить ее в подмножество Х’, а ребро включить в фрагмент остова G’=<X’; r’`>,
b) если вторая концевая вершина принадлежит фрагменту, то исключить данное ребро из анализа;
шаг 4: если все вершины графа вошли во фрагмент остова, то конец, иначе перейти к шагу 2.
Пример: найти для графа на рис. 3.27а) остов по алгоритму Дейкстра, начиная с вершины x0.
Результаты построения остова графа приведены в таблице.
-
li
шаг итерации
L
1
2
3
4
5
6
7
8
9
вершины графа
x0
1
1
1
1
1
1
1
1
1
-
x1
1
1
1
1
1
1
1
1
1
-
x2
0
1
1
1
1
1
1
1
1
-
x3
0
0
0
1
1
1
1
1
1
-
x4
0
0
0
0
0
0
0
0
1
-
x5
0
0
0
0
0
0
1
1
1
-
x6
0
0
0
0
0
0
0
1
1
-
x7
0
0
0
0
0
1
1
1
1
-
x8
0
0
0
0
1
1
1
1
1
-
x9
0
0
1
1
1
1
1
1
1
-
ребра графа
l1
10
1
1
1
1
1
1
1
1
1
10
l2
24
0
1
1
1
1
1
1
1
1
24
l3
12
0
0
0
1
1
1
1
1
1
12
l4
15
0
0
0
0
0
0
0
0
0
-
l5
10
0
0
0
0
0
0
0
0
1
10
l6
5
0
0
0
0
0
0
0
1
1
5
l7
10
0
0
0
0
0
0
0
0
0
-
l8
5
0
0
0
0
0
1
1
1
1
5
l9
8
0
0
0
0
0
0
1
1
1
8
l10
15
0
0
0
0
1
1
1
1
1
15
l11
20
0
0
0
0
0
0
0
0
0
-
l12
12
0
0
1
1
1
1
1
1
1
12
l13
32
0
0
0
0
0
0
0
0
0
-
101
Вес минимального остова графа равен L=101.
Алгоритм Краскала:
шаг 1: установить частичный порядок ребер графа;
шаг2: выбрать ребро минимального веса, не являющееся петлей, сформировать фрагмент остова G’=<X’; r’`>, а концевые вершины ребра включить в подмножество Х’Х;
шаг3: выбрать ребро минимального веса, не являющееся петлей и не принадлежащее фрагменту:
а) если фрагменту принадлежит одна вершина ребра, то вторую концевую вершину включить в подмножество Х’, а ребро включить в фрагмент остова G’=<X’; r’`>,
b) если ни одна концевая вершина ребра не принадлежит фрагменту остова, то сформировать фрагмент другого остова,
с) если концевые вершины принадлежат различным остовам, то соединить фрагменты;
шаг 4: если все вершины графа вошли во фрагмент остова, то конец, иначе перейти к шагу 2.
На каждом шаге итерации выбирается минимальное ребро из всего множества.
Пример: Найти для графа на рис. 3.26а) остов по алгоритму Краскала.
В табл. а) установлен частичный порядок на множестве ребер исходного графа.
таблица а)
-
li
l6
l8
l9
l1
l5
l7
l3
l12
l4
l10
l11
l2
l13
L
5
5
8
10
10
10
12
12
15
15
20
24
32
таблица b)
-
li
шаг итерации
L
1
2
3
4
5
6
7
8
9
вершины графа
x0
0
0
0
1
1
1
1
1
1
-
x1
0
0
0
1
1
1
1
1
1
-
x2
0
0
0
0
0
1
1
1
1
-
x3
0
0
0
0
0
1
1
1
1
-
x4
0
0
0
0
1
1
1
1
1
-
x5
1
1
1
1
1
1
1
1
1
-
x6
1
1
1
1
1
1
1
1
1
-
x7
0
1
1
1
1
1
1
1
1
-
x8
0
1
1
1
1
1
1
1
1
-
x9
0
0
0
0
0
0
1
1
1
-
ребра графа
l1
10
0
0
0
1
1
1
1
1
1
10
l2
24
0
0
0
0
0
0
0
0
1
24
l3
12
0
0
0
0
0
1
1
1
1
12
l4
15
0
0
0
0
0
0
0
0
0
-
li
шаг итерации
L
1
2
3
4
5
6
7
8
9
l5
10
0
0
0
0
1
1
1
1
1
10
l6
5
1
1
1
1
1
1
1
1
1
5
l7
10
0
0
0
0
0
0
0
0
0
-
l8
5
0
1
1
1
1
1
1
1
1
5
l9
8
0
0
1
1
1
1
1
1
1
8
l10
15
0
0
0
0
0
0
0
1
1
15
l11
20
0
0
0
0
0
0
0
0
0
-
l12
12
0
0
0
0
0
0
1
1
1
12
l13
32
0
0
0
0
0
0
0
0
0
-
101
Следует обратить внимание, что при построении остова на седьмом шаге все вершины графа были включены в три несвязных фрагмента остова. На восьмом и девятом шаге было выполнено соединение фрагментов в единый остов графа.