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

Разрезание – разбиение исходной схемы на части (микросборки, ТЭЗ и др.), типы которых заданы, либо должны быть определены с минимального числа связей между ними.

Исходная информация задается принципиальной электрической схемой, полученной в результате или решения задачи покрытия, или макетирования, или моделирования.

Схема представляется графом G(X, U), где Х – отражает множество конструктивных модулей, U – множество связей. Необходимо разрезать исходный граф на куски G₁(X₁, U₁), G₂(X₂, U₂), … G_n(X_n, U_n), так, чтобы число ребер соединяющих вершин разных кусков, было минимальным, т.е. минимизировать

при ограничениях, накладываемых на:

1) число кусков разрезания;

2) число вершин в каждом из кусков (определяется допустимым числом посадочных мест, в которые можно разместить конструктивные модули на печатной плате ТЭЗ, пластине БИС, подложке ГИС и т.д.);

3) максимальное число внешних связей конструктива, соответствующего куску графа;

4) а также на конструктивную совместимость отдельных вершин в одном подграфе (электромагнитную совместимость отдельных элементов схемы).

В САПР применяются как последовательные, так и итерационные алгоритмы разрезания.

Рассмотрим один из представленных описаний схемы графов алгоритмов.

Задан граф G(X, U), который необходимо разбить на п кусков G_k(X_k, U_k) с заданным числом вершин N_k в кадом из кусков, т.е. k=1, 2, …n; ∑ N_k=|X|.

Основные этапы.

В графе G(X, U), строим матрицу смежности А, находим вершину X_i ϵ X c минимальной степенью связей min ρ (X_i), i=1, 2, …|X|. Если таких вершин несколько, предпочтение отдается вершине с максимальным числом кратных ребер

В G₁(X₁, U₁) включается найденная вершина Х_i и все вершины смежные ей.

Если окажется |X₁|> N₁ (N₁ – заданное число вершин в первом куске), то удаляются лишние вершины, связанные с оставшимися в G₁ вершинами меньшим числом ребер. Если |X₁|< N₁, то из X \ X₁(исключение) выбираются вершина Х_j смежная с X₁ и обеспечивающая минимальное приращение числа связей ∆ S вершин из X₁ с еще не распределенными вариантами. Эта вершина включается в G₁ если не происходит нарушения ограничения по числу внешних связей.

Процесс подсоединения очередных смежных вершин в G₁ продолжается до тех пор, пока выполняются ограничения на число вершин в G₁ (т.е. N_k) и на число внешних связей.

Образованный кусок G₁(X₁, U₁) исключаем из исходного графа с его внешними связями. Из оставшегося подграфа G^*(X^*, U^*) = G(X, U) \ G₁(X₁, U₁) выбирается вершина с наименьшей локальной степенью, помещается в G₂ и процесс повторяется для образования второго, третьего и т.д. кусков, т.е. пока граф G не будет разбит на п кусков.

Рассмотрим описанный алгоритм на конкретном примере.

Задан исходный граф. Построим матрицу смежности А

Необходимо разрезать граф G на три куска G₁, G₂, G₃, содержащих соответственно N₁=3, N₂=2, N₃=2 вершины.

Выбираем вершину с минимальной локальной степенью – Х₂(ρ (Х₂)=4) и получаем множество, удаляем лишнюю вершину Х₄, имеющую меньшее число связей с другими вершинами в Х₁. Получаем G₁(X₁, U₁), Х₁ = {x₁, x₂, x₃}, удаляем G(X₁, U₁). После удаления G₁ из графа G получаем граф G^*= G \G₁, матрица смежности которого имеет вид:

Выбираем вершину Х₄ [ρ (x₄)=5] и образуем Х₂ =(x₄, x₅, x₆).

Так как |X₂|> N₂, удаляем лишние вершины Х₅ и Х₇. Следовательно, G₂ состоит из вершин Х₄ и Х₆, а G₃ из вершины Х₅ и Х₇. Тогда искомое разрезание исходного графа имеет вид: