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

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

Алгоритм

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

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

Литература

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

Ссылки

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