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