Декомпозиция элементов принципиальной схемы

1.1. Последовательный алгоритм декомпозиции

Задача: используя последовательный алгоритм распределения элементов выделить в графе G(X,U) три подграфа по три вершины в каждом, таким образом, чтобы общее число связей между подграфами было минимальным.

Исходные данные: граф G, разбитый произвольным образом на три подграфа G1, G2, G3. Каждый подграф содержит по три вершины.

На основе графа G сформируем матрицу смежности:

A(i,j) =

X1 X2 X3 X4 X5 X6 X7 X8 X9 X1 X2 X3 X4 X5 X6 X7 X8 X9 p

Расчёты производятся по следующим формулам:

δ(xi)=p(xi)-2Σaij, где δ(xi) – относительный вес вершины, равный приращению числа внешних рёбер формируемого подграфа, p(xi) – локальная степень вершины, aij – элемент A(I,j), где xj – вершины ранее включённые в G1.

Ход решения:

1) Выбираем вершину с минимальной степенью: p {x2, x5, x7, x8, x9} =2; поскольку кратные рёбра в данном графе отсутствуют, произвольно берём в качестве первого элемента подграфа G1 вершину x2: X(G1)={x2}.

2) Находим смежные вершины подграфа G1: Г(G1) = {x4, x5}; δ(x4) = 1, δ(x5) = 0; т.к. δ(x5) <δ(x4), добавляем вершину x5 к множеству вершин графа G1: X(G1) = {x2, x5}.

3) Находим смежные вершины G1: Г(G1) = {x1, x4}; δ(x1) = 2, δ(x4) = 1; т.к. δ(x4) <δ(x1), добавляем к G1 очередную вершину x4.

На этом формирование G1 закончено. Имеем: X(G1) = {x2, x5, x4}.

4) Из множества свободных вершин с наименьшей p {x7, x8, x9} произвольно, берём x7 в качестве первой вершины подграфа G2.

5) Находим смежные вершины X(G2): Г(G2) = {x3, x6}, δ(x3) = 2, δ(x6) = 1; т.к. δ(x6) <δ(x3), включаем в G2 вершину x6. X(G2) = {x7, x6}.

6) Находим смежные вершины G2: ГG2 = {x3, x9}, δ(x3) = 0, δ(x9) = 0. Предпочтение отдадим вершине в минимальной p. p(x9) < p(x3), добавим вершину x9 в подграф G2.

На этом формирование G2 закончено.

Имеем: X(G1) = {x6, x7, x9}.

7) В третий подграф G3 войдут все оставшиеся вершины:

Имеем: X(G2) = {x1, x3, x8}.

Число межмодульных связей: 6

при этом подграфы G1 и G2 не имеют непосредственных связей друг с другом.

1.2. Итерационный алгоритм декомпозиции

1. Задача: путём взаимной перестановки вершин, находящихся в разных подграфах G(X,U) добиться такого их распределения, чтобы общее число связей между подграфами было минимальным.

2. Исходные данные: граф G, разбитый произвольным образом на три подграфа G1, G2, G3. Каждый подграф содержит по три вершины.

A(i,j) =

X1 X2 X3 X4 X5 X6 X7 X8 X9 X1 X2 X3 X4 X5 X6 X7 X8 X9

Расчёты производятся по следующим формулам:

Δr_gh = (Σa_gi - Σa_gj) + (Σa_hi – Σa_hj) – 2a_gh, где

Δr_gh – приращение числа рёбер при парном обмене вершин x_g X X_a и x_h X X_b,

Σa_gi и Σa_gj – число рёбер соединяющих вершину g со смежными вершинами, входящими в X_a и X\X_a соответственно.

Σa_hi и Σa_hj – число рёбер соединяющих вершину h со смежными вершинами, входящими в X_b и X\X_b соответственно.

a_gh – число рёбер, соединяющих вершины g и h.

Ход решения:

1. Для каждой g-ой строки матрицы A(I,j) подсчитаем (Σa_gi - Σa_gj) и запишем результат справа от матрицы.
2. Строим вторую матрицу той же размерности. В каждую её ячейку запишем значений приращения числа рёбер между подматрицами Δr_gh при перестановке g-ой и h-ой вершин.
3. В полученной матрице приращений находим элемент с максимальным значением, которое характеризует на сколько уменьшится количество внешних связей между подграфами при перестановке вершин, отвечающих данным строке и столбцу.

X1 X2 X3         X1 X2 X3 X4 X5 X6 X7 X8 X9 1_2 1_3 2_3 X1 - X2 - X3 - X4 - X5 - X6 - X7 - X8 - -1 X9 - -1

X1 X2 X3   X1 X2 X3 X4 X5 X6 X7 X8 X9 X1 -2 -1 X2 3 -1 X3 3 -1 -1 X4       -1 X5       -1 X6       X7             X8             X9

1. На первом шаге в матрице приращений имеются два максимальных значения, которые соответствуют двум возможным перестановкам: (2, 4) и (3, 5), каждая из которых уменьшит количество внешних рёбер на три.

X1 X2 X3         X1 X4 X3 X2 X5 X6 X7 X8 X9 1_2 1_3 2_3 X1 -1 -1 - X4 -1 -2 - X3 -1 -1 - X2 - -1 X5 - -1 X6 - X7 - X8 - -1 X9 - -1

X1 X2 X3   X1 X4 X3 X2 X5 X6 X7 X8 X9 X1 -1 -3 -3 -2 X4 -3 -1 -1 -2 -3 X3 -1 -1 -2 -2 -1 -2 X2       -2 -1 X5       -2 -1 X6       1 1 X7             X8             X9

1. Произведём перестановку строк и столбцов соответствующих вершинам 2 и 4.

1. На втором шаге в матрице приращений имеются два максимальных значения, которые соответствуют двум возможным перестановкам: (6, 7) и (6, 8), каждая из которых уменьшит количество внешних рёбер на единицу.
2. Произведём перестановку строк и столбцов соответствующих вершинам 6 и 7.
3. На третьем шаге матрица приращений не содержит положительных значений, следовательно, ни одна из последующих перестановок не приведёт к уменьшению число внешних рёбер.

1. Всего произведено две перестановки: (2, 4) и(6, 7).
2. Приведём полученный граф:

1. Применение алгоритма декомпозиции путём перестановки позволило сократить количество внешних рёбер с 10 до 6. Получили тот же результат, что и методом последовательной декомпозиции, однако в первом случае распределение связей более оптимально.