122 проектирование Выделение плоского суграфа схемы электрической принципиальной. <...> Метод наискорейшего спуска Сергей КУРАПОВ lilili5050@rambler.ru Максим ДАВИДОВСКИЙ m.davidovsky@gmail.com В статье представлен алгоритм для построения рисунка плоской части графа схемы электрической принципиальной. <...> Исходной информацией для решения задачи служит множество единичных циклов графа, что позволяет свести решение к методам дискретной оптимизации. <...> Рассмотрены необходимые понятия и структуры для решения задачи построения плоского топологического рисунка графа схемы электрической принципиальной. <...> Введение Одна из основополагающих проблем проектирования плоских конструктивов — выделение плоской части графа схемы электрической принципиальной, — как правило, может быть сведена к задаче дискретной оптимизации, а именно к поиску экстремума на множестве единичных (изометрических) циклов. <...> Решение этой задачи достигается различными способами: фрагментарных структур, случайного поиска, наискорейшего спуска и другими методами дискретной оптимизации. <...> В статье будем рассматривать метод наискорейшего спуска. <...> Функционал Маклейна Предположим, что для графа G выделено множество единичных циклов графа [3]. <...> Тогда выбор базиса подпространства циклов, состоящего из единичных циклов графа и циклических фрагментов, позволяет применить теорему Маклейна для определения планарности выделенной плоской части из непланарного графа [10]. <...> На основе данной теоремы можно построить целевую функцию (называемую функционалом Маклейна) и свести задачу построения планарного суграфа к задачам дискретной оптимизации [11]: найти базис подпространства циклов с нулевым значением функционала Маклейна, состоящий из единичных циклов графа. <...> Выделенный базис с нулевым значением функционала Маклейна индуцирует вращение вершин графа, и это полностью характеризует плоский топологический рисунок графа. <...> Значение функционала Маклейна для накрывающего <...>