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

Задача компоновки формулируется следующим образом. Дан мультиграф G(X,U). Требуется “разрезать” его на отдельные куски G₁(X₁, U₁), G₂(X₂, U₂),…, G_k(X_k, U_k) c числом вершин в каждой, соответственно, n₁, n₂, ..., n_k (n₁ + n₂ + ...+ n_k = n), так, чтобы число ребер, соединяющих эти куски, было минимальным, т.е. минимизировать i≠j при

 i ,j = 1, 2, …, k, где U_ij – множество ребер, соединяющих куски G_i(X_i, U_i) и G_j(X_j ,U_j).

Разрезание графа последовательным алгоритмом сводится к следующему.

В графе G(X,U) находят вершину x_iX с минимальной локальной степенью (x_i).

Если таких вершин несколько, то предпочтение отдается той вершине, которая имеет большее число кратных ребер. С этой вершины начинается построение первого куска. В первый кусок включаются вершина x_i и все вершины, смежные ей: X₁={x_i}Гx_i. Возможны три случая:

1. Число вершин в первом куске Х₁=n_1. В этом случае считаем, что подграф G₁ образован.

2. Число вершин в первом куске Х₁>n_1. В этом случае ищется вершина x_jГx_i с максимальной характеристикой  (x_j) = (x_j) – .

Вершина x_j удаляется из X₁ (X₁= X₁\{x_j}).

Характеристика  (x_j) показывает, насколько уменьшится число внешних связей куска X₁, если из него удалить вершину x_j (характеристика  (x_j) знаковая).

Повторив это конечное число раз, придем к первому случаю.

3. Число вершин в первом куске Х₁<n_1. В этом случае из X \ X₁ выбирается вершина x_jХ₁, имеющая минимальное число связей с еще не распределенными вершинами. В первый кусок включаются вершины X₁= Х₁{x_j}Гx_j. Здесь опять возможны три рассмотренных варианта.

Образованный подграф G₁ исключается из исходного графа.

Получаем граф G*(X*, U*), где X*=X \ X₁, U*= U \ U₁.

Далее формируется второй подграф G₂ и т.д.

Процесс повторяется k-1 раз.

Рассмотренный алгоритм прост, легко реализуется на ЭВМ. Также среди достоинств данной группы алгоритмов выступает высокое быстродействие их при решении задач компоновки.

Основным недостатком последовательных алгоритмов является неспособность находить глобальный минимум числа внешних связей. Наибольшая эффективность метода последовательного разбиения графа имеет место, когда число вершин графа G значительно больше числа вершин в любой части разбиения n >> n₁, n₂ ,.., n_k.

В качестве примера рассмотрим компоновку элементов схемы, представ-ленной на рис. 3.24.

Необходимо разрезать граф на три куска, причем, n₁ = n₂ = 3, n₃= 2.

Повторим матрицу соединений схемы:

1. В графе G(X,U) находим вершину x_iX с минимальной локальной степенью (x_i), это вершины x₂ и x₃. У этих вершин кратных ребер нет, поэтому в качестве начальной, выбираем любую, например, x₂.

2. В первый кусок включаем X₁={x₂}Гx₂={x₀, x₂, x₄, x₆}. Х₁ = 4 > n₁.

3. Для вершин Гx₂={x₀, x₄, x₆} определим характеристики  (x_j) = (x_j) – .

 (x₀) = 7 – 6 = 1,  (x₄) = 5 – 2 = 3,  (x₆) = 6 – 6 = 0. Максимальное уменьшение внешних связей куска Х₁ будет, если из куска удалить вершину x₄.

Х₁ = Х₁ \ {x₄}.

4. Х₁ = 3 = n₁. Первый кусок сформирован.

5. Удаляем из графа вершины X₁, Х*= X \ X₁.

6. Для оставшихся вершин матрица соединений:

7. Находим вершину x_iX* с минимальной локальной степенью (x_i), это вершины x₁, x₃ и x₇. Для второго куска выберем вершину x₁. X₂={x₁}Гx₁={x₁, x₄, x₅}.

8. Х₂ = 3 = n₂. _. Второй кусок сформирован.

9. Удаляем из графа вершины Х₂ из X* \ X₂ . Нераспределенные вершины составят третий кусок Х₃ ={x₃, x₇}.

10. Х₃ = 2 = n₃. Граф разрезан.

Результат работы алгоритма представлен на рис. 5.1.

Рисунок 5.1. Результат компоновки последовательным алгоритмом