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

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

АлгоритмПравить

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

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

ЛитератураПравить

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

СсылкиПравить

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