Информационные технологии проектирования электронных средств

- 73 - вивалентно выделению в Z =( Х , U ) максимального по числу ребер бихроматиче- ского подграфа. а ) б ) Рис. 43 Граф является бихроматическим, т.е. раскрашенным в два цвета, когда он не содержит циклов нечетной длины. Решение находится как решение задачи линейного программирования. Для нашего примера решение состоит в ликвидации ребра 2-3 в Z =( Х , U ), т.е. в устранении пересечений проводников 2 и 3. Тогда разложение на два слоя бу- дет иметь вид {1*,1,6,4} и {2,3,5}. Для n слоев такой подход не может быть применен, так как в настоящее время отсутствуют общие критерии выделения максимальных n -хроматических подграфов. Как правило, используют эвристические процедуры. Так при орто- гональной трассировке проводят распределение на двух слоях, причем все го- ризонтальные соединения помещают в одном слое, а вертикальные – в другом. В точках изгибов соединений размещают контактные переходы. Для миними- зации числа контактных переходов может быть предложен следующий подход. Выделим все пересекающиеся отрезки соединений (вертикальные и го- ризонтальные) и отнесем их соответственно к первому и второму слою, т.е. по- метим. При этом очевидно, что связывающие деревья, не содержащие таких от- резков, могут быть отнесены к любому из слоев без введения дополнительных переходов.