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

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

Алгоритм

править

Пусть дан граф  , где   — множество вершин, в котором,  , а   — множество дуг, описанных матрицей смежности, в котором  . Алгоритм разбиения заключается в следующем:

  1. Для произвольной вершины   находим прямое   и обратное   транзитивные замыкания.
  2. Находим  . Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа  .
  3. Из исходного графа вычитаем подграф  :  .
  4. Граф   принимаем за исходный граф и пока   пункты 1, 2, 3 алгоритма повторяются.

Литература

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

Ссылки

править