Материал: Lab 5 Z недод

Пример 5.1

На плоскости в декартовой системе координат задано местоположение шести точек (рис. 5.2.). Расстояние между любыми двумя точками и определено по формуле (5.1). Требуется для заданного множества точек M определить минимальное связывающее дерево при условии, что локальные степени вершин не должны превышать двух – .

Решение

Составляем матрицу длин и всем элементам, лежащим на главной диагонали и ниже нее, присваиваем значение :

Формируем таблицу меток и локальных степеней (см. табл. 5.1).

На нулевом шаге все вершины получают метки, равные их номерам , а локальные степени , , длина строящегося дерева и множество ребер в дереве R = 

На первом шаге просматриваем элементы верхней половины матрицы D и выбираем из них минимальный элемент (при наличии нескольких элементов с одинаковыми минимальными значениями выбираем элемент с наименьшими индексами i и j).

Таблица 5.1.

Помечаем элемент и на его место записываем . Метки у 1-й и 2-й вершин разные ( , ), поэтому соединяем вершины 1-ю и 2-ю ребром: метки у них становятся равными: . Локальные степени обеих вершин равны единицам – и .

Рис. 5.2.

Рис.5.3.

Длина L строящегося дерева равна 1.4, а множество ребер R = 1 (см. 1-й шаг табл. 1). На втором шаге выбирается минимальный элемент , на третьем – , на четвертом – (см. рис. 5.2). На места выбранных элементов в матрице D записываем . Получили матрицу D₁:

3. Алгоритм Прима

Алгоритм Прима реализует следующую процедуру [1 – 7].

На каждом шаге просматриваются только те ребра графа, которые связы-вают вершины строящегося поддерева с новыми, еще не присоединенными вершинами, т.е. ищется вершина, ближайшая от всего построенного фрагмента дерева. Отсюда, в отличие от алгоритма Краскала, единственное строящееся поддерево последовательно наращивается до построения остова.

Основные принципы построения минимального связывающего дерева (или кратчайшей связывающей сети) при наличии ограничений на локальные степени вершин следующие.

В начале любая произвольная вершина соединяется с ближайшей соседней, образуя исходное поддерево. (Для определенности построения мини-мального дерева можно начинать с ребра, инцидентного первой вершине , или с минимального ребра). На каждом последующем шаге к строящемуся поддереву присоединяют очередное ребро минимально возможной длины, связывающее новую, еще не присоединенную вершину с одной из вершин поддеревьев , локальная степень которой .

Для реализации алгоритма составляют матрицу расстояний , элемент которой вычисляют по одной из формул (5.1) или (5.2). Просматривают элементы первой строки матрицы D и находят минимальный элемент. Пусть таким оказался элемент g-го столбца, тогда весь 1-й и g-й столбцы матрицы D исключаются из рассмотрения, а первое соединение проводится между точками и . Просматриваются 1-я и g-я строки матрицы с оставшимися элементами. Из элементов этих строк находится минимальный. Предположим, что им оказался элемент, принадлежащий j-му столбцу. Если этот элемент находится на пересечении с первой строкой, то точку соединяем с 1-й точкой ( ), если же он находится на пересечении с g-й строкой, то точку соединяем с g-й ( ), после чего из матрицы D исключаем все элементы j-го столбца. Просматриваются 1-я, g-я и j-я строки и т. д.

Выполнение ограничения на локальную степень вершин обеспе-чивается проверкой в каждой просматриваемой i-ой строке числа уже выбранных для построения минимального дерева элементов – . При все оставшиеся элементы i-й строки исключаются из рассмотрения, т.е. эта строка удаляется.

АЛГОРИТМ

1. Вычислить элементы матрицы расстояний по одной из формул – (5.1) или (5.2).

2. Найти минимальный элемент матрицы , где ; . Номера строки и столбца q и p, на пересечении которых он находится, определяют номера вершин и , соединяемых ребром.

В выделяемом минимальном дереве построены два фрагмента с суммарной длиной . У вершин 1-го фрагмента (1-й и 2-й) метки и локальные степени . У вершин 2-го фрагмента (3-й, 4-й, 5-й, 6-й) метки , а локальные степени - , .

Выбранный из оставшихся минимальный элемент , на очередном 5-м шаге, не может быть включен во множество R ребер дерева, поскольку образует цикл с ребрами ранее построенного фрагмента (на это указывают одинаковые метки у 3-й и 6-й вершин ).

На шестом и восьмом шагах выбранные ребра и соот-ветственно не образуют циклов, но их присоединение нарушает ограничение на локальную степень 3-й вершины. На седьмом – ребро не может быть подсоединено вновь из-за образования цикла (рис. 5.3).

На девятом шаге присоединяется ребро , при этом выполняется условие , т. е. дерево построено: , длина дерева (рис. 5.4). Если бы ограничение на степени вершин отсутство-вало, то можно было бы построить дерево с меньшей длиной (рис. 5.4).

Рис. 5.4.