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

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

Алгоритм

Пусть дан граф $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^{\prime }=G\setminus G{}_1,X^{\prime }=X\setminus X{}_1$.
4. Граф $G^{\prime }$ принимаем за исходный граф и пока $X^{\prime }\ne \varnothing$ пункты 1, 2, 3 алгоритма повторяются.

Литература

• Шаблон:Книга

Ссылки

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