Метод Мальгранжа

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

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

Рассмотрим этот алгоритм более подробно на примере разбиения графа, представленного на рис. 7.1,a, матрица смежности которого показана на рис. 7.1,б.

Рис. 7.1.

РАЗБИЕНИЕ – 1.

Таблица 7.1.
		X1	X7	X11
	X1
A7=	X7
	X11

1. Начальной вершиной первого разбиения выберем х₁. Построим прямое и обратное транзитивные замыкания. T⁺(х₁)– столбец, показанный справа от матрицы А, а T^-(х₁) – строка, находящаяся ниже матрицы смежности.

T⁺(х₁) = {х₁, х₄, х₅, х₆, х₇, х₈, х₁₁ },

T^-(х₁) = {х₁, х₂, х₃, х₇, х₉, х₁₀, х₁₁}.

1. Находим T⁺(х₁) T^-(х₁) = {х₁, х₇, х₁₁}. Эти вершины и составляют первый выделенный, максимальный сильно связный подграф G₁ = (Х₁, A₁), где Х₁ = {х₁, х₇, х₁₁}, а матрица смежности A₁ подграфа G₁ показана на таблица 7.1.
2. Из исходного графа G вычитаем подграф G₁ G ' = G \G₁;

G ' = (X ', A'), X ' = { х₂, х₃, х₄, х₅, х₆, х₈, х₉, х₁₀ }.

1. Так как X ' не пустое множество, то G' принимаем за G и переходим ко второму разбиению.

РАЗБИЕНИЕ – 2

Таблица 7.2.
		X2	X3	X4	X5	X6	X8	X9	X10		T+(x2)
	X2
	X3
	X4
	X5
A=	X6
	X8
	X9
	X10
	T-(x2)

1. Выбираем любую вершину, принадлежащую X, например, х₂, и находим T⁺(х₂) и T^-(х₂). Это показано в таблице 7.2. T⁺(х₂) = { х₂, х₈ }; T^-(х₂) = { х₂ }.
2. T⁺(х₂) T^-(х₂) = { х₂ }. Следовательно, второй выделенный подграф G₂ состоит из одной вершины х₂.
3. G ' = G \G₂; G ' = (X ', A'); X ' = { х₃, х₄, х₅, х₆, х₈, х₉, х₁₀ }.
4. Так как X ' не пустое множество, то G ' принимаем за G и процесс разбиения продолжается.

7. Лекция: Методы разбиения графа на максимальные сильно связные подграфы