Параллельное программирование



              

Граф-схемы параллельных алгоритмов - часть 4


В представленном выше примере после введения всех транзитивных связей матрица следования S примет вид, представленный на рисунке 7.6)рисунке 7.6 (введённые транзитивные связи выделены курсивом).

Матрица следования с транзитивными связями

Рис. 7.6.  Матрица следования с транзитивными связями

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

a.

Например, пусть задан граф G на рис. 7.7.

Граф алгоритма и матрица следования

Рис. 7.7.  Граф алгоритма и матрица следования

После первого шага преобразования S принимает вид, показанный на рис. 7.8.

Первый шаг обнаружения контура

Рис. 7.8.  Первый шаг обнаружения контура

После второго шага преобразования S принимает вид, показанный на рис. 7.9.

Обнаружение контура

Рис. 7.9.  Обнаружение контура

Т.к. на главной диагонали матрицы появились единицы, то граф G содержит циклы (контуры). Из рисунка графа виден цикл 2

6
3
5
. "Участники" цикла отмечены единицами на главной диагонали.

Определение 6. Работы a и b будем называть взаимно независимыми, если в матрице следования S выполняется условие (a, b) = (b, a) = 0.

Определение 7. Работы {ai}, i = 1, ... , s, образуют полное множество взаимно независимых работ (ПМВНР), если для любой работы j

{ai} существует задающая или транзитивная связь (a? , j) = 1 или {(j , a?) =1} (?,?
{1 , ... , s}).

Например, для графа G, представленного на рис. 7.1, после введения транзитивных связей, что учтено в матрице следования на рис. 7.6, можно установить следующие ПМВНР: {1,2}, {2,3,4}, {3,4,5}, {2,3,6}, {3,5,6,7}, {8}.




Содержание  Назад  Вперед