Пример разрезания графа на куски
Итерационным методом с использованием чисел связности
Рассмотрим пример разрезания графа с использованием чисел связности. Для примера с целью сравнения результатов выбран граф G (рис. 4), который использовался для иллюстрации последовательного метода разрезания графов в практической работе № 3.
Рис. 4
Задание
1)Разрезать граф G = (X, U), содержащий 12 вершин (рис. 4) на три куска по четыре вершины в каждом, используя числа связности.
2) Определить коэффициент разрезания.
Решение
1)Составить матрицу смежности R0 графа G.
| r1 | r2 | r3 | r4 | r5 | c1 | c2 | vd1 | vd2 | vd3 | vt1 | vs1 | ak, aq | |||
| r1 | +1 | ||||||||||||||
| r2 | +1 | ||||||||||||||
| r3 | +2 | ||||||||||||||
| r4 | +2 | ||||||||||||||
| r5 | –3 | ||||||||||||||
| R0 = | c1 | –3 | (5) | ||||||||||||
| c2 | –2 | ||||||||||||||
| vd1 | –1 | ||||||||||||||
| vd2 | –2 | ||||||||||||||
| vd3 | |||||||||||||||
| vt1 | –2 | ||||||||||||||
| vs1 | –1 | ||||||||||||||
2) Разрезать граф G на два куска G1 и`G1, выделив в матрице смежности R0 подматрицу R(1)0 порядка n1, где n1 – количество элементов, входящих в первый кусок G1. Результат разрезания представлен на рис. 5. Количество внешних связей между кусками K = 6.
Рис. 5
3) Подсчитать числа связности по формуле (3). Числа связности ak и aq указаны в дополнительном столбце матрицы смежности R0.
4) Построить вспомогательную матрицу W0, строки которой определяются вершинами r1, r2, r3 и r4, входящими в первый кусок G1, а столбцы – всеми остальными вершинами графа G (вершинами куска`G1).
| r5 | c1 | c2 | vd1 | vd2 | vd3 | vt1 | vs1 | |||
| r1 | –2 | –2 | –1 | –2 | –1 | +1 | –1 | |||
| W(1) = | r2 | –2 | –2 | –1 | –1 | +1 | –1 | (6) | ||
| r3 | –1 | –1 | +1 | +2 | –2 | –3 | ||||
| r4 | –1 | –1 | –2 | +1 | +1 | |||||
Элементы вспомогательной матрицы определяются по формуле (4).
В качестве примера рассмотрим вычисление некоторых элементов wkq вспомогательной матрицы (6)
w(r1c2) = a(r1) + a(c2) – 2r(r1c2) = 1 + (–2) – 2 ´ 0 = 1 – 2 = –1
w(r2vd1) = a(r2) + a(vd1) – 2r(r2vd1) = 1 + (–1) – 2 ´ 0 = 1 – 1 = 0
w(r1vd1) = a(r1) + a(vd1) – 2r(r1vd1) = 1 + (–1) – 2 ´ 1 = 1– 1 – 2 = –2
w(r4vs1) = a(r4) + a(vs1) – 2(r4vs1) = 2 + (–1) – 2 ´ 0 = 2 – 1 = +1
5) Выбрать в матрице (6) наибольший положительный элемент wkq. Таким элементом является элемент w(r3vd3) = +2. Следовательно, для минимизации внешних связей необходимо переставить r3 и vd3 строки и столбцы в матрице смежности R0. В результате такой перестановки количество внешних связей между кусками G1 и G1 должно уменьшиться на два и составит K = 4. Выполненная перестановка r3 и vd3 строк и столбцов означает, что вершина r3 из куска G1 переместилась в кусок `G1, а вершина vd3 – из куска `G1 в кусок G1. Результат перестановки представлен на рис. 6.
Рис. 6
6)Построить матрицу смежности R01, изоморфную матрице R0
| r1 | r2 | vd3 | r4 | r5 | c1 | c2 | vd1 | vd2 | r3 | vt1 | vs1 | ak, aq | |||
| r1 | +1 | ||||||||||||||
| r2 | +1 | ||||||||||||||
| vd3 | |||||||||||||||
| r4 | +0 | ||||||||||||||
| r5 | –3 | ||||||||||||||
| R01 = | c1 | –3 | (7) | ||||||||||||
| c2 | –2 | ||||||||||||||
| vd1 | –1 | ||||||||||||||
| vd2 | –2 | ||||||||||||||
| r3 | –2 | ||||||||||||||
| vt1 | –2 | ||||||||||||||
| vs1 | –3 | ||||||||||||||
7) Подсчитать числа связности по формуле (3). Числа связности ak и aq указаны в дополнительном столбце матрицы смежности R01.
8)Построить вспомогательную матрицу W01, строки которой определяются вершинами, входящими в первый кусок G1 ( r1, r2, vd3, r4), а столбцы – вершинами куска `G1.
| r5 | c1 | c2 | vd1 | vd2 | r3 | vt1 | vs1 | |||
| r1 | –2 | –2 | –1 | –2 | –1 | –1 | –2 | –2 | ||
| W01 = | r2 | –2 | –2 | –1 | –1 | –1 | –2 | –4 | (8) | |
| vd3 | –3 | –3 | –2 | –1 | –2 | –2 | –5 | –3 | ||
| r4 | –3 | –3 | –4 | –1 | –2 | –2 | –3 | –3 | ||
9) Во вспомогательной матрице W01 отсутствуют какие-либо положительные элементы. Это означает, что на данном этапе разрезания графа G отсутствует пара вершин, перестановка которых уменьшит количество внешних связей K между кусками G1 и `G1. Следовательно, кусок G1 = (X1, U1) считается сформированным, где X1 = {r1, r2, vd3, r4}.
10) Удалить из графа G кусок G1. В результате будет получен граф G*, представленный на рис. 7.
Рис. 7
11) Составить матрицу смежности R1 графа G*.
| r5 | c1 | c2 | vd1 | vd2 | r3 | vt1 | vs1 | ak, aq | |||
| r5 | +1 | ||||||||||
| c1 | +1 | ||||||||||
| c2 | –1 | ||||||||||
| R1 = | vd1 | +2 | (9) | ||||||||
| vd2 | +2 | ||||||||||
| r3 | –2 | ||||||||||
| vt1 | +1 | ||||||||||
| vs1 | +2 | ||||||||||
12) Разрезать граф G* на два куска G2 и`G2, выделив в матрице смежности R1 подматрицу R(1)1 порядка n2, где n2 — количество элементов, входящих во второй формируемый кусок G2. Результат разрезания графа представлен на рис. 8. Количество внешних связей между кусками K = 7.
Рис. 8
13) По формуле (3) подсчитать числа связности. Числа связности ak и aq указаны в дополнительном столбце матрицы смежности R1.
14) Построить вспомогательную матрицу W1, строки которой определяются вершинами r5, c1, c2 и vd1, входящими во второй формируемый кусок G2, а столбцы – всеми остальными вершинами, входящими в кусок `G2.
| vd2 | r3 | vt1 | vs1 | |||
| r5 | +3 | –1 | +2 | –1 | ||
| W1 = | c1 | +1 | –1 | +3 | (10) | |
| c2 | +1 | –3 | +1 | |||
| vd1 | +2 | +1 | +4 | |||
15) Выбрать в матрице (10) наибольший положительный элемент wkq. Таким элементом является элемент w(vd1vs1) = +4. Это означает, что переместив вершину vd1 из куска G2 в кусок`G2, а вершину vs1 из куска`G2 в кусок G2, количество внешних связей K между кусками G2 и`G2 уменьшится на 4 и составит K = 3 (рис. 9).
Рис. 9
16) Построить матрицу смежности R11, изоморфную матрице R1.
| r5 | c1 | c2 | vs1 | vd2 | r3 | vt1 | vd1 | ak, aq | |||
| r5 | –3 | ||||||||||
| c1 | +1 | ||||||||||
| c2 | –3 | ||||||||||
| R11 = | vs1 | –2 | (11) | ||||||||
| vd2 | |||||||||||
| r3 | |||||||||||
| vt1 | –1 | ||||||||||
| vd1 | –2 | ||||||||||
17) Построить вспомогательную матрицу W11.
| 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) наибольший положительный элемент wkq. Таким элементом является элемент w(c1r3) = +1, следовательно, вершину c1 необходимо переместить из куска G2 в кусок`G2, а вершину r3 — из куска `G2 в кусок G2. Данная перестановка уменьшит количество внешних связей между кусками на 1. Результат перестановки представлен на рис. 10.
Рис. 10
19)Построить матрицу смежности R12, изоморфную матрице R11.
| r5 | r3 | c2 | vs1 | vd2 | c1 | vt1 | vd1 | ak, aq | |||
| r5 | –3 | ||||||||||
| r3 | |||||||||||
| c2 | –1 | ||||||||||
| R12 = | vs1 | –4 | (13) | ||||||||
| vd2 | |||||||||||
| c1 | |||||||||||
| vt1 | –1 | ||||||||||
| vd1 | –2 | ||||||||||
В дополнительном столбце матрицы смежности R12 нет элементов ak и aq, имеющих положительное значение. Это означает, что и во вспомогательной матрице W12 также не будет ни одного положительного элемента, поэтому процесс формирования куска G2 = (X2, U2) следует считать законченным, где X2 = {r5, r3, c2, vs1}. Оставшиеся четыре вершины vd2, c1, vt1 и vd1 образуют третий кусок G3. Полученное разрезание графа G на три куска G1, G2 и G3 представлено на рис. 11. Коэффициент разрезания рассматриваемого графа D(G) = 10/6 = 1,67.
Рис. 11
Результат разбиения принципиальной электрической схемы изделия на отдельные блоки представлен на рис. 12.
Рис. 12. Распределение радиоэлектронных компонентов по блокам РЭС