Пусть задан граф G=(E,U) и подмножество запрещенных элементов QÍE, |Q|=q. Требуется найти такое разбиение P(G) графа G на m одинаковых кусков G1,G2,…,Gm, чтобы суммарное число соединяющих ребер было минимальным.
Рассмотрим последовательный алгоритм разбиения графа, приводящий к минимуму числа соединительных ребер за конечное число шагов при наличии ограничений.
Основная идея метода заключается в следующем. Сначала по кускам графа распределяются запрещенные вершины. Формирование первого куска начинается с вершины eεÎQ, которую априорно считаем входящей во множество вершин E1 первого куска G1=(E1,U1).
Составление кусков будем вести по уровням. Вершина eε в куске G1 образует первый уровень и на этом уровне E1={eε}.
Для определения вершин второго уровня, т.е. второй вершины, которую необходимо поместить в G1, строится множество вершин, смежных eε.
Обозначим множество, содержащее вершину eε, смежные ей вершины, и не содержащее других запрещенных вершин через Гeε.
Введем понятие относительного веса d(еi) для любой вершины еi графа G:
d(еi)=r(ei)-Srik, k=1,m
(4.1)
где Srik, k=1,m - число ребер, соединяющих вершину ei с вершинами сформированного подмножества E1, m=|E1|.
Из приведенного выражения (4.1) следует, что для получения требуемого куска из множества Гeε необходимо выбрать вершину с минимальной величиной d(еi*) (чем больше связей у вершины из Гeε с вершинами из G1, тем меньше разность в (4.1) и тем меньше величина d(еi))
d(еi*) = min d(еi), eiÎГeε
(4.2)
где iÎI=(1,2,…,t), t=|Гeε|
Вершина еi* является вершиной второго уровня. На втором уровне E1={eε,ei*}.
Далее рассматривается множество ГeεUГei*, и для каждой вершины еkÎГeεUГei*, определяется относительный вес по (4.1). Выбрав вершину еk* с минимальным весом, получим E1={eε,ei*,еk*}.
Указанный процесс продолжается до тех пор, пока множество вершин E1 не будет содержать n1 вершин. Полученный кусок G1 удаляется из графа G. Последующие куски формируются аналогично.
Если при формировании куска G1 графа G несколько рассматриваемых вершин имеют одинаковый относительный вес, то в кусок G помещается вершина, имеющая большую локальную степень. Покажем это.
Пусть для вершин ei,еjÎE графа G=(E,U) локальные степени r(ei)>r(ej). В рассматриваемом случае d(еi)=d(еj) , а по определению
d(еi) = r(ei) - Srik,
d(еj) = r(ej) - Srjk, k=1,m, т.е.
r(ei) - Srik=r(ej) - Srjk
(4.3)
r(ei) -r(ej) =Srik - Srjk
Т.к. r(ei)>r(ej), то
Srik>Srjk, k=1,m
(4.4)
Обозначим число внешних соединительных ребер куска Gi до внесения в него вершин еi и ej через zi. Тогда при внесении в кусок Gi вершины ei число внешних ребер станет
d*(еi)= zi-Srik+(r(ei)- Srik)= d(еi)+ zi-Srik
(4.5)
новое + старое число ребер
zi-Srik: zi – было внешних выводов в Gi; Srik – соединились с новым элементом и стали внутренними;r(ei)- Srik: r(ei)-было у ei внешних выводов; Srik – стали внутренними
А при внесении ej число внешних ребер станет
d*(еj)= zi-Srjk+(r(ej)- Srjk)=d(еj)+ zi-Srjk
(4.6)
Учитывая выражение (4.4), из (4.6) следует
Вычитая из (4.5) выражение (4.6) и учитывая (4.4), получаем:
т.е. при внесении вершины ei число внешних соединительных ребер уменьшилось.
ПРИМЕР
Дан сформированный кусок графа G Gi (рис. 4.1). Рассматриваются для внесения в него вершины еi и ej, расположение которых приведено на рис. 4.2. Число внешних соединительных ребер куска Gi до внесения в него вершин еi и ej zi=6.
4.При внесении ei число внешних соединительных ребер будет равным d*(еi)= zi-Srik+(r(ei)- Srik)=6-4+7-4=5;
5.При внесении ej число внешних соединительных ребер будет равным d*(еj)= zi-Srjk+(r(ej)- Srjk)=6-2+5-2=7, т.е. при внесении еi число внешних соединительных ребер меньше, чем при внесении ej, а по условию r(ei)> r(ej) что и требовалось показать.
Пример алгоритма 2
Дан граф G=(E,U), изображенный на рис. 4.3, матрица смежности которого имеет вид:
R =
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e11
e12
e1
r(e1)=7
e2
r(e2)=8
e3
r(e3)=8
e4
r(e4)=8
e5
r(e5)=8
e6
r(e6)=5
e7
r(e7)=11
e8
r(e8)=4
e9
r(e9)=3
e10
r(e10)=11
e11
r(e11)=5
e12
r(e12)=8
Граф G необходимо разбить на три куска по четыре вершины в каждом. Множество запрещенных вершин Q={e1,e5,e10}.
Построим первый кусок G1.
Выбираем вершину e1 (можно e5 или e10) и записываем E1={e1}. Далее рассматриваем множество. Гe1={e1,e2,e3,e9} (вершин, смежных с e1). Вершина e10 в Гe1 не включается т.к. она является запрещенной.
По формуле (4.1) определяем относительные веса вершин из Гe1, кроме вершины e1, уже вошедшей в E1:
d(е2) = r(e2) - Sr2k=8 – 1 = 7 (k=1,|E1|)
d(е3) = r(e3) - Sr3k=8 – 4 = 4 (k=1,|E1|)
d(е9) = r(e9) - Sr9k=3 – 1 = 2 (k=1,|E1|)
Включаем вершину е9, имеющую min d(е9), в кусок G1=(E1,U), и получаем E1={e1,e9}.
Строим теперь множество вершин, смежных множеству вершин E1. Это множество Гe1ÈГe9={e1,e2,e3,e9}. Определяем относительные веса e3 и e2.
d(е3) = r(e3) - Sr3k=8 – (4+1) = 3 (k=1, 2=|E1|)
(где Sr3k, k=1,2 - число ребер, соединяющих вершину e3 с вершинами подмножества E1={e1,e9}).
d(е2) = r(e2) - Sr2k=8-(1+1) = 6 (k=1, 2=|E1|)
В кусок G1 помещаем вершину e3 т.к. она имеет наименьший относительный вес, тогда E1={e1e9,e3}.
Составляем множество Гe1ÈГe9ÈГe3= (e1,e2,e3,e9,е6) (вершин, смежных с e1,e3,e9) и находим
d(е2) = r(e2) - Sr2k=8-(1+1+0) = 6 (k=1, 3=|E1|)
(где Sr3k, k=1,3 - число ребер, соединяющих вершину e2 с вершинами подмножества E1={e1e9,e3}).
d(е6) = r(e6) - Sr6k=5-(0+0+1) = 4 (k=1, 3=|E1|)
(где Sr3k, k=1,3 - число ребер, соединяющих вершину e6 с вершинами подмножества E1={e1e9,e3}).
Включив вершину е6 в кусок G1, получим
E1={e1e9,e3,е6}.
Таким образом, кусок G1 сформирован. Удаляем его из графа G и получаем новый граф G’= G\G1. Его матрица получится, если из R вычеркнуть строки и столбцы, соответствующие e1e9,e3,е6:
R =
e2
e4
e5
e7
e8
e10
e11
e12
e2
r(e2)=5
e4
r(e4)=8
e5
r(e5)=8
e7
r(e7)=11
e8
r(e8)=4
e10
r(e10)=8
e11
r(e11)=5
e12
r(e12)=5
Сформируем теперь кусок G2. Берем запрещенную вершину е5 (можно и е10), тогда E2={e5}. Строим множество вершин, смежных e5: Гe5={e5,e2,e4,e7,e8}.
Рис. 4.1
Рис. 4.2
