Алгоритм построения конденсации

1. Построим матрицу достижимости орграфа G.

R=||r_ij||, где i, j = 1..p.

1, если i достижима для j;

r_ij =

0, иначе

Построим матрицу контрдостижимости

Q=||q_ij||, где i, j= 1..p, Q = R^T.

1, если i контрдостижима для j;

q_ij =

0, иначе.

2. Найдем матрицу взаимной достижимости, где “ * ” – оператор поэлементного умножения матриц.

S=R * Q=R * R ^T,

s_ij=r_ij*q_ij, i, j = 1..p.

3. Выберем некоторую вершину v_i Î V, тогда сильная компонента орграфа, содержащая v_i, определяется единичными элементами i-той строки матрицы S, или перестановкой строк и столбцов можно привести матрицу S к блочно-диагональному виду, где каждый блок будет соответствовать некоторой сильной компоненте орграфа G.

Например:

Задан граф G. Построить конденсацию G ^*.

Решение:

Матрица достижимости R_G:

Матрица контрдостижимости Q_G:

Матрица взаимной достижимости S_G: