Пример разрезания графа на куски

Итерационным методом с использованием чисел связности

 

 

Рассмотрим пример разрезания графа с использованием чисел связности. Для примера с целью сравнения результатов выбран граф G (рис. 4), который использовался для иллюстрации последовательного метода разрезания графов в практической работе № 3.

 

Рис. 4

 

Задание

 

1) Разрезать граф G = (X, U), содержащий 12 вершин (рис. 4) на три куска по четыре вершины в каждом, используя числа связности.

2) Определить коэффициент разрезания.

 

Решение

 

1) Составить матрицу смежности R₀ графа G.

 

r1

r2

r3

r4

r5

c1

c2

vd1

vd2

vd3

vt1

vs1

ak, aq

r1

+1

r2

+1

r3

+2

r4

+2

r5

–3

R0 =

c1

–3

(5)

c2

–2

vd1

–1

vd2

–2

vd3

vt1

–2

vs1

–1

2) Разрезать граф G на два куска G₁ и`G₁, выделив в матрице смежности R₀ подматрицу R⁽¹⁾₀ порядка n₁, где n₁ – количество элементов, входящих в первый кусок G₁. Результат разрезания представлен на рис. 5. Количество внешних связей между кусками K = 6.

 

Рис. 5

 

3) Подсчитать числа связности по формуле (3). Числа связности a_k и a_q указаны в дополнительном столбце матрицы смежности R₀.

4) Построить вспомогательную матрицу W₀, строки которой определяются вершинами r₁, r₂, r₃ и r₄, входящими в первый кусок G₁, а столбцы – всеми остальными вершинами графа G (вершинами куска`G₁).

		r5	c1	c2	vd1	vd2	vd3	vt1	vs1
	r1	–2	–2	–1	–2	–1	+1	–1
W(1) =	r2	–2	–2	–1		–1	+1	–1		(6)
	r3	–1	–1		+1		+2	–2	–3
	r4	–1	–1	–2	+1				+1

 

Элементы вспомогательной матрицы определяются по формуле (4).

В качестве примера рассмотрим вычисление некоторых элементов w_kq вспомогательной матрицы (6)

w(r₁c₂) = a(r₁) + a(c₂) – 2r(r₁c₂) = 1 + (–2) – 2 ´ 0 = 1 – 2 = –1

w(r₂vd₁) = a(r₂) + a(vd₁) – 2r(r₂vd₁) = 1 + (–1) – 2 ´ 0 = 1 – 1 = 0

w(r₁vd₁) = a(r₁) + a(vd₁) – 2r(r₁vd₁) = 1 + (–1) – 2 ´ 1 = 1– 1 – 2 = –2

w(r₄vs₁) = a(r₄) + a(vs₁) – 2(r₄vs₁) = 2 + (–1) – 2 ´ 0 = 2 – 1 = +1

5) Выбрать в матрице (6) наибольший положительный элемент w_kq. Таким элементом является элемент w(r₃vd₃) = +2. Следовательно, для минимизации внешних связей необходимо переставить r₃ и vd₃ строки и столбцы в матрице смежности R₀. В результате такой перестановки количество внешних связей между кусками G₁ и G₁ должно уменьшиться на два и составит K = 4. Выполненная перестановка r₃ и vd₃ строк и столбцов означает, что вершина r₃ из куска G₁ переместилась в кусок `G<sub>1,</sub> а вершина vd<sub>3</sub> – из куска `G₁ в кусок G₁. Результат перестановки представлен на рис. 6.

 

Рис. 6

 

6) Построить матрицу смежности R₀₁, изоморфную матрице R₀

 

r1

r2

vd3

r4

r5

c1

c2

vd1

vd2

r3

vt1

vs1

ak, aq

r1

+1

r2

+1

vd3

r4

+0

r5

–3

R01 =

c1

–3

(7)

c2

–2

vd1

–1

vd2

–2

r3

–2

vt1

–2

vs1

–3

 

7) Подсчитать числа связности по формуле (3). Числа связности a_k и a_q указаны в дополнительном столбце матрицы смежности R₀₁.

8) Построить вспомогательную матрицу W₀₁, строки которой определяются вершинами, входящими в первый кусок G₁ (r₁, r₂, vd₃, r₄), а столбцы – вершинами куска `G₁.

 

		r5	c1	c2	vd1	vd2	r3	vt1	vs1
	r1	–2	–2	–1	–2	–1	–1	–2	–2
W01 =	r2	–2	–2	–1		–1	–1	–2	–4	(8)
	vd3	–3	–3	–2	–1	–2	–2	–5	–3
	r4	–3	–3	–4	–1	–2	–2	–3	–3

 

9) Во вспомогательной матрице W₀₁ отсутствуют какие-либо положительные элементы. Это означает, что на данном этапе разрезания графа G отсутствует пара вершин, перестановка которых уменьшит количество внешних связей K между кусками G₁ и `G₁. Следовательно, кусок G₁ = (X₁, U₁) считается сформированным, где X₁ = {r₁, r₂, vd₃, r₄}.

10) Удалить из графа G кусок G₁. В результате будет получен граф G^*, представленный на рис. 7.

Рис. 7

11) Составить матрицу смежности R₁ графа G^*.

 

		r5	c1	c2	vd1	vd2	r3	vt1	vs1	ak, aq
	r5									+1
	c1									+1
	c2									–1
R1 =	vd1									+2	(9)
	vd2									+2
	r3									–2
	vt1									+1
	vs1									+2

 

12) Разрезать граф G^* на два куска G₂ и`G₂, выделив в матрице смежности R₁ подматрицу R⁽¹⁾₁ порядка n₂, где n₂ — количество элементов, входящих во второй формируемый кусок G₂. Результат разрезания графа представлен на рис. 8. Количество внешних связей между кусками K = 7.

 

 

Рис. 8

 

13) По формуле (3) подсчитать числа связности. Числа связности a_k и a_q указаны в дополнительном столбце матрицы смежности R₁.

14) Построить вспомогательную матрицу W₁, строки которой определяются вершинами r₅, c₁, c₂ и vd₁, входящими во второй формируемый кусок G₂, а столбцы – всеми остальными вершинами, входящими в кусок `G₂.

 

		vd2	r3	vt1	vs1
	r5	+3	–1	+2	–1
W1 =	c1	+1	–1		+3	(10)
	c2	+1	–3		+1
	vd1	+2		+1	+4

15) Выбрать в матрице (10) наибольший положительный элемент w_kq. Таким элементом является элемент w(vd₁vs₁) = +4. Это означает, что переместив вершину vd₁ из куска G₂ в кусок`G<sub>2</sub>, а вершину vs<sub>1</sub> из куска`G₂ в кусок G₂, количество внешних связей K между кусками G₂ и`G₂ уменьшится на 4 и составит K = 3 (рис. 9).

 

Рис. 9

16) Построить матрицу смежности R₁₁, изоморфную матрице R₁.

 

		r5	c1	c2	vs1	vd2	r3	vt1	vd1	ak, aq
	r5									–3
	c1									+1
	c2									–3
R11 =	vs1									–2	(11)
	vd2
	r3
	vt1									–1
	vd1									–2

17) Построить вспомогательную матрицу W₁₁.

 

		vd2	r3	vt1	vd1
	r5	–3	–3	–4	–5
W11 =	c1	–1	+1	–2	–1	(12)
	c2	–3	–3	–4	–5
	vs1	–2	–4	–3	–4

 

18) Выбрать в матрице (12) наибольший положительный элемент w_kq. Таким элементом является элемент w(c₁r₃) = +1, следовательно, вершину c₁ необходимо переместить из куска G₂ в кусок`G<sub>2</sub>, а вершину r<sub>3</sub> — из куска `G₂ в кусок G₂. Данная перестановка уменьшит количество внешних связей между кусками на 1. Результат перестановки представлен на рис. 10.

 

 

Рис. 10

19) Построить матрицу смежности R₁₂, изоморфную матрице R₁₁.

 

		r5	r3	c2	vs1	vd2	c1	vt1	vd1	ak, aq
	r5									–3
	r3
	c2									–1
R12 =	vs1									–4	(13)
	vd2
	c1
	vt1									–1
	vd1									–2

 

В дополнительном столбце матрицы смежности R₁₂ нет элементов a_k и a_q, имеющих положительное значение. Это означает, что и во вспомогательной матрице W₁₂ также не будет ни одного положительного элемента, поэтому процесс формирования куска G₂ = (X₂, U₂) следует считать законченным, где X₂ = {r₅, r₃, c_2, vs₁}. Оставшиеся четыре вершины vd₂, c₁, vt₁ и vd₁ образуют третий кусок G₃. Полученное разрезание графа G на три куска G₁, G₂ и G₃ представлено на рис. 11. Коэффициент разрезания рассматриваемого графа D(G) = 10/6 = 1,67.

 

Рис. 11

 

Результат разбиения принципиальной электрической схемы изделия на отдельные блоки представлен на рис. 12.

 

 

Рис. 12. Распределение радиоэлектронных компонентов по блокам РЭС