Матрица следования для информационно-логического графа. Построение транзитивных связей в этой матрице

При решении задачи распараллеливания важную роль играют не только задающие связи, но и так называемые транзитивные.

Если вершины и связаны задающими связями, то существует транзитивная связь .

Множество связей, которые введены напра­вленно внутри всех пар элементов, принадлежащих одному пути в графе G и не связанных задающими связями, назовем множеством транзитивных связей для заданного пути.

Множество транзитивных связей графа G есть объединение множеств транзитивных связей но всем путям графа G.

Множество транзитивных связей, очевидно, полностью опреде­ляется множеством задающих связей. При формировании множе­ства транзитивных связей следует учитывать, что если и , где — множество всех операторов, связанных с оператором , то все операторы связаны транзитивно с опе­ратором .

Рассмотрим построение матрицы следования с транзитивными связями S_t- Возьмем три произвольные вершины i, j, k такие, что между ними определены следующие связи: связь вершины i с вер­шиной j, вершины j с вершиной k, вершины i с вершиной k, как показано на рис:

В матрице следовании, изображенной на рисунке, многоточием обозначены другие связи, которые для данного случая не предста­вляют интереса. При построении матрицы S элементы матрицы, соответствующие логическим связям, выписываются по формуле , а информационным — по формуле .

Алгоритм. Построение матрицы следования с транзитивны­ми связями.

1.Вычислим S_t:=S.

2. В матрице следования S _Т размера RS просмотрим строки, начиная с первой.

3.Если в очередной i-й строке матрицы S_t отыскивается эле­мент (i, j)≠ 0, то вычислим значения элементов (i, 1),..., (i, j- 1) матрицы S_t для k = 1,..., j- 1, используя соотношение

4.Вычислим j:= j + 1. Если j ≤ RS, то переходим к шагу 3, иначе — работа алгоритма заканчивается (просмотрены все стро­ки).