Нахождение минимально охватывающего дерева

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

Дадим краткое описание алгоритма решения поставленной задачи, известного под названием метода Прима (Prim) [8]. Алгоритм начинает работу с произвольной вершины графа, выбираемого в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет конструируемое дерево до МОД. Пусть есть множество вершин, уже включенных алгоритмом в МОД, а величины , , характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества , т.е.

(если для какой либо вершины не существует ни одной дуги в , значение устанавливается в ). В начале работы алгоритма выбирается корневая вершина МОД и полагается

, .

Действия, выполняемые на каждой итерации алгоритма Прима, состоят в следующем:

- определяются значения величин для всех вершин, еще не включенные в состав МОД;

- выбирается вершина графа , имеющая дугу минимального веса до множества

;

- включение выбранной вершины в .

После выполнения итераций метода МОД будет сформировано; вес этого дерева может быть получен при помощи выражения

.

Трудоемкость нахождения МОД характеризуется квадратичной зависимостью от числа вершин графа

.

Оценим возможности для параллельного выполнения рассмотренного алгоритма нахождения минимально охватывающего дерева. Итерации метода должны выполняться последовательно и, тем самым, не могут быть распараллелены. С другой стороны, выполняе­мые на каждой итерации алгоритма действия являются независимыми и могут реализовываться одновременно. Так, например, определение величин может осуществляться для каждой вершины графа в отдельности, нахождение дуги минимального веса может быть реализовано по каскадной схеме и т.д.

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

, , ,

соответствующий этому набору блок из величин , , и вертикальную полосу матрицы инцидентности графа из соседних столбцов, а также общую часть набора и формируемого в процессе вычислений множества вершин .

С учетом такого разделения данных итерация параллельного варианта алгоритма Прима состоит в следующем:

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

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

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

Получение МОД обеспечивается при выполнении итераций алгоритма Прима; как результат, общая трудоемкость метода определяется соотношением

.

С учетом данной оценки показатели эффективности параллельного алгоритма имеют вид:

, .

Анализ выражений показывает, что достижение асимптотически ненулевого значения показателя становится возможным при количестве процессоров, пропорциональном величине .