Алгоритм Мальгранжа

Пусть дан граф ${\displaystyle G=(X,A)}$, где ${\displaystyle X=\{x{_{i}}\}}$ — множество вершин, в котором, ${\displaystyle i={\overline {1,n}}}$, а ${\displaystyle A=\{a{_{i}}\}}$ — множество дуг, описанных матрицей смежности, в котором ${\displaystyle i={\overline {1,m}}}$. Алгоритм разбиения заключается в следующем:

1. Для произвольной вершины ${\displaystyle x{_{i}}\in X}$ находим прямое ${\displaystyle T{^{+}}(x{_{i}})}$ и обратное ${\displaystyle T{^{-}}(x{_{i}})}$ транзитивные замыкания.
2. Находим ${\displaystyle T{^{+}}(x{_{i}})\cap T{^{-}}(x{_{i}})}$. Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа ${\displaystyle G{_{1}}=(X{_{1}},A{_{1}})}$.
3. Из исходного графа вычитаем подграф ${\displaystyle G{_{1}}}$: ${\displaystyle G'=G\setminus G{_{1}},X'=X\setminus X{_{1}}}$.
4. Граф ${\displaystyle G'}$ принимаем за исходный граф и пока ${\displaystyle X'\neq \varnothing }$ пункты 1, 2, 3 алгоритма повторяются.

• А. Кофман. Введение в прикладную комбинаторику. — М.: Наука, 1975. — С. 166. — 480 с.

• Тамара Волченская, Владимир Князьков, Курс «Введение в теорию графов», Лекция 7: «Методы разбиения графа на максимальные сильно связные подграфы» // Интуит.ру, 2008