Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 49 стр.

                         4.2. Матричный метод разбиения


       Метод разбиения графа на максимальные сильно связные подграфы по
матрицам достижимости R и контрдостижимости Q состоит в следующем [5].
       1. По матрице смежности строится матрица достижимости R. Используя
операцию транспонирования, находим матрицу контрдостижимости Q.
       2. Находится матрица C = { сij }, i,j=1,2,3,...,n, где n-число вершин исходного
графа , а каждый элемент Cij = rij ∧ gij , т.е. матрица C получается поэлементным
логическим умножением матриц R и Q :           С = R ∧ Q.
       3. Элементы, имеющие одинаковые строки и столбцы в матрице С
группируем перестановкой строк и столбцов, получаем блочно диагональную
матрицу Св, где каждая группа элементов и есть максимальный сильно связный
подграф.
       Рассмотрим пример разбиения для графа представленного на рис.21,а. Как
следует из определения матрицы R (п.2.3) для ее нахождения следует для каждой
вершины найти прямое транзитивное замыкание. Если некоторая xj вершина
графа входит в транзитивное замыкание
       T+( хi ), то элемент матрицы R rij=1. Полученные, таким образом, матрицы R
и Q показаны на рис.24,а и б. В результате логического умножения получили
матрицу С (рис.24,в), в которой находим одинаковые строки. Например, для
вершины х1 строка совпадает с седьмой и одиннадцатой. Следовательно,
вершины х1, х7, х11 группируем вместе и они составляют первый выделенный
подграф. Как видим из блочно-диагональной матрицы (рис.24,г) полученные
подграфы     совпадают    с   результатом    разбиения      по   методу    Мальгранжа
(п.4.1.,рис.23,а).
       Блок-схема    алгоритма    матричного    метода      разбиения     приведена   в
приложении 5.