2.2. Разрезание графа с использованием чисел связности

Если некоторый граф G = (X, U) произвольно разрезать на два куска G₁ и G₂, то в общем случае в каждом куске любая вершина x_i может быть связана с вершинами, лежащими внутри того же куска и с верши­нами, не принадлежащими этому куску (рис. 1). Рёбра, соединяющие вер­шину x_i с другими вершинами внутри куска, назовём  внутренними, а рёбра, соединяющие эту вершину с вершинами, не вошедшими в данный кусок – внешними. Это обстоятельство позволяет для каждой вершины графа, разрезанного на куски, ввести числовую характеристику, которая называется числом связности.

Рис. 1

Число связности (x_i) вершины x_i – это разность количества внешних и внутренних рёбер, инцидентных вершине x_i. Тогда формула для определения числа связности будет иметь вид:

(xi)=

ri(G1) – ri (G2), если xi  X2 ri(G2) – ri(G1), если xi  X1

(1)

где r_i(G₁) – количество рёбер, соединяющих вершину x_i с вершинами куска G₁ = (X₁, U₁);

r_i(G₂) – количество рёбер, соединяющих вершину x_i с вершинами куска G₂ = (X₂, U₂).

Подсчитаем числа связности (x₁), (x₂), ..., (x₇) для всех вершин графа G = (X, U), представленного на рис. 1. Вершина x₁  X₁. Количество рёбер, связывающих эту вершину с вершинами, принадлежащими куску G₂: r₁(G₂) = 2. Количество рёбер, связывающих вершину x₁ с вершинами куска G₁: r₁(G₁) = 3. Тогда в соответствии с (1) (x₁) = r₁(G₂) – r₁(G₁) = 2 – 3 = –1

Аналогично для вершин x₂ и x₃, принадлежащих куску G₁:

(x₂) = r₂(G₂) – r₂(G₁) = 3 – 2 = +1; (x₃) = r₃(G₂) – r₃(G₁) = 3 – 3 = 0

Вершина x₄  X₂. Количество рёбер, связывающих эту вершину с вершинами, принадлежащими кускам G₁ и G₂: r₄(G₁) = 1; r₄(G₂) = 4. Тогда в соответствии с (1): (x₄) = r₄(G₁) – r₄(G₂) = 1 – 4 = –3.

Аналогично для остальных вершин, принадлежащих куску G₂:

(x₅) = r₅(G₁) – r₅(G₂) = 2 – 3 = –1; (x₆) = r₆(G₁) – r₆(G₂) = 3 – 2 = +1;

(x₇) = r₇(G₁) – r₇(G₂) = 2 – 3 = –1; (x₈) = r₈(G₁) – r₈(G₂) = 0 – 2 = –2.

Как видно из полученных результатов, число связности может быть отрицательным, положительным и равным нулю.

Если число связности (x_i) отрицательно, то это означает, что при перемещении вершины x_i из одного куска в другой количество внешних рёбер, соединяющих куски, увеличится. Так, например, (x₁) = –1. Количество внешних рёбер (связей) между кусками G₁ и G₂ равно 8 (рис.1). Если вершину x₁ переместить из куска G₁ в кусок G₂, то количество внешних связей между этими кусками увеличится на 1 и будет равно 9 (рис. 2).

Положительное значение числа связности вершины x_i означает, что при перемещении этой вершины в другой кусок количество внешних связей между кусками уменьшится. В рассматриваемом примере для вершины x₂ число связности  (x₂) = +1 (рис. 1). Если эту вершину переместить из куска G₁ в кусок G₂, то количество связей между кусками уменьшится на 1 и будет равно 7 (рис. 3).

Рис. 2

Рис. 3

Для вершины x₃ (x₃) = 0. Это означает, что перемещение данной вершины из куска G₁ в кусок G₂ не изменит количества внешних связей между этими кусками. Два ребра U₃₅ и ребро U₃₇ (рис. 1) станут внутренними рёбрами куска G₂, а два ребра U₃₁ и ребро U₃₂ станут внешними связями между кусками G₁ и G₂.

Так как граф G = (X, U) достаточно полно описывается матрицей смежности, то и разрезание этого графа на куски G₁ и G₂ также можно показать в матрице смежности. Для этого в матрице смежности R₀ выделяют по главной диагонали две подматрицы R⁽¹⁾₀ и R⁽²⁾₀. При этом порядок подматрицы R⁽¹⁾₀ равен количеству вершин, которые должны находиться в первом куске G₁, а порядок подматрицы R⁽²⁾₀ – количеству всех оставшихся вершин графа, образующих второй кусок G₂ графа G.

		x1	x2	x3	x4	x5	x6	x7	x8	k, q
	x1	0	1	2	1	0	0	1	0	-1
	x2	1	0	1	0	0	3	0	0	+1
	x3	2	1	0	0	2	0	1	0	0
R0 =	x4	1	0	0	0	3	0	1	0	-3	(2)
	x5	0	0	2	3	0	0	0	0	-1
	x6	0	3	0	0	0	0	1	1	+1
	x7	1	0	1	1	0	1	0	1	-1
	x8	0	0	0	0	0	1	1	0	-2

Затем следует так переставить строки и столбцы матрицы смежности, чтобы количество рёбер между кусками G₁ и G₂ стало минимальным. С этой целью для каждой строки матрицы смежности необходимо подсчитать число связности по формуле

(xi)=

rkv –  rkl, если xk  R1 rkl –  rkv, если xk  R2

(3)

где l  I = {1, 2, …, p}, v  V = {p+1, p+2, …, n}, причём строка x_v принадлежит подматрице R^’’­₀, а строка x_l – подматрице R^’₀;

k  J = {1, 2, …, n};

p – старший индекс подматрицы R^’₀.

Значения чисел связности для каждой строки матрицы смежности записаны в дополнительном столбце матрицы (4). Примеры вычисления чисел связности:

(x₁) = (r₁₄ + r₁₇) – (r₁₂ + r₁₃) = (1 + 1) – (1 + 2) = –1;

(x₃) = (r₁₅ + r₁₇) – (r₁₁ + r₁₂) = (2 + 1) – (2 + 1) = 0;

(x₅) = r₅₃ – r₅₄ = 2 – 3 = –1;

(x₇) = (r₇₁ + r₇₃) – (r₇₄ + r₇₆ + r₇₈) = (1 + 1) – (1 + 1 + 1) = –1.

После подсчёта чисел связности необходимо построить вспомогательную прямоугольную матрицу W₀ = w_ij порядка n_i  (n – n_i), в которой строки определяются вершинами из подматрицы R^(1)­₀, а столбцы – вершинами из подматрицы R⁽²⁾₀. Элемент w_kq, который расположен в матрице W₀ на пересечении k-й строки (k  I) и q-го столбца (q  V), определяется по формуле

w_kq =  _k + _q – 2r_kq (4)

где r_kq – элемент матрицы смежности R₀.

Элемент w_kq  вспомогательной матрицы W₀ характеризует изменение количества внешних рёбер, соединяющих куски G₁ и G₂, при перестановке вершин x_k  X₁ и x_q  X₂ из одного куска в другой. Перестановке подлежат те вершины x_k и x_q, для которых элемент w_kq имеет максимальное положительное значение. Если таких элементов несколько, то выбирается тот, у которого соответствующие ему вершины x_k и x_q имеют меньшую локальную степень.

После перестановки строк и столбцов x_k и x_q будет получена матрица R₀₁, изоморфная исходной матрице смежности R₀ (2). В матрице смежности R₀₁ вновь подсчитываются числа связности _k и _k и строится вспомогательная матрица W₀₁, по которой определяется следующая пара вершин для очередной перестановки. Этот процесс повторяется до тех пор, пока во вспомогательной матрице W_0(n–1)  не останется ни одного положительного элемента.

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

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

Рассмотрим пример разрезания графа с использованием чисел связности. Для примера с целью сравнения результатов выбран граф 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	k, q
	r1	0	0	0	0	0	0	0	1	0	0	0	0	+1
	r2	0	0	0	0	0	0	0	0	0	0	0	1	+1
	r3	0	0	0	0	0	0	0	0	0	0	1	1	+2
	r4	0	0	0	0	0	0	1	0	0	1	0	0	+2
	r5	0	0	0	0	0	0	1	0	0	0	0	2	–3
R0 =	c1	0	0	0	0	0	0	1	0	1	0	1	0	–3	(5)
	c2	0	0	0	0	1	1	0	0	0	0	0	1	–2
	vd1	1	0	0	0	0	0	0	0	1	0	1	0	–1
	vd2	0	0	0	0	0	1	0	1	0	0	0	0	–2
	vd3	0	0	0	1	0	0	0	0	0	0	1	0	0
	vt1	0	0	1	0	0	1	0	1	0	1	0	0	–2
	vs1	0	1	1	0	2	0	1	0	0	0	0	0	–1

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

Рис. 5

3) Подсчитать числа связности по формуле (3). Числа связности  _k и _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	0
W(1) =	r2	–2	–2	–1	0	–1	+1	–1	0	(6)
	r3	–1	–1	0	+1	0	+2	–2	–3
	r4	–1	–1	–2	+1	0	0	0	+1

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

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

w(r₁c₂) = (r₁) + (c₂) – 2r(r₁c₂) = 1 + (–2) – 2  0 = 1 – 2 = –1

w(r₂vd₁) = (r₂) + (vd₁) – 2r(r₂vd₁) = 1 + (–1) – 2  0 = 1 – 1 = 0

w(r₁vd₁) = (r₁) + (vd₁) – 2r(r₁vd₁) = 1 + (–1) – 2  1 = 1– 1 – 2 = –2

w(r₄vs₁) = (r₄) + (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_1, а вершина vd₃ – из куска G₁ в кусок G₁. Результат перестановки представлен на рис. 6.

Рис. 6

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

		r1	r2	vd3	r4	r5	c1	c2	vd1	vd2	r3	vt1	vs1	k, q
	r1	0	0	0	0	0	0	0	1	0	0	0	0	+1
	r2	0	0	0	0	0	0	0	0	0	0	0	1	+1
	vd3	0	0	0	1	0	0	0	0	0	0	1	0	0
	r4	0	0	1	0	0	0	1	0	0	0	0	0	+0
	r5	0	0	0	0	0	0	1	0	0	0	0	2	–3
R01 =	c1	0	0	0	0	0	0	1	0	0	1	1	0	–3	(7)
	c2	0	0	0	0	1	1	0	0	0	0	0	1	–2
	vd1	1	0	0	0	0	0	0	0	1	0	1	0	–1
	vd2	0	0	0	0	0	1	0	1	0	0	0	0	–2
	r3	0	0	0	0	0	0	0	0	0	0	1	1	–2
	vt1	0	0	1	0	0	1	0	1	0	1	0	0	–2
	vs1	0	1	0	0	2	0	1	0	0	1	0	0	–3

7) Подсчитать числа связности по формуле (3). Числа связности _k и _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	0	–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	k, q
	r5	0	0	1	0	0	0	0	2	+1
	c1	0	0	1	0	1	0	1	0	+1
	c2	1	1	0	0	0	0	0	1	–1
R1 =	vd1	0	0	0	0	1	0	1	0	+2	(9)
	vd2	0	1	0	1	0	0	0	0	+2
	r3	0	0	0	0	0	0	1	1	–2
	vt1	0	1	0	1	0	1	0	0	+1
	vs1	2	0	1	0	0	1	0	0	+2

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

Рис. 8

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

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

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

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

Рис. 9

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

		r5	c1	c2	vs1	vd2	r3	vt1	vd1	k, q
	r5	0	0	1	2	0	0	0	0	–3
	c1	0	0	1	0	1	0	1	0	+1
	c2	1	1	0	1	0	0	0	0	–3
R11 =	vs1	2	0	1	0	0	1	0	0	–2	(11)
	vd2	0	1	0	0	0	0	0	1	0
	r3	0	0	0	1	0	0	1	0	0
	vt1	0	1	0	0	0	1	0	1	–1
	vd1	0	0	0	0	1	0	1	0	–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₂, а вершину r₃ — из куска G₂ в кусок G₂. Данная перестановка уменьшит количество внешних связей между кусками на 1. Результат перестановки представлен на рис. 10.

Рис. 10

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

		r5	r3	c2	vs1	vd2	c1	vt1	vd1	k, q
	r5	0	0	1	2	0	0	0	0	–3
	r3	0	0	0	1	0	0	1	0	0
	c2	1	0	0	1	0	1	0	0	–1
R12 =	vs1	2	1	1	0	0	0	0	0	–4	(13)
	vd2	0	0	0	0	0	1	0	1	0
	c1	0	0	1	0	1	0	1	0	0
	vt1	0	1	0	0	0	1	0	1	–1
	vd1	0	0	0	0	1	0	1	0	–2

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

Рис. 11

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

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