Исходная информация задается принципиальной электрической схемой, полученной в результате или решения задачи
покрытия, или макетирования, или
моделирования. Схема представляется ориентированным
мультиграфом 
(
,
), где
отображает множество конструктивных модулей,
— множество связей. Необходимо разрезать исходный граф на куски
(
,
),
(
,
), ....
(
,
) так, чтобы число ребер, соединяющих вершины разных кусков, было минимальным, т. е. минимизировать
при
где
— множество ребер, инцидентных кускам
(
,
) и
(
,
).
Конструктивные ограничения могут накладываться на такие величины, как число кусков разрезания, число вершин в каждом из кусков (определяется допустимым числом посадочных мест, в которые можно разместить конструктивные модули на печатной плате
ТЭЗ, пластине СБИС, подложке ГИС и т. д.), максимальное число внешних связей конструктива, соответствующего
куску графа, а также на конструктивную совместимость отдельных вершин в одном
подграфе (электромагнитную совместимость отдельных элементов схемы).
В САПР применяются как последовательные, так и итерационные алгоритмы
разрезания. Рассмотрим один из последовательных алгоритмов.
Задан граф
(
,
), который необходимо разбить на
кусков
(
,
) с заданным числом вершин
в каждом из кусков, т. е.
=1, 2,...,
;
= |
|. В графе
(
,
) находим вершину
с минимальной локальной степенью
ρ(
), i=l, 2,...,|
|. Если таких вершин несколько, предпочтение отдается вершине с максимальным числом кратных ребер. В
включаются найденная вершина
и все вершины, смежные ей. Если окажется |
|>
, то удаляются лишние вершины, связанные с оставшимися
вершинами меньшим числом ребер. Если |
|<
, то из
\
выбирается вершина
, смежная
и обеспечивающая минимальное приращение числа связей вершин из
с еще нераспределенными вершинами. Эта вершина включается в
, если не происходит нарушения ограничения по числу внешних связей.
Процесс подсоединения очередных смежных вершин в
продолжается до тех пор, пока выполняются ограничения на число вершин в
и на число внешних связей.
Образованный кусок
(
,
) исключаем из исходного графа. Из оставшегося подграфа
*(
*,
*)=
(
,
)\
(
,
) выбирается вершина с наименьшей локальной степенью, помещается в
и процесс повторяется для образования второго, третьего и т. д. кусков, т. е. пока граф
не будет разбит на
кусков.
Пример 1
Таблица 1
| |  |  |  |  |  |  |  | ρ |
| 0 | 2 | 3 | 0 | 0 | 0 | 0 | 5 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 | 4 |
| 3 | 1 | 0 | 0 | 0 | 1 | 0 | 5 |
| 0 | 1 | 0 | 0 | 1 | 4 | 0 | 6 |
| 0 | 0 | 0 | 1 | 0 | 1 | 5 | 9 |
| 0 | 0 | 1 | 4 | 1 | 0 | 1 | 7 |
| 0 | 0 | 0 | 0 | 5 | 1 | 0 | 6 |
Необходимо разрезать граф
на три куска
,
, содержащих соответственно
=3,
=2 и
=2 вершины.
Выбираем вершину
(минимальная локальная степень р(
)=4) и получаем множество
= {
,
,
,
}, так как мощность
|>
, удаляем лишнюю вершину
, имеющую меньшее число связей с другими вершинами в
. Получаем
(
,
),
={
,
,
}. После удаления
из графа
получаем, граф
* =
\
, (рис. 2), матрица смежности которого примет вид
Таблица 2
| | | | | | ρ |
| 0 | 1 | 4 | 0 | 5 |
| 1 | 0 | 1 | 5 | 7 |
| 4 | 1 | 0 | 1 | 6 |
| 0 | 5 | 1 | 0 | 6 |
Рис. 3. Результат разрезания
Выбираем вершину
[р(
)=5] и образуем
= (
,
,
,
). Так как |
|>
, удаляем лишние вершины
,
. Следовательно,
состоит из вершин
и
, a
из вершин
и
. Искомое разрезание исходного графа приведено на рис. 3.
