Исходная информация задается принципиальной электрической схемой, полученной в результате или решения задачи покрытия, или макетирования, или моделирования. Схема представляется ориентированным мультиграфом (, ), где отображает множество конструктивных модулей, — множество связей. Необходимо разрезать исходный граф на куски (, ), (, ), .... (, ) так, чтобы число ребер, соединяющих вершины разных кусков, было минимальным, т. е. минимизировать
| |, ij
при
(, ), (, ) (, )
[(, )(, ) ()= (=)];
(, ) = (, ); =1,2,...,.
где — множество ребер, инцидентных кускам (, ) и (, ).
Конструктивные ограничения могут накладываться на такие величины, как число кусков разрезания, число вершин в каждом из кусков (определяется допустимым числом посадочных мест, в которые можно разместить конструктивные модули на печатной плате ТЭЗ, пластине СБИС, подложке ГИС и т. д.), максимальное число внешних связей конструктива, соответствующего куску графа, а также на конструктивную совместимость отдельных вершин в одном подграфе (электромагнитную совместимость отдельных элементов схемы).
В САПР применяются как последовательные, так и итерационные алгоритмы разрезания. Рассмотрим один из последовательных алгоритмов.
Задан граф (, ), который необходимо разбить на кусков (, ) с заданным числом вершин в каждом из кусков, т. е. =1, 2,..., ; = ||. В графе (, ) находим вершину с минимальной локальной степенью ρ(), i=l, 2,...,||. Если таких вершин несколько, предпочтение отдается вершине с максимальным числом кратных ребер. В включаются найденная вершина и все вершины, смежные ей. Если окажется ||>, то удаляются лишние вершины, связанные с оставшимися вершинами меньшим числом ребер. Если ||<, то из \ выбирается вершина , смежная и обеспечивающая минимальное приращение числа связей вершин из с еще нераспределенными вершинами. Эта вершина включается в , если не происходит нарушения ограничения по числу внешних связей.
Процесс подсоединения очередных смежных вершин в продолжается до тех пор, пока выполняются ограничения на число вершин в и на число внешних связей.
Образованный кусок (, ) исключаем из исходного графа. Из оставшегося подграфа *(*, *)=(, )\(, ) выбирается вершина с наименьшей локальной степенью, помещается в и процесс повторяется для образования второго, третьего и т. д. кусков, т. е. пока граф не будет разбит на кусков.
Пример 1
Задан граф (рис. 1) матрицей смежности (табл. 1)
Таблица 1    
 ρ
02300005
20010004
31000105
01001406
00010159
00141017
00005106

Необходимо разрезать граф на три куска , , содержащих соответственно =3, =2 и =2 вершины.
Рис. 1.   Исходный граф
Выбираем вершину (минимальная локальная степень р()=4) и получаем множество = {, , , }, так как мощность |>, удаляем лишнюю вершину , имеющую меньшее число связей с другими вершинами в . Получаем (, ), ={,,}. После удаления из графа получаем, граф * = \ , (рис. 2), матрица смежности которого примет вид
Таблица 2    
 ρ
01405
10157
41016
05106

Рис. 2.   Граф G*
Рис. 3.   Результат разрезания
Выбираем вершину [р()=5] и образуем = (, , , ). Так как ||>, удаляем лишние вершины , . Следовательно, состоит из вершин и , a из вершин и . Искомое разрезание исходного графа приведено на рис. 3.