Меню Главная Случайная статья Настройки Алгоритм Мальгранжа Материал из https://ru.wikipedia.org Алгоритм Мальгранжа — метод для разбиения графа на сильно связные подграфы. Алгоритм Пусть дан граф ${\displaystyle G=(X,A)}$, где ${\displaystyle X=\{x{_{i}}\}}$ — множество вершин, в котором, ${\displaystyle i={\overline {1,n}}}$, а ${\displaystyle A=\{a{_{i}}\}}$ — множество дуг, описанных матрицей смежности, в котором ${\displaystyle i={\overline {1,m}}}$. Алгоритм разбиения заключается в следующем: Для произвольной вершины ${\displaystyle x{_{i}}\in X}$ находим прямое ${\displaystyle T{^{+}}(x{_{i}})}$ и обратное ${\displaystyle T{^{-}}(x{_{i}})}$ транзитивные замыкания. Находим ${\displaystyle T{^{+}}(x{_{i}})\cap T{^{-}}(x{_{i}})}$. Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа ${\displaystyle G{_{1}}=(X{_{1}},A{_{1}})}$. Из исходного графа вычитаем подграф ${\displaystyle G{_{1}}}$: ${\displaystyle G'=G\setminus G{_{1}},X'=X\setminus X{_{1}}}$. Граф ${\displaystyle G'}$ принимаем за исходный граф и пока ${\displaystyle X'\neq \varnothing }$ пункты 1, 2, 3 алгоритма повторяются. Литература А. Кофман. Введение в прикладную комбинаторику. — М.: Наука, 1975. — С. 166. — 480 с. Ссылки Тамара Волченская, Владимир Князьков, Курс «Введение в теорию графов», Лекция 7: «Методы разбиения графа на максимальные сильно связные подграфы» // Интуит.ру, 2008