Алгоритмы решения задачи компоновки конструктивных узлов

Часто при разбиении ставится требование получения равных по числу вершин частей графа. Кроме того, как правило, некоторые вершины графа жестко закрепляются за определенными частями. Такие вершины называются запрещенными.

Пусть задан граф G=(E, U) и подмножество запрещенных элементов QE, |Q|=q. Требуется найти такое разбиение P (G) графа G на m одинаковых кусков G1, G2,…, Gm, чтобы суммарное число соединяющих ребер было минимальным.

Рассмотрим последовательный алгоритм разбиения графа, приводящий к минимуму числа соединительных ребер за конечное число шагов при наличии ограничений.

Основная идея метода заключается в следующем. Сначала по кускам графа распределяются запрещенные вершины. Формирование первого куска начинается с вершины eеQ, которую априорно считаем входящей во множество вершин E1 первого куска G1=(E1,U1).

Составление кусков будем вести по уровням. Вершина eе в куске G1 образует первый уровень и на этом уровне E1=eе.

Для определения вершин второго уровня, т. е. второй вершины, которую необходимо поместить в G1, строится множество вершин, смежных eе.

Обозначим множество, содержащее вершину eе, смежные ей вершины, и не содержащее других запрещенных вершин через Гeе.

Введем понятие относительного веса (еi) для любой вершины еi графа G:

(еi)=(ei)-rik, k=1,m, (1).

где rik, k=1,m — число ребер, соединяющих вершину ei с вершинами сформированного подмножества E1, m=|E1|.

Из приведенного выражения (1) следует, что для получения требуемого куска из множества Гeе необходимо выбрать вершину с минимальной величиной (еi*) (чем больше связей у вершины из Гeе с вершинами из G1, тем меньше разность в (1) и тем меньше величина (еi)):

(еi*) = min (еi), eiГeе (2).

где iI=(1,2,…, t), t=|Гeе|.

Вершина еi* является вершиной второго уровня. На втором уровне E1=eе, ei*.

Далее рассматривается множество ГeеUГei*, и для каждой вершины еkГeеUГei*, определяется относительный вес по (1). Выбрав вершину еk* с минимальным весом, получим E1=eе, ei*, еk*.

Указанный процесс продолжается до тех пор, пока множество вершин E1 не будет содержать n1 вершин. Полученный кусок G1 удаляется из графа G. Последующие куски формируются аналогично.

Если при формировании куска G1 графа G несколько рассматриваемых вершин имеют одинаковый относительный вес, то в кусок G помещается вершина, имеющая большую локальную степень. Покажем это.

Пусть для вершин ei, еjE графа G=(E, U) локальные степени (ei)>(ej). В рассматриваемом случае (еi)=(еj), а по определению.

• (еi) = (ei) — rik,
• (еj) = (ej) — rjk, k=1,m,
• (ei) — rik=(ej) — rjk (3)
• (ei) -(ej) =rik — rjk

Т.к. (ei)>(ej),.

То:

rik>rjk, k=1,m (4).

Обозначим число внешних соединительных ребер куска Gi до внесения в него вершин еi и ej через zi. Тогда при внесении в кусок Gi вершины ei число внешних ребер станет:

граф соединительный минимум ребро.

*(еi)= zi-rik+((ei) — rik)= (еi)+ zi-rik (5).

новое + старое число ребер:

zi-rik:

zi — было внешних выводов в Gi;

rik — соединились с новым элементом и стали внутренними;

• (ei) — rik:
• (ei)-было у ei внешних выводов;

rik — стали внутренними, А при внесении ej число внешних ребер станет:

*(еj)= zi-rjk+((ej) — rjk)=(еj)+ zi-rjk (6).

Учитывая выражение (4), из (6) следует Вычитая из (5) выражение (6) и учитывая (4), получаем:

• *(еi) — *(еj)=((еi)+ zi-rik)-((еj)+ zi-rjk)<0 (7)
• *(еi)<*(еj)

т.е. при внесении вершины ei число внешних соединительных ребер уменьшилось.