АЛГОРИТМЫ ВЫДЕЛЕНИЯ КОМПЛЕКСОВ

Алгоритмы выделения комплексов используют основное свойство вершин графа, принадлежащих комплексу. Для любых двух вершин I и J, входящих в ком­плекс, должен существовать путь из I-й в J-ю вершину и обратный путь из J-и в I-ю вершину (двигаясь в направлении ориентированных дуг). Для выделения комплексов существуют различные матричные алгоритмы. Некоторые из них связаны с представлением структуры ХТС в виде матрицы связей и последующими операциями с этой матрицей с целью выделения на графе ХТС путей различной длины и построения матрицы комплексов.

В основе других алгоритмов лежит использование матрицы путей на графе. Матрица путей является квадратной и содержит столько столбцов, сколько эле­ментов имеется в составе ХТС. Если на графе есть путь любой длины из верши­ны I в вершину J, то на пересечении I-й строки и J-го столбца матрицы путей ставится 1, иначе ставится  - 0. На главной диагонали этой матрицы ставятся единицы, так как считается, что путь длиной 0 из любого элемента в этот же самый элемент всегда существует.

Рисунок  2.1 -Граф ХТС

Матрица путей графа ХТС, представленной на рисунке 2.1 (обозначим эту матрицу буквой Р), имеет вид:

Наряду с матрицей Р. строится вспомогательная матрица S. Она является транспонированной по отношению к матрице Р, т. е. столбцы матрицы S являют­ся строками матрицы Р:

Элементы матрицы Р указывают на наличие пути из I вершины в J-ю вершину, а элементы матрицы S - из J-й вершины в I-ю. Логически пере­множая элементы матриц Р и S (полагая 0 * 0 = 0, 0 * 1 = 0, 1 * 0 = 0, 1 * 1 = 1), получим матрицу комплексов D:

С помощью матрицы D определяются комплексы, входящие в состав графа ХТС, по следующим правилам:

- если в I-ой строке этой матрицы имеется только один не нулевой элемент d(I,I)=1 (принадлежащий главной диагонали), то элемент ХТС с номером I может быть рассчитан отдельно от остальных элементов систе­мы. В рассматриваемом примере это элементы 1 и 5;

- строки матрицы D, имеющие, кроме элемента d (1,1), другие не нулевые элемен­ты, соответствуют комплексам. Не нулевые элементы строк указывают вершины графа, входящие в состав комплекса.

В нашем примере, согласно матрице D, в состав ХТС входят два комплекса:

комплекс 1 - (2, 3, 4)

комплекс 2 - (6, 7).

Одинаковые строки матрицы соответствуют одному и тому же комплексу.

Для решения задач структурного анализа ХТС используют различные алгоритмы.

Остановимся на одном из них.

Рассмотрим три любые вершины графа ХТС: I, J, M. Если существует путь лю­бой длины из вершины I в вершину J и из вершины J в I, то эти вершины при­надлежат одному и тому же комплексу К. Для присоединения вершины M к ком­плексу K необходимо проанализировать, есть ли путь из любой вершины (например, I принадлежащей комплексу К, в вершину M и обратный путь из вершины M в любую вершину комплекса К (например, I). Если эти два пути существуют, то вер­шина M принадлежит комплексу К

Применение этого правила к ХТС, изображенной на рисунке 2.2, позволяет выделить следующие комплексы: - комплекс К1- (1,2, 3, 8, 9, 10), комплекс К2 - (5,11) , элементы 4,6, 7 рассчитываются автономно.

Рисунок 2.2 - Граф некоторой замкнутой ХТС