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

             Разбиение графа на подграфы по методу Мальгранжа.
Изучение метода показывает, что в его основе лежит задача нахождения прямого
и обратного транзитивного замыканий для некоторой вершины. Блок-схема
нахождения прямого транзитивного замыкания (“TRAN”) показана в приложении 2.
Эту     подпрограмму    можно     использовать       и   для   нахождения     обратного
транзитивного     замыкания,      введя    небольшие      добавления,    а   именно   :
признак р:
 P=1,     если,      необходимо      найти     прямое      транзитиное       замыкание,
 P=0,        если,       ищется           обратное       транзитиное         замыкание.
В зависимости от значения признака р будем просматривать в матрице A строку
или столбец.
В блок- схеме алгоритма разбиения графа на подграфы обратите внимание, что
прежде, чем вызывается подпрограмма “TRAN”, задается значение признака р, а
после того как прямое транзитивное замыкание найдено, содержимое массива T
переписывается в массив P. Все используемые обозначения в блок-схеме
совпадают с введенными ранее. После того, как определено, что i-ый элемент
входит в подграф, номер элемента выводится на печать , обнуляется номер в
списке элементов Y (блок 19) и обнуляются i-ая строка и i-ый столбец в матрице A
. Номер выделяемого подграфа N1 увеличивается на 1 (блок 23) и процесс
разбиения продолжается.