Теория и практика параллельных вычислений
Параллельные методы на графах
Математические модели в виде графов широко используются при моделировании разнообразных явлений, процессов и систем. Как результат, многие теоретические и реальные прикладные задачи могут быть решены при помощи тех или иных процедур анализа графовых моделей. Среди множества этих процедур может быть выделен некоторый определенный набор типовых алгоритмов обработки графов. Рассмотрению вопросов теории графов, алгоритмов моделирования, анализу и решению задач на графах посвящено достаточно много различных изданий, в качестве возможного руководства по данной тематике может быть рекомендована работа [[26]].
Пусть G есть граф
G=(V,R),
для которого набор вершин Vi, 0in, задается множеством V, а список дуг графа
определяется множеством R. В общем случае дугам графа могут приписываться некоторые числовые характеристики (веса) wj, 0jm (взвешенный граф). Пример взвешенного графа приведен на рис. 10.1.
Рис. 10.1. Пример взвешенного ориентированного графа
Известны различные способы задания графов. При малом количестве дуг в графе (т. е. m<<n2) целесообразно использовать для определения графов списки, перечисляющие имеющиеся в графах дуги. Представление достаточно плотных графов, для которых почти все вершины соединены между собой дугами (т. е. m~n2), может быть эффективно обеспечено при помощи матрицы смежности:
A=(aij), 1i, jn,
ненулевые значения элементов которой соответствуют дугам графа:
(для обозначения отсутствия ребра между вершинами в матрице смежности на соответствующей позиции используется знак бесконечности, при вычислениях знак бесконечности может быть заменен, например, на любое отрицательное число). Так, например, матрица смежности, соответствующая графу на рис. 10.1, приведена на рис. 10.2.
Рис. 10.2. Матрица смежности для графа с рис. 10.1
Как положительный момент такого способа представления графов можно отметить, что использование матрицы смежности позволяет применять при реализации вычислительных процедур анализа графов матричные алгоритмы обработки данных.
Далее мы рассмотрим способы параллельной реализации алгоритмов на графах на примере задачи поиска кратчайших путей между всеми парами пунктов назначения и задачи выделения минимального охватывающего дерева (остова) графа. Кроме того, мы рассмотрим задачу оптимального разделения графов, широко используемую для организации параллельных вычислений. Для представления графов при рассмотрении всех перечисленных задач будут применяться матрицы смежности.
