Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
При решении задачи распараллеливания важную роль играют не только задающие связи, но и так называемые транзитивные.
Если вершины и связаны задающими связями, то существует транзитивная связь .
Множество связей, которые введены направленно внутри всех пар элементов, принадлежащих одному пути в графе G и не связанных задающими связями, назовем множеством транзитивных связей для заданного пути.
Множество транзитивных связей графа G есть объединение множеств транзитивных связей но всем путям графа G.
Множество транзитивных связей, очевидно, полностью определяется множеством задающих связей. При формировании множества транзитивных связей следует учитывать, что если и , где — множество всех операторов, связанных с оператором , то все операторы связаны транзитивно с оператором .
Рассмотрим построение матрицы следования с транзитивными связями St- Возьмем три произвольные вершины i, j, k такие, что между ними определены следующие связи: связь вершины i с вершиной j, вершины j с вершиной k, вершины i с вершиной k, как показано на рис:
В матрице следовании, изображенной на рисунке, многоточием обозначены другие связи, которые для данного случая не представляют интереса. При построении матрицы S элементы матрицы, соответствующие логическим связям, выписываются по формуле , а информационным — по формуле .
Алгоритм. Построение матрицы следования с транзитивными связями.
1.Вычислим St:=S.
2. В матрице следования S Т размера RS просмотрим строки, начиная с первой.
3.Если в очередной i-й строке матрицы St отыскивается элемент (i, j)≠ 0, то вычислим значения элементов (i, 1),..., (i, j- 1) матрицы St для k = 1,..., j- 1, используя соотношение
4.Вычислим j:= j + 1. Если j ≤ RS, то переходим к шагу 3, иначе — работа алгоритма заканчивается (просмотрены все строки).
Дата публикования: 2015-02-18; Прочитано: 630 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!