Алгоритм Мальгранжа — метод для разбиения графа на сильно связные подграфы.
Алгоритм Пусть дан граф , где — множество вершин, в котором, , а — множество дуг, описанных матрицей смежности, в котором . Алгоритм разбиения заключается в следующем:
Для произвольной вершины находим прямое и обратное транзитивные замыкания. Находим . Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа . Из исходного графа вычитаем подграф : . Граф принимаем за исходный граф и пока пункты 1, 2, 3 алгоритма повторяются.
Литература
Ссылки Тамара Волченская, Владимир Князьков, Курс «Введение в теорию графов», Лекция 7: «Методы разбиения графа на максимальные сильно связные подграфы» // Интуит.ру, 2008
Категория:Алгоритмы на графах