| Топологические рисунки графа |
|
 |
|
|
| Авторы |
| | Курапов С.В. |
| | Давидовский М.В. |
| Год публикации |
| | 2022 |
| DOI |
| | 10.31114/2078-7707-2022-3-32-39 |
| УДК |
| | 519.173 |
|
| Аннотация |
| | В данной работе рассматривается трудно решаемая комбинаторная задача построения топологического рисунка графа. В соответствии с предложенным в данной статье подходом решение этой задачи разбивается на несколько этапов, вводятся основные определения и ограничения предлагаемых математических моделей. Основой построения моделей служат методы дискретной оптимизации и теория вращения вершин графа. Для построения математической модели решается задача выделения плоской части графа, которая рассматривается как комбинаторная задача нахождения подмножества изометрических циклов графа. Представленный метод выделения плоской части графа основан на выделении базиса изометрических циклов графа модифицированным алгоритмом Гаусса с последующим выделением плоской части методом градиентного спуска. Рассматриваются методы построения топологического рисунка графа с минимальным числом пересечений. |
| Ключевые слова |
| | граф, топологический рисунок графа, диаграмма вращения вершин, изометрические циклы. |
| Ссылка на статью |
| | Курапов С.В., Давидовский М.В. Топологические рисунки графа // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2022. Выпуск 3. С. 32-39. doi:10.31114/2078-7707-2022-3-32-39 |
| Адрес статьи |
| | http://www.mes-conference.ru/data/year2022/pdf/D035.pdf |
