- Алгоритм Мальгранжа
-
Алгоритм Мальгранжа — разбиение графов на сильно связные под-графы.
Алгоритм
Пусть дан граф 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 алгоритма повторяются.
Ссылки
Методы разбиения графа на максимальные сильно связные подграфы
Для улучшения этой статьи по математике желательно?: - Воспользоваться подсказкой и установить ссылки из других статей Википедии.
- Проставить интервики в рамках проекта Интервики.
- Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).
- Переработать оформление в соответствии с правилами написания статей.
- Викифицировать статью.
Категория:- Алгоритмы на графах
Wikimedia Foundation. 2010.