Краткие теоретические сведения. 1. Повторить теоретический материал по теме 4.2.1.3 «Итерационный матричный алгоритм разрезания графа» по конспекту и по [1]

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

1. Повторить теоретический материал по теме 4.2.1.3 «Итерационный матричный алгоритм разрезания графа» по конспекту и по [1].

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) сравнить количество внешних связей между сформированными кусками графа с количеством внешних связей между скомпонованными блоками (физическими) РЭС.

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

Любой граф можно описать матрицей смежности R, поэтому разрезание графа G на l кусков G1, G2,…, Gl эквивалентно разбиению матрицы на клетки. В случае матрицы смежности R разрезание графа соответствует разрезанию матрицы на l2 клеток (подматриц) как показано на рис. 1.

x1 x2 x3 xi xj xn
x1   G1            
x2            
x3            
R =         G2      
xi            
           
xj               G3
           
xn            
                     

Рис. 1

Клетки (подматрицы), расположенные по главной диагонали матрицы R, соответствуют кускам Gi графа G. Элементы, расположенные в диагональных клетках, определяют количество рёбер, соединяющих вершины куска Gi между собой (внутренние связи). Элементы, расположенные в остальных клетках, определяют количество рёбер, соединяющих куски между собой (внешние связи).

Задача разрезания графа на куски применительно к матричному методу формулируется следующим образом.

Пусть задан граф G = (X, U), имеющий n вершин и r рёбер. Требуетсяразрезать граф на куски так, чтобы получить максимальное значение функции

L = Краткие теоретические сведения. 1. Повторить теоретический материал по теме 4.2.1.3 «Итерационный матричный алгоритм разрезания графа» по конспекту и по [1] - student2.ru(1)

где L – суммарное количество рёбер внутри всех кусков графа;

aji = 1, если uj Î Uij,

aji = 0 в противном случае,

Uшо – множество внутренних рёбер куска Gj;

|Uij| = rj

Задаётся стандартная матрица F = ||fij||n, i, j Î J = {1, 2, …, n}, в которой по главной диагонали расположено столько единичных подматриц, на сколько кусков разрезается граф G. Порядок единичной подматрицы определяется количеством вершин, которое должно быть помещено в кусок Gi после разрезания графа.

Матрица смежности R разбивается на подматрицы в соответствии с разбиением матрицы F. Разбиение матрицы R в определённом смысле эквивалентно случайному разрезанию графа G на заданное количество кусков.

Методику разрезания графа G на куски матричным методом рассмотрим на примере выполнения конкретного задания. На рис. 2 представлен граф G принципиальной электрической схемы автоматического зарядного устройства. Разрезание этого графа на три куска по четыре вершины в каждом последовательным и итерационным методом с использованием чисел связности было рассмотрено в методических разработках к практическим работам №№ 3 и 4.

Краткие теоретические сведения. 1. Повторить теоретический материал по теме 4.2.1.3 «Итерационный матричный алгоритм разрезания графа» по конспекту и по [1] - student2.ru

Рис. 2

Задание

1)Разрезать граф G (рис. 2) на трикуска почетыре вершины в каждом.

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

3)Сравнить полученный результат с результатами выполнения практических работ №№ 3, 4.

Решение

1) Построить стандартную матрицу F, выделив в ней единичные подматрицы, соответствующие заданному разрезанию графа.

r1 r2 r3 r4 r5 c1 c2 vd1 vd2 vd3 vt1 vs1
r1
r2
r3
r4
r5
F = c1 (2)
c2
vd1
vd2
vd3
vt1
vs1
                               

2) Построить матрицу смежности R и разбить её на подматрицы в соответствии с разбиением матрицы F.

r1 r2 r3 r4 r5 c1 c2 vd1 vd2 vd3 vt1 vs1
r1
r2
r3
r4
r5
R = c1 (3)
c2
vd1
vd2
vd3
vt1
vs1
                               

Указанному разрезанию матрицы смежности R соответствует разрезание графа G, показанное на рис. 3. Общее количество рёбер внутри кусков L = 3, а количество внешних связей между кусками K = 13. Коэффициент разрезания графа D(G) = 3/13 = 0,23.

Краткие теоретические сведения. 1. Повторить теоретический материал по теме 4.2.1.3 «Итерационный матричный алгоритм разрезания графа» по конспекту и по [1] - student2.ru

Рис. 3. Разрезание графа, соответствующее разрезанию матрицы смежности (3)

Для максимизации функции L необходимо выполнить перестановки строк и столбцов матрицы смежности (3). С этой целью вводятся некоторые вспомогательные матрицы

3) Построить вспомогательную матрицу M = ||mij||n, где i, j Î J = {1, 2, …, n}, как результат умножения матриц Fи R:

M = F Ä R(4)

Элементы матрицы M вычисляются по формулам:

mij = Краткие теоретические сведения. 1. Повторить теоретический материал по теме 4.2.1.3 «Итерационный матричный алгоритм разрезания графа» по конспекту и по [1] - student2.ru , mji = Краткие теоретические сведения. 1. Повторить теоретический материал по теме 4.2.1.3 «Итерационный матричный алгоритм разрезания графа» по конспекту и по [1] - student2.ru (5)

Для рассматриваемого графа G матрица M будет иметь вид:

r1 r2 r3 r4 r5 c1 c2 vd1 vd2 vd3 vt1 vs1
r1
r2
r3
r4
r5
M = c1 (6)
c2
vd1
vd2
vd3
vt1
vs1
                               

Ниже приведены примеры использования формул (5) для вычисления некоторых значений элементов матрицы M.

m11 = f11 × (r1, r1) + f12 × (r1, r2) + f13 × (r1, r3) + f14 × (r1, r4) + f15 × (r1, r5) +

+ f16 × (r1, c1) + f17 × (r1, c2) + f18 × (r1, vd1) + f19 × (r1, vd2) + f110 × (r1, vd3) +

+ f111 × (r1, vt1) + f112 × (r1, vs1) =

= 1 × 0 + 1 × 0 + 1 × 0 + 1 × 0 + 0 × 0 + 0 × 0 + 0 × 1 + 0 × 1 + 0 × 0 + 0 × 1 + 0 × 2 = 0

m17 = f11 × (c2, r1) + f12 × (c2, r2) + f13 × (c2, r3) + f14 × (c2, r4) + f15 × (c2, r5) +

+ f16 × (c2, c1) + f17 × (c2, c2) + f18 × (c2, vd1) + f19 × (c2, vd2) + f110 × (c2, vd3) +

+ f111 × (c2, vt1) + f112 × (c2, vs1) =

= 1 × 0 + 1 × 0 + 1 × 0 + 1 × 1 + 0 × 1 + 0 × 1 + 0 × 0 + 0 × 0 + 0 × 0 + 0 × 0 + 0 × 1 = 1

m112 = f11 × (vs1, r1) + f12 × (vs1, r2) + f13 × (vs1, r3) + f14 × (vs1, r4) + f15 × (vs1, r5) +

+ f16 × (vs1, c1) + f17 × (vs1, c2) + f18 × (vs1, vd1) + f19 × (vs1, vd2) + f110 × (vs1, vd3) +

+ f111 × (vs1, vt1) + f112 × (vs1, vs1) =

= 1 × 0 + 1 × 1 + 1 × 1 + 1 × 0 + 0 × 2 + 0 × 0 + 0 × 1 + 0 × 0 + 0 × 0 + 0 × 0 + 0 × 0 = 2

m812 = f81 × (vs1, r1) + f82 × (vs1, r2) + f83 × (vs1, r3) + f84 × (vs1, r4) + f85 × (vs1, r5) +

+ f86 × (vs1, c1) + f87 × (vs1, c2) + f88 × (vs1, vd1) + f89 × (vs1, vd2) + f810 × (vs1, vd3) +

+ f811 × (vs1, vt1) + f812 × (vs1, vs1) =

= 0 × 0 + 0 × 1 + 0 × 1 + 0 × 0 + 1 × 2 + 1 × 0 + 1 × 1 + 1 × 0 + 0 × 0 + 0 × 0 + 0 × 0 +

+ 0 × 0 = 2 +1 = 3

Процесс продолжается до тех пор, пока не будут найдены все элементы матрицы M. Матрица M не является симметричной, т.е. в общем случае mij¹ mji.

4)Построить вспомогательную матрицу B = ||bij||n, где i, j Î J = {1, 2, …, n}. Матрица B представляет собой результат поэлементного перемножения матриц `F и R:

B = `F ´ R(7)

где `F – инверсия матрицы F, т.е. каждый единичный элемент матрицы F заменяется на нулевой и наоборот.

Для рассматриваемого примера матрица `F имеет вид:


   
  r1 r2 r3 r4 r5 c1 c2 vd1 vd2 vd3 vt1 vs1
r1
r2
r3
r4
r5
``F = c1 (8)
c2
vd1
vd2
vd3
vt1
vs1
                               

Элемент bij матрицы B определяется по формуле:

bij = `fij × rij (9)

где `fij – элемент матрицы `F.

Элементы первой строки матрицы B равны:

b11 = `f11 × (r1, r1) = 0; b12 = `f12 × (r1, r2) = 0; b13 = `f13 × (r1, r3) = 0;

b14 = `f14 × (r1, r4) = 0; b15 = `f15 × (r1, r5) = 0; b16 = `f16 × (r1, c1) = 0;

b17 = `f11 × (r1, c2) = 0; b18 = `f18 × (r1, vd1) = 1; b19 = `f19 × (r1, vd2) = 0;

b110 = `f110 × (r1, vd3) = 0; b111 = `f111 × (r1, vt1) = 0; b112 = `f112 × (r1, vs1) = 0;

Аналогично определяются все остальные элементы матрицы. В результате будет получена вспомогательная матрица B:

   
  r1 r2 r3 r4 r5 c1 c2 vd1 vd2 vd3 vt1 vs1
r1
r2
r3
r4
r5
B = c1 (10)
c2
vd1
vd2
vd3
vt1
vs1
                               

Матрица B является симметричной относительно главной диагонали: bij=bji.

5) Построить вспомогательную матрицу P = ||pij||n, где i, j Î J = {1, 2, …, n}. Матрица P определяется с помощью матриц M и B по формулам:

pij = mij – bij; pij = mij – bij(11)

Как следует из (11), матрица P не является симметричной.

Для рассматриваемого примера матрица P будет иметь вид:

   
r1 r2 r3 r4 r5 c1 c2 vd1 vd2 vd3 vt1 vs1
r1
r2
r3
r4
r5
P = c1 (12)
c2
vd1
vd2
vd3
vt1
vs1
                               

6) Для максимизации значения функции (1) после случайного разрезания графа необходимо выбрать пару вершин, принадлежащих разным кускам графа и переставить их, если значение L при этом увеличивается. Перестановочные коэффициенты определяются по формуле:

hij = pij + pji – (pii + pjj) (13)

Следует заметить, что вершины xi и xj принадлежат разным кускам. Отсюда следует, что первые два члена выражения (13) характеризуют внешние связи между кусками, а вторые два (в скобках) – внутренние. В таком случае положительное максимальное значение hij является условием для перестановки вершин из одного куска в другой. Для определения перестановочных коэффициентов целесообразно построить матрицу H = ||hij||n, где i, j Î J = {1, 2, …, n}. Так как матрица H строится только по результатам операций с элементами симметричной матрицы P, то матрица H также будет симметричной, поэтому достаточно построить только треугольную полуматрицу.


   
r1 r2 r3 r4 r5 c1 c2 vd1 vd2 vd3 vt1 vs1
r1 +2
r2   -1 -1 -1 +1 +1 +1 +1 +1
r3     -1 -1 -1 +1 +2 +2 +2
r4       -2 +2 +1 -1 +1 +3
r5         +1 +2
H = c1           +1 +4 (14)
c2             +1 -2
vd1               +2 +1 +1 +5
vd2                
vd3                  
vt1                    
vs1                      
                               

Наибольшее положительное значение имеет элемент h8-12, расположенный на пересечении строки vd1 и столбца vs1. После перемещения вершины vd1 из куска G2 в кусок G3, а вершины vs1 – из куска G3 в кусок G2 общее количество L рёбер внутри кусков увеличится на и 5 станет равным 8. Соответственно количество внешних связей K между кусками графа уменьшится и станет равным 8 (рис. 4). Коэффициент разрезания графа DG = 8/8 = 1.

Краткие теоретические сведения. 1. Повторить теоретический материал по теме 4.2.1.3 «Итерационный матричный алгоритм разрезания графа» по конспекту и по [1] - student2.ru

Рис. 4. Разрезание графа G после перестановки вершин vd1 и vs1

7) Переставить строки и столбцы vd1 и vs1 в матрице смежности (5.3). В результате будет получена матрица R(1):

r1 r2 r3 r4 r5 c1 c2 vs1 vd2 vd3 vt1 vd1
r1
r2
r3
r4
r5
R(1) = c1 (15)
c2
vs1
vd2
vd3
vt1
vd1
                               

8) По матрицам F (2) и R(1) (15) построить вспомогательную матрицу M(1). Матрица F будет оставаться неизменной до полного окончания процесса разрезания графа.

   
r1 r2 r3 r4 r5 c1 c2 vs1 vd2 vd3 vt1 vd1
r1
r2
r3
r4
r5
M(1) = c1 (16)
c2
vs1
vd2
vd3
vt1
vd1
                               

9) Построить вспомогательную матрицу B(1), используя матрицы `F и R(1). Матрица `F является инверсией матрицы F, поэтому она также будет неизменной до окончания решения задачи.

   
r1 r2 r3 r4 r5 c1 c2 vs1 vd2 vd3 vt1 vd1
r1
r2
r3
r4
r5
B(1) = c1 (17)
c2
vs1
vd2
vd3
vt1
vd1
                               

10)По матрицам M(1) и B(1), руководствуясь формулой (11), построить вспомогательную матрицу P(1).

Наши рекомендации