ПРИМЕНЕНИЕ ЗАПРЕЩЕННЫХ ФИГУР В ЗАДАЧЕ РАСКРАСКИ ГРАФА ПРИ ПРОЕКТИРОВАНИИ ПЕЧАТНЫХ ПЛАТ
Проектирование конструкции печатных плат в виде плоских структур без перемычек является одной из самых сложных задач на этапе схемотехнического проектирования. Задача в такой постановке особенно актуальна микросборок и для электронных модулей контрольно-проверочной, бортовой аппаратуры, выполненных по технологии поверхностного монтажа, где, например, по причине металлического теплоотвода или керамического основания, структура соединений возможна только в одном слое. В работе рассматривается задача проектирования печатных плат в виде синтеза плоских структур электронных схем. Целью является расположение соединений на печатной плате без пересечений, что облегчает условия проведения трасс любому трассировщику современных программ проектировании. Для её решения предложено большое число различных алгоритмов, основным недостатком которых является заложенный в них принцип последовательного и фрагментарного просмотра коммутационного пространства. Сложность алгоритмов синтеза подобных структур обусловлена также необходимостью учета большого числа различных требований, связанных со спецификой их изготовления и особенностями разрабатываемого конструктивно-технологического решения. В настоящей работе предлагается выполнить проектирование печатной платы с высокой эффективностью трассировки соединений за счет решения задачи расслоения исходного графа-схемы и построения плоского графа-схемы как на стороне установки ЭРЭ, так и на обратной стороне платы - стороне пайки, исключая запрещенные фигуры по теореме Потрягина-Куратовского. Критерием является минимизация переходных отверстий, а также минимизация проводников (ребер) на одной стороне печатной платы. Задача расслоения представляет собой задачу раскраски графа в два цвета с использованием принципов характеризационного управления, решение которой базируется на теореме Кенига, определяющей запрещенную фигуру в виде циклов нечетной длины. Для проектирования печатных плат разработаны алгоритм и методика построения планарных графов и расслоения графа на две стороны печатной платы с уменьшением количества неразведенных ребер. Точное решение принимает вид полиномиальной зависимости не выше 5-й степени, позволяет получить результат за приемлемое время и повысить эффективность трассировки на 5-15 %.