И построения структуры АСОИУ

Пусть G – построенный информационно-логический граф, а G^* - граф, называемый конденсацией графа G, который определяется следующим образом: каждая его вершина соответствует множеству вершин некоторой сильной компоненте графа G, то есть (разным сильным компонентам из графа G отвечают разные вершины в конденсации G^*); дуга существует в конденсации G^* тогда и только тогда, когда в графе G имеется такая дуга , что вершина принадлежит сильной компоненте , соответствующей вершине в конденсации G^*, а вершина принадлежит сильной компоненте , соответствующей вершине в конденсации G^*, то есть справедливы следующие соотношения: , а .

Сильными компонентами графа будем считать максимальные подграфы графа G, обладающие заданным свойством. Поскольку в данном случае в качестве такого свойства выступает сильная связность вершин графа G, его сильные компоненты будут представлять собой подмножества (порожденные подграфы) взаимно связных вершин.

Требуется найти его сильные компоненты и построить конденсацию графа G, то есть построить граф G^*.

Эта процедура реализуется при использовании матриц достижимости R_G и контрдостижимости Q_G графа G.

Матрица достижимости R_G=||r_js|| определяется следующим образом:

1, если вершина ℓ_s достижима из вершины ℓ_j (т.е. ℓ_j→ℓ_s)

r_js=

0, в противном случае.

Вершина ℓ_s считается достижимой из вершины ℓ_j, если существует путь от вершины ℓ_j к вершине ℓ_s.

Полагают, что все диагональные элементы матрицы R_G равны 1, т.к. каждая вершина достижима из самой себя путем длиной 0. В качестве алгоритма построения матрицы достижимости R_G можно предложить следующий:

Вход: Матрица A_G смежности графа G, состоящая из строк A₁, A₂,…, A_j,…, A_k; A_j=(a_j1,…, a_js,…, a_jk)

Выход: Матрица достижимости R_G, состоящая из строк R₁, R₂,..., R_j,…, R_k, где

R_j=(r_j1,…, r_js,…, r_jk)

Алгоритм запишем в виде, использующем так называемый псевдоалгол:

Начало

1. для j от 1 до k шаг 1 цикл А

2. сформировать множество S индексов s таких, что a_js=1;

3. R_j := A_j ; k:=0;

4. пока S≠0 цикл В

5. выбрать sєS;

6. R_j:=R_j A_s;

7. S:=S\{s};

8. K:=K {s};

9. Сформировать множество S_s индексов r таких, что a_sr=1;

10. S:=S (S_s\K);

11. конец цикла В;

12. возврат R_j;

13. конец цикла А;

Конец

Матрица контрдостижимости Q_G=║q_js║ определяется следующим образом:

1, если из вершины ℓ_s графа G достижима вершина ℓ_j (т.е. ℓ_j←ℓ_s)

q_js=

0, в противном случае.

При этом q_js=1, если j=s. Очевидно, что матрица Q_G есть транспонированная матрица R_G.

На следующем этапе алгоритма выполняется поэлементное умножение матриц R_G и Q_G графа G, в результате чего получаем матрицу (R_G Q_G).

При этом строка ℓ_j матрицы R_G Q_G содержит единицы только в тех столбцах ℓ_s , для которых выполняется условие: вершины ℓ_j и ℓ_s взаимно достижимы. В других местах строки стоят нули. Таким образом, две вершины графа G находятся в одной и той же сильной компоненте тогда, когда соответствующие им строки (или столбцы) в матрице R_G Q_G идентичны.

Следующий шаг алгоритма – преобразование матрицы (R_G Q_G )путем транспонирования ее строк и столбцов в блочно-диагональную матрицу , каждая из диагональных подматриц (блоков) которой соответствует сильной компоненте графа G и содержит только единичные элементы, поскольку вершины, которым отвечают строки, имеющие единицу в столбце ℓ_s, образуют множество вершин сильной компоненты, содержащей вершину ℓ_s. Все остальные блоки данной матрицы имеют нули.

Графическое представление полученной диагональной матрицы представляет собой граф искомой структуры, рассматриваемой АСОИУ.

Для инфологического графа G , представленного на рис. 1, его конденсация, то есть граф G^* , полученный путем применением рассмотренного алгоритма, представлен на рис. 2.

Рис. 1. Пример инфологического графа АСОИУ

Рис. 2. Граф G^* как структура АСОИУ