Теория и практика параллельных вычислений
Задача нахождения минимального охватывающего дерева
Охватывающим деревом (или остовом) неориентированного графа G называется подграф T графа G, который является деревом и содержит все вершины из G. Определив вес подграфа для взвешенного графа как сумму весов входящих в подграф дуг, под минимально охватывающим деревом (МОД) T будем понимать охватывающее дерево минимального веса. Содержательная интерпретация задачи нахождения МОД может состоять, например, в практическом примере построения локальной сети персональных компьютеров с прокладыванием соединительных линий связи минимальной длины. Пример взвешенного неориентированного графа и соответствующего ему минимально охватывающего дерева приведен на рис. 10.6.
Рис. 10.6. Пример взвешенного неориентированного графа (а) и соответствующему ему минимально охватывающего дерева (б)
Дадим общее описание алгоритма решения поставленной задачи, известного под названием метода Прима (the Prim method); более полная информация может быть получена, например, в [[26]].
