схемотехника проектирование 81 Проверка планарности графа схемы электрической принципиальной (метод нитей) Сергей КУРАПОВ lilili5050@rambler.ru Максим ДАВИДОВСКИЙ m.davidovsky@gmail.com В работе рассматривается алгоритм проверки графа схемы электрической принципиальной на планарность с одновременным построением математических структур для описания топологического рисунка плоского графа схемы. <...> В качестве таких математических структур рассматриваются изометрические циклы и вращение вершин графа. <...> Представленный алгоритм основан на перестройке дерева графа и опорного цикла и выделении блоков обратных маршрутов. <...> Полученная в результате работы алгоритма система простых циклов графа индуцирует вращение вершин для описания топологического рисунка плоского графа с последующей его визуализацией. го проектирования плоских конструктивов и других сложных изделий электронной техники. <...> Визуализация непланарных и планарных графов — важнейшая задача при проектировании плоских конструктивов и других сложных систем. <...> Проверка планарности графа принципиальной электрической схемы является одной из первоочередных подзадач построения множества плоских частей непланарного графа. <...> Обычно для проверки графа на планарность применяется алгоритм Хопкрофта — Тарьяна [13] или сходные с ним [12]. <...> Однако эти алгоритмы не позволяют получить топологический рисунок графа. <...> С одной стороны, следует учитывать топологические свойства, такие как планарность графа, минимальное число пересечений ребер, взаимное расположение вершин и ребер, разбиение рисунка графа на плоские части, пересечение отрезков с функциональной неопределенностью и т. д. <...> С другой — на основании топологических структур геометрическими методами определяются координаты вершин и конфигурация ребер, расстояние между ними и иные метрические характеристики [1–5]. <...> Поэтому современная концепция описания рисунка графа и его визуализации должна быть построена <...>