Русская Википедия:Алгоритм Мальгранжа

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Алгоритм

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

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

Литература

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

Ссылки

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