WikiSort.ru - Не сортированное

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

Алгоритм

Пусть дан граф 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 с.

Ссылки

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

Для улучшения этой статьи по математике желательно: Установить ссылки из других статей Википедии. Связать? Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Переработать оформление в соответствии с правилами написания статей. Викифицировать статью.