Материал: Lab 5 Z недод
3.
Занести номера вершин во множество
,
построенное ребро – во множество
.
4.
Подсчитать локальные степени
и
,
подлежащих соединению на данном шаге
вершин
и
.
5.
Проверить условие
и
.
Индексы вершин, для которых это условие
не выполняется, указывают номера строк
матрицы D,
которые необходимо исключить из
рассмотрения.
6.
Найти
.
Здесь
,
,
т. е. среди еще не вошедших в дерево
вершин отыскать вершину
,
минимально удаленную от некоторой
вершины дерева
.
7.
Дополнить множества
;
.
8.
Проверить, все ли вершины графа соединены
ветвями
.
Если условие выполняется, идти к 9, иначе
– к 4.
Конец.
Пример 5.2
На плоскости в декартовой системе координат задано местоположение шес-ти точек (рис. 5.5). Расстояние между любыми двумя точками и определено по формуле (5.2). Требуется для заданного множества точек M определить минимальное связывающее дерево при условии, что локальные степени вершин не должны превышать двух: .
Решение
Составляем матрицу расстояний
D= |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
0 |
2 |
4 |
6 |
8 |
7 |
1+1 |
||
2 |
2 |
0 |
4 |
6 |
6 |
7 |
1 |
||
3 |
4 |
4 |
0 |
2 |
4 |
3 |
1 |
||
4 |
6 |
6 |
2 |
0 |
6 |
5 |
|
||
5 |
8 |
6 |
4 |
6 |
0 |
3 |
|
||
6 |
7 |
7 |
3 |
5 |
3 |
0 |
|
||
Просматриваем
все строки матрицы и выбираем элемент,
являющийся минимальным. Поскольку таких
элементов два
,
выбираем элемент с наименьшими индексами
–
.
Помечаем его, локальные степени 1-й и
2-й вершин увеличиваем на единицу –
.
Исключаем из рассмотрения (вычеркиваем)
все элементы первого и второго столбцов.
Соединяем
и
(рис. 5.6, а).
Просматриваем
первую и вторую строки матрицы. Выбираем
элемент
;
локальные степени 1-й и 3-й вершин
увеличиваем на единицу –
;
.
Исключаем из рассмотрения элементы
3-го столбца и 1-й строки (к 1-й вершине
подключено уже два ребра). Соединяем
с
(рис. 5.6, б). Получили матрицу D1:
D1= |
|
4 |
5 |
6 |
|
2 |
6 |
6 |
7 |
1 |
|
3 |
2 |
4 |
3 |
1+1 |
|
4 |
0 |
6 |
5 |
1+1 |
|
5 |
6 |
0 |
3 |
1 |
|
6 |
5 |
3 |
0 |
1 |
Просматриваем
вторую и третью строки. Выбираем элемент
;
;
.
Соединяем вершины
и
(рис. 5.6, в). Исключаем из рассмотрения
четвертый столбец и третью строку,
поскольку
.
Просматриваем
вторую и четвертую строки. Выбираем
элемент
;
;
.
Соединяем
с
(рис. 5.6, г). Поскольку
,
исключаем из рассмотрения шестой столбец
и четвертую строку. И, наконец,
просма-триваем вторую и шестую строки.
Выбираем
;
,
.
Соединяем
с
(рис. 5.6, д). Исключаем из рассмотрения
последний пятый столбец.
Минимальное связывающее дерево, полученное в результате решения, приведено на рис.5.6, д.
Рис. 5.5
Множество
ребер в нем
.
Суммарная длина его ребер L
равна 16.
Если
локальную степень вершин не ограничивать,
то в результате решения будут выбраны
элементы
,
,
,
,
и суммарная длина ребер при этом равна
14 (см. рис. 5.6, е).
Выводы: Оба рассмотренных алгоритма позволяют при выполнении соот-ветствующих условий находить глобально-оптимальные или близкие к ним решения.
При этом для работы алгоритма Краскала требуется n (n-1)/2 памяти ЭВМ для записи исходных данных, однако в процессе работы необходимо дополни-тельное время для проверки ребер на образование циклов.
Для работы алгоритма Прима памяти необходимо n2, но зато отсутствует необходимость проверки ребер на образование циклов.
Следовательно, алгоритм Краскала требует в два с лишним раза меньше памяти, чем алгоритм Прима; зато машинного времени меньше необходимо при расчёте по алгоритму Прима. Кроме этого надо отметить, что алгоритм Краскала более прост при реализации.