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

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

 

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

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

 

Таблица 1

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

 

 

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

 

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

 

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

 

 

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

Рис. 1

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

 

a(xi)= ri(G1) – ri (G2),если xi Î X2 ri(G2) – ri(G1),если xi Î X1 (1)

 

 

где ri(G1) – количество рёбер, соединяющих вершину xi с вершинами куска G1 = (X1, U1);

ri(G2) – количество рёбер, соединяющих вершину xi с вершинами куска G2 = (X2, U2).

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

Аналогично для вершин x2 и x3, принадлежащих куску G1:

a(x2) = r2(G2) – r2(G1) = 3 – 2 = +1; a(x3) = r3(G2) – r3(G1) = 3 – 3 = 0

Вершина x4 Î X2. Количество рёбер, связывающих эту вершину с вершинами, принадлежащими кускам G1 и G2: r4(G1) = 1; r4(G2) = 4. Тогда в соответствии с (1): a(x4) = r4(G1) – r4(G2) = 1 – 4 = –3.

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

a(x5) = r5(G1) – r5(G2) = 2 – 3 = –1; a(x6) = r6(G1) – r6(G2) = 3 – 2 = +1;

a(x7) = r7(G1) – r7(G2) = 2 – 3 = –1; a(x8) = r8(G1) – r8(G2) = 0 – 2 = –2.

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

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

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

 

 

  Рис. 2   Рис. 3

 

Для вершины x3 a(x3) = 0. Это означает, что перемещение данной вершины из куска G1 в кусок G2 не изменит количества внешних связей между этими кусками. Два ребра U35 и ребро U37 (рис. 1) станут внутренними рёбрами куска G2, а два ребра U31 и ребро U32 станут внешними связями между кусками G1 и G2.

Так как граф G = (X, U) достаточно полно описывается матрицей смежности, то и разрезание этого графа на куски G1 и G2 также можно показать в матрице смежности. Для этого в матрице смежности R0 выделяют по главной диагонали две подматрицы R(1)0 и R(2)0. При этом порядок подматрицы R(1)0 равен количеству вершин, которые должны находиться в первом куске G1, а порядок подматрицы R(2)0 – количеству всех оставшихся вершин графа, образующих второй кусок G2 графа 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  
                       

 

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

 

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}, причём строка xv принадлежит подматрице R’’­0, а строка xl – подматрице R’0;

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

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

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

a(x1) = (r14 + r17) – (r12 + r13) = (1 + 1) – (1 + 2) = –1;

a(x3) = (r15 + r17) – (r11 + r12) = (2 + 1) – (2 + 1) = 0;

a(x5) = r53 – r54 = 2 – 3 = –1;

a(x7) = (r71 + r73) – (r74 + r76 + r78) = (1 + 1) – (1 + 1 + 1) = –1.

После подсчёта чисел связности необходимо построить вспомогательную прямоугольную матрицу W0 = |wij| порядка ni ´ (n – ni), в которой строки определяются вершинами из подматрицы R(1)­0, а столбцы – вершинами из подматрицы R(2)0. Элемент wkq, который расположен в матрице W0 на пересечении k-й строки (k Î I) и q-го столбца (q Î V), определяется по формуле

 

wkq = ak + aq – 2rkq(4)

 

где rkq – элемент матрицы смежности R0.

Элемент wkq вспомогательной матрицы W0 характеризует изменение количества внешних рёбер, соединяющих куски G1 и G2, при перестановке вершин xk Î X1 и xq Î X2 из одного куска в другой. Перестановке подлежат те вершины xk и xq, для которых элемент wkq имеет максимальное положительное значение. Если таких элементов несколько, то выбирается тот, у которого соответствующие ему вершины xk и xq имеют меньшую локальную степень.

После перестановки строк и столбцов xk и xq будет получена матрица R01, изоморфная исходной матрице смежности R0 (2). В матрице смежности R01 вновь подсчитываются числа связности ak и ak и строится вспомогательная матрица W01, по которой определяется следующая пара вершин для очередной перестановки. Этот процесс повторяется до тех пор, пока во вспомогательной матрице W0(n–1) не останется ни одного положительного элемента.