Два подхода к проведению соединений в плоских конструктивах

№ 7’2015
PDF версия
В данной статье предлагается метод проведения соединений в плоских конструктивах, основанный на понятии топологического рисунка графа. На основе данного метода возможно построение многовариантных систем автоматизированного проектирования радиоэлектронной аппаратуры (РЭА).

Введение

Будем называть плоским конструктивом техническое устройство (конструкцию), в котором непересекающиеся соединения между его элементами и сами элементы расположены в параллельных (эквидистантных) плоскостях. Это могут быть печатные платы, интегральные микросхемы, БИС, СБИС и т. д.

В методах построения систем автоматизированного проектирования наметилось два подхода к характеру проведения соединений в плоских конструктивах.

Первый подход основан на традиционной методике, когда все геометрическое поле плоского конструктива разбивается на части (макродискреты) и затем осуществляется построение рисунка графа волновым алгоритмом Ли или его модификациями. Причем завуалированный рисунок графа строится случайным и, как правило, далеко не оптимальным образом по отношению к ручным методам проектирования. Данный подход развивается уже много лет, на его базе создано множество систем автоматизированного проектирования плоских конструктивов: PCAD, OrCAD, Specctra, Topor и другие системы [1, 7].

Однако существует и другой подход к проведению соединений. В нем в качестве клеток (макродискретов) используются единичные циклы плоской части графа, которые порождаются вращением вершин графа, то есть топологическим рисунком его плоской части [4, 5]. Вначале математическими методами создается топологический рисунок графа с определением числа пересекающихся ребер алгебраическими методами без конкретной геометрической прорисовки на плоскости. Затем на основании топологического рисунка в виде теоретико-множественного представления строится геометрическое изображение рисунка с учетом специфики области применения.

Это представление о процессе проектирования соединений позволяет связать в единое целое методы проведения соединений и размещение корпусов элементов — таким образом удается обеспечить решение многовариантной задачи данного процесса.

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

Решение данного этапа можно разбить на ряд задач:

  • построение топологического рисунка плоской части графа;
  • размещение элементов по посадочным местам;
  • построение топометрических линий;
  • определение пересечений топометрических линий;
  • проведение соединений для плоской части графа.

Для того чтобы показать сущность такого подхода, рассмотрим этап построения соединений для плоской части графа принципиальной электрической схемы, представленной на рис. 1. Здесь элементы представлены циклическими фрагментами с заданным порядком расположения контактов, а электрические цепи — вершинами графа Кенига.

Представление принципиальной электрической схемы в виде графа Кенига с циклическими фрагментами

Рис. 1. Представление принципиальной электрической схемы в виде графа Кенига с циклическими фрагментами

 

Задача выделения плоской части графа

Нам понадобятся следующие определения.

Определение 1. Несепарабельным графом G будем называть связный неориентированный граф без петель и кратных ребер, без мостов и точек сочленения, без вершин с локальной степенью, равной двум и единице.

Граф G = (X,U;P), как правило, задается множеством вершин Х, множеством ребер U и трехместным предикатом Р в виде матрицы смежностей или матрицы инциденций [9]. Необходимым понятием для топологического описания плоского рисунка графа G является понятие о вращении вершин графа, введенное Г. Рингелем [8].

Определение 2. Единичным циклом в графе будем называть суграф в виде простого цикла, если между двумя любыми его несмежными вершинами в графе не существует маршрутов меньшей длины, чем маршруты, принадлежащие данному циклу.

Математическая модель описания топологического рисунка графа в виде вращения его вершин и индуцированного этим вращением подмножества единичных циклов Cτ позволяет решать задачу определения плоской части графа.

Метод определения плоской части графа сводит задачу к отысканию минимума некоторого функционала на множестве базисов подпространства квазициклов (единичных циклов). Определим следующий функционал на векторе циклов по ребру Vu и впредь будем его называть функционалом Маклейна:

Формула

где Si — количество единичных циклов, проходящих по i‑му ребру графа.

Функционал F(С) принимает целое неотрицательное значение. Наличие базиса единичных циклов, соответствующего минимальному значению функционала Маклейна, определяет плоскую часть графа. Поэтому часть графа будем считать планарной тогда и только тогда, когда существует базис единичных циклов, для которого значение функционала Маклейна равно нулю [5].

Поиск минимального значения функционала Маклейна, таким образом, является частным случаем решения следующей задачи дискретной оптимизации: найти минимум F(С) на множестве матриц единичных циклов Cτ размера km, k = v(G), и ранга ρ(G), каждая из которых покрывает все множество вершин графа.

Определение 3. Максимально плоским суграфом для данного несепарабельного графа будем называть плоский суграф, полученный путем удаления минимального количества ребер.

В случае удачного нахождения базиса линейного подпространства циклов, состоящего из единичных циклов, метод наискорейшего спуска позволяет выделить максимально плоский суграф графа. Для решения данной задачи приближенные алгоритмы имеют полиномиальные оценки, а точные алгоритмы в той или иной форме осуществляют полный перебор вариантов (рис. 2–4).

Топологический рисунок плоской части графа (вариант 1)

Рис. 2. Топологический рисунок плоской части графа (вариант 1)

Топологический рисунок плоской части графа (вариант 2)

Рис. 3.  Топологический рисунок плоской части графа (вариант 2)

Топологический рисунок плоской части графа (вариант 3)

Рис. 4. Топологический рисунок плоской части графа (вариант 3)

Поэтому при решении задачи многовариантного построения топологического рисунка графа разумно использовать метаэвристики. В качестве основы для ряда эвристических методов поиска приближенных оптимальных решений предлагается использовать фрагментарную модель [2, 3].

Граф на рис. 1 не планарен, поэтому выделяем плоскую часть графа. Для наглядности будем рассматривать только три варианта плоского рисунка графа, хотя на самом деле можно получить и большее количество вариантов.

Выделим подмножество единичных цик-лов для плоской части графа (вариант 1):

с2 = {u12,u13,u14,u40,u41,u42} → < x21,x20,x47,x7,x6,x42 >;
с16 = {u8,u9,u10,u13,u30,u31,u42} → < x6,x5,x4,x46,x15,x21,x42 >;
с46 = {u6,u7,u9,u57,u59,u60,u62,u65} → < x32,x31,x30,x29,x46,x4,x3,x43 >;
с50 = {u15,u16,u19,u28,u32,u33,u35,u52,u53,u55} → < x27,x26,x50,x17,x16,x45, x9,x8,x14,x43 >;
с58 = {u43,u44,u47,u54,u55,u76,u77,u79} → < x39,x38,x48,x23,x22,x28,x27,x43 >;
с61 = {u26,u27,u28,u64,u65,u67} → < x14,x13,x51,x33,x32,x43 >;
с78 = {u18,u19,u21,u29,u31,u33} → < x16,x15,x46,x10,x9,x45 >;
с86 = {u1,u2,u5,u14,u69,u70,u73,u82} → < x2,x1,x7,x47,x36,x35,x41,x45 >;
с92 = {u20,u21,u22,u24,u27,u58,u59,u66,u67} → < x29,x34,x33,x51,x13,x12,x11,x10,x46 >;
с107 = {u38,u39,u41,u72,u73,u74,u77} → < x20,x19,x48,x38,x37,x36,x47 >;
с108 = {u36,u37,u39,u46,u47,u49} → < x19,x18,x49,x24,x23,x48 >;
с117 = {u34,u35,u37,u48,u49,u50,u53} → < x18,x17,x50,x26,x25,x24,x49 >;
с132 = {u1,u2,u4,u6,u8,u10,u12} → < x1,x2,x3,x4,x5,x6,x7 >;
с133 = {u15,u16,u18,u20,u22,u24,u26} → < x8,x9,x10,x11,x12,x13,x14 >;
с134 = {u29,u30,u32,u34,u36,u38,u40} → < x15,x16,x17,x18,x19,x20,x21 >;
с135 = {u43,u44,u46,u48,u50,u52,u54} → < x22,x23,x24,x25,x26,x27,x28 >;
с136 = {u57,u58,u60,u62,u64,u66} → < x29,x30,x31,x32,x33,x34 >;
с137 = {u69,u70,u72,u74,u76,u78,u80} → < x35,x36,x37,x38,x39,x40,x41 >.

Обод плоской части графа (вариант 1):

с0 = с2⊕с16⊕с46⊕с50⊕с58⊕с61⊕с78⊕с86⊕с92⊕с107⊕с108⊕с117⊕⊕с132⊕с133⊕с134⊕с135⊕с136⊕с137 = {u4,u5,u7,u78,u79,u80,u82} → → < x41,x40,x39,x43,x3,x2,x45 >.

Вектор Vu для выбранного подмножества единичных циклов имеет вид:

Vu = (2,2,2,1,1,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,2,1).

Вращение вершин графа H = {ħ1, ħ2, … ħn} для выделенной плоской части представим в виде множества вращений каждой вершины графа, соответствующей упорядоченной записи смежностей вершин. Вершины обозначены соответствующими цифрами (вариант 1):

ħ1 = <2,41,7>; ħ2 = <1,45,3>; ħ3 = <2,43,4>; ħ4 = <46,5,3>; ħ5 = <4,6>; ħ6 = <5,42,7>; ħ7 = <1,6,47>; ħ8 = <9,14>; ħ9 = <8,45,10>;
ħ10 = <9,46,11>; ħ11 = <10,12>; ħ12 = <11,13>; ħ13 = <12,51,14>;
ħ14 = <13,43,8>; ħ15 = <16,21,46>; ħ16 = <15,45,17>; ħ17 = <16,50,18>;
ħ18 = <17,49,19>; ħ19 = <18,48,20>; ħ20 = <19,47,21>; ħ21 = <15,20,42>;
ħ22 = <23,28>; ħ23 = <22,48,24>; ħ24 = <23,49,25>; ħ25 = <24,26>;
ħ26 = <25,50,27>; ħ27 = <26,43,28>; ħ28 = <27,22>; ħ29 = <30,34,46>; ħ30 = <29,31>; ħ31 = <30,32>; ħ32 = <31,43,33>; ħ33 = <32,51,34>; ħ34 = <33,29>; ħ35 = <36,41>; ħ36 = <35,47,37>; ħ37 = <36,38>;
ħ38 = <37,48,39>; ħ39 = <38,43,40>; ħ40 = <39,41>; ħ41 = <40,45,35>; ħ42 = <6,21>; ħ43 = <14,32,3,39,27>; ħ44 = ∅;
ħ45 = <2,41,16,9>; ħ46 = <15,4,29,10>; ħ47 = <7,20,36>;
ħ48 = <19,23,38>; ħ49 = <18,24>; ħ50 = <17,26>; ħ51 = <13,33>.

Выделим подмножество единичных циклов для плоской части графа (вариант 2):

c38 = {u40,u41,u42,u69,u71,u73} → < x21,x20,x47,x36,x5,x42 >;
c43 = {u2,u3,u6,u7,u8,u10,u12,u52,u53,u55} → < x27,x26,x50,x1,x7,x6,x5,x4, x3,x43 >;
c48 = {u4,u5,u7,u15,u16,u19,u28} → < x3,x2,x45,x9,x8,x14,x43 >;
с58 = {u43,u44,u47,u54,u55,u76,u77,u79} → < x39,x38,x48,x23,x22,x28,x27,x43 >;
с61 = {u26,u27,u28,u64,u65,u67} → < x14,x13,x51,x33,x32,x43 >;
с78 = {u18,u19,u21,u29,u31,u33} → < x16,x15,x46,x10,x9,x45 >;
c79 = {u1,u3,u5,u32,u33,u35} → < x2,x1,x50,x17,x16,x45 >;
с92 = {u20,u21,u22,u24,u27,u58,u59,u66,u67} → < x29,x34,x33,x51,x13,x12,x11,x10,x46 >;
с107 = {u38,u39,u41,u72,u73,u74,u77} → < x20,x19,x48,x38,x37,x36,x47 >;
с108 = {u36,u37,u39,u46,u47,u49} → < x19,x18,x49,x24,x23,x48 >;
с117 = {u34,u35,u37,u48,u49,u50,u53} → < x18,x17,x50,x26,x25,x24,x49 >;
с132 = {u1,u2,u4,u6,u8,u10,u12} → < x1,x2,x3,x4,x5,x6,x7 >;
с133 = {u15,u16,u18,u20,u22,u24,u26} → < x8,x9,x10,x11,x12,x13,x14 >;
с134 = {u29,u30,u32,u34,u36,u38,u40} → < x15,x16,x17,x18,x19,x20,x21 >;
с135 = {u43,u44,u46,u48,u50,u52,u54} → < x22,x23,x24,x25,x26,x27,x28 >;
с136 = {u57,u58,u60,u62,u64,u66} → < x29,x30,x31,x32,x33,x34 >;
с137 = {u69,u70,u72,u74,u76,u78,u80} → < x35,x36,x37,x38,x39,x40,x41 >.

Обод плоской части графа (вариант 2):

с0 = с38⊕с43⊕с48⊕с58⊕с58⊕с61⊕с78⊕с79⊕с92⊕с107⊕с108⊕с117⊕с132⊕ с133⊕⊕с134⊕с135 с136⊕с137 = {u30,u31,u42,u54,u55,u56,u57,u59,u60,u62,u65} → → < x28,x27,x43,x32,x31,x30,x29,x46,x15,x21,x42 >.

Выделим подмножество единичных циклов для плоской части графа (вариант 3):

с3 = {u2,u3,u12,u13,u52,u53,u54,u56} → < x28,x27,x26,x50,x1,x7,x6,x42 >;
c15 = {u15,u17,u19,u70,u71,u82} → < x35,x41,x45,x9,x8,x42 >;
с31 = {u16,u17,u28,u57,u58,u60,u62,u65,u68} → < x8,x14,x43,x32,x31,x30,x29,x34,x42 >;
с36 = {u10,u11,u13,u69,u71,u72,u75} → < x6,x5,x51,x37,x36,x35,x42 >;
с47 = {u6,u7,u8,u11,u74,u75,u76,u79} → < x39,x38,x37,x51,x5,x4,x3,x43 >;
с61 = {u26,u27,u28,u64,u65,u67} → < x14,x13,x51,x33,x32,x43 >;
с64 = {u4,u5,u7,u78,u79,u80,u82} → < x3,x2,x45,x41,x40,x39,x43 >;
с78 = {u18,u19,u21,u29,u31,u33} → < x16,x15,x46,x10,x9,x45 >;
c79 = {u1,u3,u5,u32,u33,u35} → < x2,x1,x50,x17,x16,x45 >;
c99 = {u30,u31,u38,u39,u40,u43,u45,u47} → < x15,x21,x20,x19,x48,x23,x22,x46 >;
с108 = {u36,u37,u39,u46,u47,u49} → < x19,x18,x49,x24,x23,x48 >;
с117 = {u34,u35,u37,u48,u49,u50,u53} → < x18,x17,x50,x26,x25,x24,x49 >;
с132 = {u1,u2,u4,u6,u8,u10,u12} → < x1,x2,x3,x4,x5,x6,x7 >;
с133 = {u15,u16,u18,u20,u22,u24,u26} → < x8,x9,x10,x11,x12,x13,x14 >;
с134 = {u29,u30,u32,u34,u36,u38,u40} → < x15,x16,x17,x18,x19,x20,x21 >;
с135 = {u43,u44,u46,u48,u50,u52,u54} → < x22,x23,x24,x25,x26,x27,x28 >;
с136 = {u57,u58,u60,u62,u64,u66} → < x29,x30,x31,x32,x33,x34 >;
с137 = {u69,u70,u72,u74,u76,u78,u80} → < x35,x36,x37,x38,x39,x40,x41 >.

Обод плоской части графа (вариант 3):

с0 = с3⊕с15⊕с31⊕с36⊕с47⊕с61⊕с64⊕с78⊕с79⊕с99⊕с108⊕с117⊕с132⊕с133⊕ ⊕с134⊕с135⊕с136⊕с137 = {u20,u21,u22,u24,u27,u44,u45,u56,u66,u67,u68} → → < x28,x42,x34,x33,x51,x13,x12,x11,x10,x46,x22 >.

Выделенное множество P = (p1, p2, …, pq) топологических рисунков плоских частей графа сохраняется в памяти ЭВМ и служит основой для проведения дальнейших вычислений.

 

Задача определения элементов по посадочным местам

Выделение плоской части графа является основой для решения задачи размещения элементов по посадочным местам.

Математической моделью геометрического рисунка графа может служить силовая модель, представляющая ребра графа как пружины с заданным модулем упругости, причем вершины, принадлежащие выделенному циклу (ободу), заранее закреплены [6]. И тогда каждое ребро графа представляется вектором силы, прямо пропорциональным его длине:

Формула

где F– — вектор силы, g — модуль упругости, ī — вектор длины отрезка.

Для силовой модели сумма векторов сил при равновесии в точке должна быть равна нулю:

Формула

где p — количество сил, действующих на точку (локальная степень вершины графа).

К уравнению (3) можно добавить условие равенства нулю векторной суммы длин отрезков для любого замкнутого контура (цикла в графе):

Формула

где k — количество ребер в контуре (длина цикла в графе).

Уравнения (2–3) аналогичны первому и второму законам Кирхгофа для электрической цепи в предположении, что сила пружины F– соответствует току ветви l, а длина пружины l соответствует электрическому напряжению ветви. Если вместо модуля упругости ввести g — проводимость ветви, то, воспользовавшись данной аналогией, можно составить уравнения равновесия относительно координат оси x методом узловых потенциалов. Тем самым удается свести решение задачи к хорошо разработанным методам расчета электрических цепей:

Формула

 

где ni — количество вершин, смежных с вершиной i, ki — количество смежных вершин с вершиной i, принадлежащих ободу.

И уравнения равновесия относительно координат оси y:

Формула

Пример решения задачи назначения по посадочным местам проведем для случая плоской части графа (вариант 1).

Удалив из рисунка связи, характеризующие электрические цепи, определим координаты центра тяжести фигур, применяя известные математические модели.

Решим задачу о назначении элементов по посадочным местам известными методами линейного программирования (рис. 5).

Размещение элементов по посадочным местам

Рис. 5. Размещение элементов по посадочным местам

Решение задачи зависит от выбора обода топологического рисунка графа. В качестве обода может быть выбран любой единичный цикл плоского рисунка. В нашем случае в качестве обода выбран цикл с46.

 

Задача построения топометрических линий

Определение 4. Будем называть топометрической линией прямую линию, соединяющую два крайних контакта двух корпусов или крайний контакт корпуса и контур плоского конструктива.

На рис. 6 показаны топометрические линии, обозначенные цифрами.

Построение топометрических линий

Рис. 6. Построение топометрических линий

Топометрические линии связывают два элемента. Например, топометрическая линия 12 связывает элементы Ф1 и Ф3. Топо-метрическая линия 22 связывает элементы Ф6 и Ф4. Топометрическая линия 17 связывает элементы Ф3 и Ф4. Топометрическая линия 29 связывает элемент Ф6 с контуром плоского конструктива К0.

Топометрические линии могут быть образованы и для триангулированного пространства (рис. 7).

Топометрические линии в триангулированном пространстве

Рис. 7. Топометрические линии в триангулированном пространстве

Параметрами топометрических линий являются номер линии и номера соединяемых контактов элементов. Например, для топометрических линий, представленных на рис. 6, линия 12 может связывать контакт 7 фрагмента Ф1 и контакт 19 фрагмента Ф3 (рис. 8).

Различные ориентации элемента Ф1

Рис. 8. Различные ориентации элемента Ф1

 

Задача определения пересечений топометрических линий

Следующая задача — определение пересечений топометрических линий.

Для ее решения строится граф циклов Gc, дуальный к топологическому рисунку плоской части графа. Здесь вершины характеризуют единичные циклы графа, а ребра определяются как результат пересечения двух циклов (рис. 9, 10).

Граф циклов для топологического рисунка плоской части графа (вариант 1)

Рис. 9. Граф циклов для топологического рисунка плоской части графа (вариант 1)

Выбор минимального пути

Рис. 10. Выбор минимального пути

Находим соответствующие единичные циклы, принадлежащие Ф1 и Ф3:

с2 = {u12,u13,u14,u40,u41,u42} → < x21,x20,x47,x7,x6,x42 >;
с46 = {u6,u7,u9,u57,u59,u60,u62,u65} → < x32,x31,x30,x29,x46,x4,x3,x43 >;
с86 = {u1,u2,u5,u14,u69,u70,u73,u82} → < x2,x1,x7,x47,x36,x35,x41,x45 >;
с107 = {u38,u39,u41,u72,u73,u74,u77} → < x20,x19,x48,x38,x37,x36,x47 >;
с0 = {u4,u5,u7,u78,u79,u80,u82} → < x41,x40,x39,x43,x3,x2,x45 >.

Определяем минимальный маршрут алгоритмом поиска в ширину для выделенного множества циклов (рис. 11). Обратным проходом алгоритма определяем последовательность прохождения вершин в графе циклов.

Определение совместных единичных циклов, принадлежащих фрагментам Ф1 и Ф3

Рис. 11. Определение совместных единичных циклов, принадлежащих фрагментам Ф1 и Ф3

Определяем пересечение циклов с107 и с86:

с107 ∩ с86 = {u38,u39,u41,u72,u73,u74,u77}∩{u1,u2,u5,u14,u69,u70,u73,u82} = {u73},

Определяем пересечение циклов с86 и с0:

с107 ∩ с0 = {u1,u2,u5,u14,u69,u70,u73,u82}∩{u4,u5,u7,u78,u79,u80,u82} = {u82}.

Определяем пересечение циклов с0 и с46:

с0 ∩ с46 = {u4,u5,u7,u78,u79,u80,u82}∩{u6,u7,u9,u57,u59,u60,u62,u65} = {u7}.

Ребро u73 характеризует цепь 47, ребро u82 характеризует цепь 45, а ребро u7 характеризует цепь 43 (рис. 2).

В зависимости от ориентации элементов меняются и параметры топометрических линий. Например, запись 12(7Ф1,19Ф3) означает топометрическую линию номер 12, соединяющую контакт 7 фрагмента Ф1 и контакт 19 фрагмента Ф3 (рис. 12). Смена ориентации фрагмента Ф1 создает другие параметры топометрической линии 12 с записью 12(4Ф1,19Ф3). Данная ситуация представлена на рис. 13. Для двух элементов Ф1 и Ф6 возможно четыре способа взаимной ориентации и, как следствие, четыре рисунка соединений (рис. 12–15).

Первый вариант соединений в зависимости от ориентации расположения элементов

Рис. 12. Первый вариант соединений в зависимости от ориентации расположения элементов

Второй вариант соединений в зависимости от ориентации расположения элементов

Рис. 13. Второй вариант соединений в зависимости от ориентации расположения элементов

Третий вариант соединений в зависимости от ориентации расположения элементов

Рис. 14. Третий вариант соединений в зависимости от ориентации расположения элементов

Четвертый вариант соединений в зависимости от ориентации расположения элементов

Рис. 15. Четвертый вариант соединений в зависимости от ориентации расположения элементов

Рассмотрим вопрос пересечения топометрической линии 12 в случае ориентации фрагментов для рис. 15. Топометрическая линия 12 связывает два фрагмента Ф1 и Ф3. Фрагмент Ф1 представлен стороной, описываемой последовательностью контактов <x4, x3, x2, x1>, а фрагмент Ф3 — стороной, описываемой последовательностью <x21, x20, x19> (рис. 11).

Топометрическая линия 8 определяется контактами 1 и 21 и пересечением только двух единичных циклов с86 и с2:

с2 ∩ с86 = {u12,u13,u14,u40,u41,u42}∩{u1,u2,u5,u14,u69,u70,u73,u82} = {u14}.

Ребро u14 относится к цепи 47 (рис. 2).

Таким образом, топометрическая линия 12 соответствует последовательному расположению цепей 47, 45, 43 начиная с контакта 19 фрагмента Ф3 и заканчивая контактом 4 фрагмента Ф1.

 

Задача проведения соединений

После вычисления пересечений топометрических линий и определения номеров цепей, линии разбиваются равномерно на количество пересекающихся отрезков. После этого одноименные цепи соединяются прямыми (рис. 16).

Проведение соединений в макродискрете. Осуществив проведение соединений в каждом макродискрете, производим сшивку всех макродискретов для получения общего рисунка плоской части графа на плоскости (рис. 12–15)

Рис. 16. Проведение соединений в макродискрете. Осуществив проведение соединений в каждом макродискрете, производим сшивку всех макродискретов для получения общего рисунка плоской части графа на плоскости (рис. 12–15)

Выбрать наиболее оптимальный рисунок можно, исходя из суммарного числа пересечений топометрических линий. Для данного примера наиболее оптимальным вариантом по минимальному количеству пересечений топометрических линий является рис. 12а.

 

Алгоритм построения рисунка плоской части

Кратко опишем алгоритм построения рисунка плоской части принципиальной электрической схемы:

Шаг 1: [Выделение множества единичных циклов].

    Выделяем множество единичных циклов Cτ для графа принципиальной электрической схемы.

Шаг 2: [Выделение плоской части графа].

    Выделяем множество плоских топологических рисунков графа P, состоящих из единичных циклов. P = {p1, p2, …, pq}, p ∈ P, где q — количество плоских рисунков графа. В свою очередь p = {c1, c2, …, cmy–n+1}, с ∈ Ct, где my — количество оставшихся ребер в графе.

Шаг 3: [Размещение элементов].

    Силовым алгоритмом решаем задачу распределения элементов по посадочным местам. Ставя в соответствие каждому элементу из множества плоских топологических рисунков P элемент множества Y, характеризующий размещение элементов конструкции по посадочным местам в пространстве R2:

Формула

Шаг 4: [Проведение топометрических линий].

    Строим множество топометрических линий TR = {tr1, tr2, …, tre} в зависимости от параметров макродискрета (треугольник, прямоугольник, многоугольник и т. д.), где card(e) — количество топометрических линий.

Шаг 5: [Определение параметров топометрических линий].

    В зависимости от ориентации элементов ставим в соответствие концевым вершинам топометрических линий номера контактов.

Шаг 6: [Определение пересечений топометрических линий].

    Построив граф циклов Gc, определяем последовательность пересечения топометрических линий.

Шаг 7: [Формирование макродискретов].

    Формируем макродискреты и проводим прямые, соединяющие точки совпадающих цепей.

Шаг 8: [Сшивка макродискретов].

    Производим сшивку макродискретов и получаем рисунок соединений для выделенной плоской части принципиальной электрической схемы.

 

Выводы

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

В данной работе продемонстрирован метод организации соединений простым проведением прямых в отличие от методов, когда проведение следующего соединения напрямую зависит от предыдущего и вида дискретизации пространства R2.

Окончание статьи.

Литература
  1. Казеннов Г. Г., Щемелинин В. М. Топологическое проектирование нерегулярных БИС. М.: Высшая школа, 1990.
  2. Козин И. В., Полюга С. И. Фрагментарные модели для некоторых экстремальных задач на графах // Математичні машини і системи. Київ, 2014. № 1.
  3. Козин И. В., Полюга С. И. О свойствах фрагментарных структур // Вісник Запорізького національного університету. Збірник науковіх праць. Фізико-математичні науки. Запоріжжя. ЗНУ, 2012, № 1.
  4. Курапов С. В., Савин В. В. Векторная алгебра и рисунок графа. Запорожье, 2003.
  5. Курапов С. В., Толок А. В. Методы построения топологического рисунка графа // Автоматика и телемеханика. 2013. № 9.
  6. Курапов С. В., Чеченя В. С. Математическая модель упругой системы на основе рисунка графа // Методи розв’язування прикладних задач механіки деформівного твердого тіла. Збірник науковіх праць / Ред. кол.: А. П. Дзюба (відп. ред.) та ін. Днепропетровськ, Ліра, 2012. Вип. 13.
  7. Норенков И. П. Основы автоматизированного проектирования. М.: Изд. МГТУ им. Н. Э. Баумана, 2002.
  8. Рингель Г. Теорема о раскраске карт. М.: Мир, 1977.
  9. Свами М., Тхуласираман К. Графы, сети и алгоритмы. Пер. с англ. М.: Мир, 1984.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *