Алгоритм Мальгранжа — метод для разбиения графа на сильно связные подграфы .

Алгоритм

Пусть дан граф ${\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 с.

Ссылки

• Тамара Волченская, Владимир Князьков, // Интуит.ру , 2008