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

Программа работы

1. Повторить теоретический материал по теме 4.2.1.2 «Итерационный алгоритм компоновки РЭС с использованием чисел связности» по конспекту и по [1-3].

2. Разрезать граф принципиальной электрической схемы, полученный для своего варианта изделия в практической работе № 2, на три куска. Количество вершин n_i в кусках в зависимости от количества вершин в графе указано в таблице 1.

Таблица 1

Количество вершин в графе	Количество вершин в кусках	Количество вершин в графе	Количество вершин в кусках
G1	G2	G3	G1	G2	G3

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

4. Сделать вывод по работе, указав достоинства и недостатки итерационного метода разрезания графа с использованием чисел связности.

5. Дать предложения по совершенствованию данного метода.

6. Составить отчёт о выполнении работы.

Отчёт по практической работе оформляется на листах формата А4 в соответствии с ГОСТ 2.105-79.

Отчет по практической работе должен содержать:

1) номер работы;

2) название работы;

3) цель работы;

4) задание с указанием номера заданного варианта;

5) описание процесса разрезания графа на куски итерационным матричным методом с использованием чисел связности применительно к своему варианту задания;

6) результат разрезания графа заданного варианта принципиальной электрической схемы;

7) результат разбиения принципиальной электрической схемы изделия РЭС на отдельные конструктивно законченные части (блоки);

8) сравнить количество внешних связей между сформированными кусками графа с количеством внешних связей между скомпонованными блоками (физическими) РЭС.

Краткие теоретические сведения

Общие сведения

Метод разрезания графа с использованием чисел связности является итерационным методом. Суть итерационных методов заключается в том, что граф произвольным образом разрезается на заданное количество кусков, после чего с целью минимизации внешних связей осуществляется перестановка вершин из одного куска в другой. При реализации метода с использованием чисел связности осуществляется поочерёдное формирование кусков. Исходный граф произвольно разрезается на два куска G₁ = (X₁, U₁) и G^* = (X^*, U^* ), где X₁ – множество вершин, входящих в первый кусок; X^* = X\X₁ – остальные вершины. После этого по определённым критериям вершины из одного куска переставляются в другой таким образом, чтобы свести к минимуму количество рёбер, соединяющих вершины куска G₁ с вершинами куска G^*. По окончании перестановки кусок G₁ удаляется из исходного графа. Из множества вершин X\X₁, не вошедших в сформированный кусок G₁, аналогичным образом формируется второй кусок G₂ графа. Указанная последовательность действий выполняется до тех пор, пока не будет закончено разрезание графа на заданное количество кусков.

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

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

Рис. 1

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

a(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₂).

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

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

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

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

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

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

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

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

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

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

Рис. 2

Рис. 3

Для вершины x₃ a(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	ak, aq
	x1									-1
	x2									+1
	x3
R0 =	x4									-3	(2)
	x5									-1
	x6									+1
	x7									-1
	x8									-2

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

a(xi)=

Srkv – S rkl,если xk Î R1 Srkl – S 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). Примеры вычисления чисел связности:

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

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

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

a(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 = a_k + a_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₀₁ вновь подсчитываются числа связности a_k и a_k и строится вспомогательная матрица W₀₁, по которой определяется следующая пара вершин для очередной перестановки. Этот процесс повторяется до тех пор, пока во вспомогательной матрице W_0(n–1) не останется ни одного положительного элемента.