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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Алгоритм[править | править код]

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

  1. Для произвольной вершины хi ∈ X находим прямое T+(хi) и обратное T-(хi) транзитивные замыкания.
  2. Находим T+(хi) ∩ T-(хi). Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа G1 = (Х1, A1).
  3. Из исходного графа вычитаем подграф G1:G '=G\G1, Х=X\Х1 .
  4. Граф G 'принимаем за исходный граф и пока X ' ≠ Ø пункты 1, 2, 3 алгоритма повторяются.

Литература[править | править код]

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

Ссылки[править | править код]