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

- 72 - мальный охватывающий прямоугольник П i . Тогда два комплекса v i и v j называ- ют перекрывающимися, если П i ∩ П j ≠∅ (рис. 41). Строим граф перекрытий Z =( V , U ), вершины v ∈ V соответствуют ком- плексам, а ребра u ∈ U – перекрытиям между ними (рис.42). Степенью перекрытия системы комплексов { v i } называется хроматиче- ское число γ ( Z ) графа Z =( V , U ). Если γ ( Z )=1, то все связывающие деревья для системы комплексов { v i } могут быть расположены в одном слое. В общем случае хроматическое число γ ( Z ) будет являться верхней оценкой числа слоев при условии, что каждое свя- зывающее дерево полностью размещается в одном слое. Таким образом правильная раскраска вершин графа Z = ( V , U ), γ ( Z ) цве- тами будет соответствовать разбиению системы комплексов {v i } на γ ( Z ) групп { v i 1 },{ v i 2 },…,{ v i l }, каждая из которых содержит неперекрывающиеся комплек- сы. Для нашего примера γ ( Z )=2, т.е. схема могла быть реализована в двух сло- ях. Расслоение после трассировки Для выполнения этого этапа нужно иметь совмещенный топологический эскиз схемы, т.е. трассировку на одной плоскости. Затем при расслоении лик- видируются возникшие пересечения с учетом конструкции многослойных схем. Самая простая постановка задачи, когда пересечения ликвидируют таким обра- зом, чтобы можно было реализовать соединения без пересечений в двух слоях. При этом предполагается, что для каждой цепи построено минимальное дерево и связь между слоями возможна лишь в точках, соответствующих выводам элементов. Рассмотрим систему проводников на плоскости (рис.43, а ) и составим ее граф пересечений Z =( Х , U ), вершины которого х ∈ Х соответствуют проводни- кам, ребра u ∈ U – пересечениям этих проводников (рис. 43, б ). Найдем двухцветную раскраску графа Z , при которой суммарное коли- чество ребер, соединяющих одноцветные вершины, будет минимально. Это эк-