13.Алгоритм формальной декомпозиции систем по методу разбиения графа на максимально сильно связные подграфы.

Матричный алгоритм формальной декомпозиции состоит в выполнении следующих действий:

1. строится квадратная матрица связности М_L=[m_ij], , где m – число узлов, элементы которой получаются поэлементным логическим умножением матриц достижимости и контрдостижимости:

;

2. элементы, имеющие одинаковые строки и столбцы в матрице связности группируются перестановкой строк и столбцов для получения блочно-диагональной матрицы, в которой элементы, равные 1, сгруппированы как можно более плотно вдоль главной диагонали матрицы. Каждая диагональная группа элементов в виде квадратного блока в перестановочной матрице связности и есть максимальный сильно связный подграф.

Для построения матрицы достижимости при ограничении достижимости длинной пути, равной 1 или 2 дуги (k2) следует поэлементно сложить M_С и . В результате получится матрица, ненулевые элементы которой показывают наличие путей из узла x_i в узел x_j длиной в k2 дуг. Замена ненулевых элементов этой матрицы на 1 дает матрицу достижимости.

Матрицей контрдостижимости называется транспонированная матрица достижимости.

1