ВУЗ:
Составители:
81
6.3 Построение и преобразование матрицы следования
Для удобства исследования и преобразования графов в рассмотрение вво-
дят матрицу следования S. Вершине (оператору) i графа ставят в соответствие
i-ю строку и i-й столбец матрицы. Элемент (i,j) этой матрицы будем отмечать
знаком , если между операторами с этими номерами существует связь вида
ji (по управлению или информации). Для различения типа операторов там,
где это необходимо, связи по управлению будем отмечать знаком C, а связи по
информации – I.
Можно показать [1], что по графу без кон-
туров может быть построена треугольная мат-
рица следования с нулевыми элементами на
главной диагонали, что упрощает некоторые
задачи их анализа. На рис. 6.3 приведена мат-
рица следования, соответствующая граф-схеме,
показанной на рис. 6.2.
Для дальнейшего исследования матрицы S
необходимо отразить в ней (неявные) связи
между операторами, которые реально сущест-
вуют и определяются задающими связями, но непосредственно между ними в
графе отсутствуют. Их введение необходимо для выявления ветвей связанных
операторов, которые не могут выполняться параллельно. Кроме того, введение
этих связей позволяет выявить контуры в графе. Рассмотрим способы установ-
ления этих связей.
Если существуют задающие связи
и
, но нет задающей связи
, то дополнение вычислительной схемы такими связями не меняет резуль-
тата решения задачи, а лишь подтверждает недопустимость определенного по-
рядка следования операций. Связи, которые введены направленно внутри всех
пар операторов, принадлежащих одному пути в графе G и не связанные задаю-
щими связями, образуют множество транзитивных связей [1]. Транзитивные
Рис. 6.3 Матрица следования
S
Страницы
- « первая
- ‹ предыдущая
- …
- 79
- 80
- 81
- 82
- 83
- …
- следующая ›
- последняя »
