Если ek и eq не смежные, и выполняется:
k+k> 0 |
(7.7) |
Б) если ek и eq смежные, и выполняется:
k+k>2 |
(7.8) |
В общем случае
k+k>2rkq |
(7.9) |
Докажем утверждение А). Очевидно, что перестановка целесообразна, еслиKii=Kii-K’ii>0 (например, было 5 внешних реберных соединений, стало 2), где Kii и K’ii- числа внешнего реберного соединения до и после перестановки и
Kii=rk(Gi )+ rq(Gi) |
(7.10) |
K’ii=rk(Gi)+ rq(Gi) |
(7.11) |
Тогда
Kii=rk(Gi)+rq(Gi)- k(Gi )-rq(Gi)= k+q>0 |
(7.12) |
Аналогично доказывается утверждение Б).
Теперь опишем суть алгоритма
Разрезание начинаем выделением в матрице R двух произвольных подматриц Q и Q. Порядок подматрицы Q равен числу вершин первого выделяемого куска, а порядок Q - числу всех оставшихся вершин.
Перестановка элементов из одного куска в другой будет соответствовать перестановке строк и столбцов матрицы R.
Сумма всех элементов подматрицы главной диагонали (деленная на два) соответствует числу внутренних ребер, а элементы, не принадлежащие главной диагонали, определяют соединяющие ребра между кусками. Тогда
|
(7.13) |
|
(7.14) |
Для каждой строки матрицы смежности подсчитываем k или q в зависимости от того, к какой подматрице принадлежит данная строка. Запишем эти числа справа матрицы.
Построим матрицу В =||bkq||ni*(n-ni), в которой строки определяются вершинами ekEi, а столбцы вершинами eqEi. На пресечении k– ой строки и q – го столбца элемент
bkq= k+q-2rkq |
(7.15) |
где rkq - элемент матрицы R.
Элемент bkq характеризует изменение числа соединительных ребер между кусками Gi и Gi при перестановке вершин ekGi и eqGi.
Выбираем для перестановки пару с наибольшим положительным bkq.
Осуществляется перестановка строк и столбцов k и q в матрице R и процесс снова повторяется пока в матрице B все элементы не станут со знаком «-».
Исключается из графа G кусок G1, соответствующий подматрице Q1 и процесс повторяется для матрицы Q1 с выделением куска с n2 элементами и т. д.
Пример.
З
адана
матрица смежности R0
графа G.
Надо разрезать граф с рис. 7.1 на 3
куска
по 5, 3, 4
вершин
R0= |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
+4 |
k |
|
2 |
0 |
0 |
0 |
2 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
||
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
+2 |
||
4 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
0 |
+1 |
||
5 |
0 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
1 |
0 |
0 |
+2 |
||
6 |
0 |
1 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
+1 |
q |
|
7 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
+2 |
||
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
-2 |
||
9 |
2 |
0 |
0 |
0 |
2 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
+2 |
||
10 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
+1 |
||
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
-4 |
||
12 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
3 |
0 |
-4 |
Согласно п.1 алгоритма выделяем в матрице R0 две подматрицы, в одной из которых 5 строк, т.е. включаем в первый кусок элементы e1, e2, e3, e4, e5 (т.к. разбиваем на куски по 5, 3, 4 вершин), в оставшейся части 7 строк.
Согласно п.3 алгоритма для каждой строки матрицы смежности по формулам (7.13) и (7.14) подсчитываем k и k и записываем в столбец справа от матрицы смежности. Число соединительных ребер между G1 и G1 (число внешних связей) для этого разбиения K1=14 (сумма элементов выделенной части)
Согласно п.4 алгоритма по формуле (7.15) построим матрицу В. Для примера:
b16= 1+5-2r16=4+1-2*0=5
b411= 4+11-2r411=1-4-2*0=-3
B0= |
|
e6 |
e7 |
e8 |
e9 |
e10 |
e11 |
e12 |
e1 |
+5 |
+2 |
+2 |
+2 |
+5 |
0 |
0 |
|
e2 |
-2 |
-1 |
-3 |
+1 |
0 |
-5 |
-5 |
|
e3 |
+3 |
+4 |
-2 |
+4 |
+3 |
-2 |
-4 |
|
e4 |
+2 |
+3 |
-1 |
-1 |
0 |
-3 |
-3 |
|
e5 |
-1 |
+4 |
0 |
+4 |
+1 |
-2 |
-2 |
Согласно п.4 алгоритма выбираем для перестановки пару с наибольшим положительным b16=5, т.е. из B0 выбираем для перестановки элементы e1 и e6.
Согласно п.5 алгоритма в матрице R0 переставляем строчки и столбцы, соответствующие e1 и e6 и смотрим, как изменится число внешних связей между кусками от этой перестановки.
Получается матрица R1
R1= |
|
6* |
2 |
3 |
4 |
5 |
1* |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
6* |
0 |
1 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
-1 |
k |
|
2 |
1 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-3 |
||
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
2 |
||
4 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
0 |
1 |
||
5 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
-2 |
||
1* |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
-4 |
q |
|
7 |
0 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
-2 |
||
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
-2 |
||
9 |
0 |
0 |
0 |
0 |
2 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
-2 |
||
10 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
||
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
-4 |
||
12 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
3 |
0 |
-2 |
Число соединительных ребер между G1 и G1 (число внешних связей) для этого разбиения K2=9 (сумма элементов выделенной части).
Число соединительных ребер между G1 и G1снизилось с 14 до 9, т.е. перестановка элементов e1 и e6 дает уменьшение числа соединительных ребер. Переход к п.4.
Согласно п.4 по формуле (7.15) строим матрицу В1:
B1= |
|
e1 |
e7 |
e8 |
e9 |
e10 |
e11 |
e12 |
e6 |
-5 |
-3 |
-3 |
-3 |
0 |
-5 |
-7 |
|
e2 |
-7 |
-7 |
-5 |
-5 |
0 |
-7 |
-7 |
|
e3 |
-2 |
0 |
-2 |
0 |
+5 |
-2 |
-4 |
|
e4 |
-3 |
-1 |
-1 |
-5 |
+2 |
-3 |
-3 |
|
e5 |
-6 |
-4 |
-4 |
-4 |
-1 |
-6 |
-6 |
Согласно п.4 алгоритма выбираем для перестановки пару с наибольшим положительным b310=5, т.е. из B1 выбираем для перестановки элементы e3 и e10.
В матрице R1 переставляем строчки и столбцы, соответствующие e3 и e10.
R’2= |
|
6 |
2 |
10 |
4 |
5 |
1 |
7 |
8 |
9 |
3 |
11 |
12 |
|
|
6 |
0 |
1 |
1 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
k |
|
2 |
1 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-3 |
||
10* |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-3 |
||
4 |
0 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
-1 |
||
5 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-2 |
||
1 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
-4 |
q |
|
7 |
0 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
-2 |
||
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
-4 |
||
9 |
0 |
0 |
0 |
0 |
2 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
-2 |
||
3* |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
-2 |
||
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
-4 |
||
12 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
3 |
0 |
-4 |
Число соединительных ребер между G1 и G1 снизилось до 4.
Согласно п.5 алгоритма т.к. в R’2 все значения αк и αq отрицательные, то в В2 не будет положительных элементов, и процесс выделения подграфа G1 закончен,
E1=e6,e2,e10,e4,e5
Строим кусок E2, содержащий 3 вершины Включаем в него элементы e1, e7, e8. Согласно п.6 алгоритма, исключив из R’2 кусок, соответствующий G1, получим:
R’’0= |
|
1 |
7 |
8 |
9 |
3 |
11 |
12 |
|
|
1 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
0 |
k |
|
7 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
||
8 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
4 |
||
9 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
4 |
q |
|
3 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
||
11 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
-2 |
||
12 |
0 |
0 |
1 |
0 |
1 |
3 |
0 |
-3 |
Строим матрицу B’’0:
B’’0= |
|
e9 |
e3 |
e1 |
e12 |
e1 |
1 |
-1 |
-3 |
-3 |
|
e7 |
-5 |
0 |
-7 |
-4 |
|
e8 |
6 |
2 |
0 |
-1 |
Выбираем max b89=6. Из B’’0 выбираем для перестановки элементы e8 и e9. В матрице R’’0 переставляем строчки и столбцы, соответствующие e8 и e9:
R’’1= |
|
1 |
7 |
9 |
8 |
3 |
11 |
12 |
|
|
1 |
0 |
2 |
2 |
0 |
0 |
0 |
0 |
-4 |
k |
|
7 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
-3 |
||
9 |
2 |
1 |
0 |
1 |
0 |
0 |
0 |
-2 |
||
8 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
-2 |
q |
|
3 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
-2 |
||
11 |
0 |
0 |
0 |
1 |
0 |
0 |
3 |
-4 |
||
12 |
0 |
0 |
0 |
1 |
1 |
3 |
0 |
-5 |
Число соединительных ребер между G2и G2снизилось с 7 до 1, т.е. перестановка элементов e8 и e9 дает уменьшение числа соединительных ребер.
Т.к. все αк и αq отрицательные, то в В’’1 все члены будут со знаком «–» и перестановки не может быть. Тогда
E2=e1,e7,e9, E3=e8,e3,e11,e12.
Число соединительных ребер между кусками =5.
Число внутренних ребер равно 9+5+7=21.
∆(G)=21/5=4,2.
Результат разбиения приведен на рис. 7.2.
