Читать онлайн

В данной работе рассматривается труднорешаемая комбинаторная задача построения топологического рисунка графа. В соответствии с предложенным в данной статье подходом решение этой задачи разбивается на несколько этапов, вводятся основные определения и ограничения предлагаемых математических моделей. Основой построения моделей служат методы дискретной оптимизации и теория вращения вершин графа. Для построения математической модели решается задача выделения плоской части графа, которая рассматривается как комбинаторная задача нахождения подмножества изометрических циклов графа. Представленный метод выделения плоской части графа основан на выделении базиса изометрических циклов графа модифицированным алгоритмом Гаусса с последующим выделением плоской части методом градиентного спуска. Рассматриваются методы построения топологического рисунка графа с минимальным числом пересечений.

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

Предпросмотр статьи

Идентификаторы и классификаторы

УДК
519.173. Топологические и метрические задачи теории графов
Для цитирования:
КУРАПОВ С. В., ДАВИДОВСКИЙ М. В. ТОПОЛОГИЧЕСКИЕ РИСУНКИ ГРАФА // ПРОБЛЕМЫ РАЗРАБОТКИ ПЕРСПЕКТИВНЫХ МИКРО- И НАНОЭЛЕКТРОННЫХ СИСТЕМ (МЭС). 2022. № 3
Текстовый фрагмент статьи