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

Данная работа продолжает цикл материалов на тему «Топологический рисунок графа при проектировании плоских конструктивов» [6, 7, 8]. Основное внимание в статье уделено вопросу определения пересечений соединений топологического рисунка на основе выбранной плоской части графа [5, 6, 13]. Будем рассматривать задачу определения пересечений соединений в плоском конструктиве. В качестве основы положим один из рисунков плоской части графа принципиальной электрической схемы (рис. 1 и 2) работ [6, 8].

Рис. 1. Пересечение соединений (х₁,х₁₇) и (х₆,х₃₅)

Рис. 2. Пересечение соединений (х₁,х₁₇) и (х₂₈,х₃₅)

Как было показано в [7], обручи для соединений, удаленных в процессе планаризации графа, имеют вид:

соединение (х6,х35) = с2 ⊕ c86 ⊕ c107 = < x21,х20,х19,х23,х38,х37,х36,х35,х41,х2,х1,х7,х6 >;
соединение (х28,х35) = с86 ⊕ с107 ⊕ с58 = < x2,х1,х7,х20,х19,х23,х22,х28,х27,х39,х38,х37,х36,х35,х41 >;
соединение (х28,х34) = c58 ⊕ c46 ⊕ c92 = < x39,х38,х23,х22,х28,х27,х32,х31,х30,х29,х34,х33,х13,х12,х11,х10,х15,х4,х3 >
соединение (х8,х21) = c16 ⊕ c46 ⊕ c78 ⊕ c50 = < x6,х5,х4,х3,х39,х27,х32,х31,х30,х29,х10,х9,х8,х14,х32,х27,х26,х17,х16,х15,х21 >;
соединение (х12,х25) = c117 ⊕ c50 ⊕ c61 ⊕ c92 = < x18,х17,х16,х9,х8,х14,х13,х12,х11,х10,х29,х34,х33,х32,х27,х26,х25,х24 >;
соединение (х25,х40) = c0 ⊕ c46 ⊕ c50 ⊕ c117 = < x41,х40,х39,х27,х26,х25,х24,х18,х17,х16,х9,х8,х14,х32,х31,х30,х29,х10,х15,х4,х3,х2 >;
соединение (х2,х16) = c46 ⊕ c0 ⊕ c78 = < x32,х31,х30,х29,х10,х9,х16,х15,х4,х3,х2,х41,х40,х39,х27 >;
соединение (х22,х15) = c16 ⊕ c2 ⊕ c107 ⊕ c58 = < x6,х5,х4,х15,х21,х20,х19,х23,х22,х28,х27,х39,х38,х37,х36,х7 >;
соединение (х23,х30) = c58 ⊕ c46 = < x39,х38,х23,х22,х28,х27,х32,х31,х30,х29,х10,х15,х4,х3 >;
соединение (х11,х18) = c92 ⊕ c61 ⊕ c50 ⊕ c117 = < x29,х34,х33,х32,х27,х26,х25,х24,х18,х17,х16,х9,х8,х14,х13,х12,х11,х10 >;
соединение (х1,х17) = c86 ⊕ c107 ⊕ c108 ⊕ c117 = < x2,х1,х7,х20,х19,х18,х17,х26,х25,х24,х23,х38,х37,х36,х35,х41 >;
или = c86 ⊕ c46 ⊕ c0 ⊕ c78 ⊕ c50 = < x2,х1,х7,х36,х35,х41,х40,х39,х27,х32,х31,х30,х29,х10,х9,х8,х14,х32,х27,х26,х17,х16,х15,х4,х3 >;
соединение (х26,х31) = c46 ⊕ c50 = < x32,х31,х30,х29,х10,х15,х4,х3,х39,х27,х26,х17,х16,х9,х8,х14 >;
соединение (х5,х37) = c16 ⊕ c2 ⊕ c107 = < x6,х5,х4,х15,х21,х20,х19,х23,х38,х37,х36,х7 >;
соединение (х5,х13) = c16 ⊕ c46 ⊕ c92 = <x6,х5,х4,х3,х39,х27,х32,х31,х30,х29,х34,х33,х13,х12,х11,х10,х15,х21 >.

Нахождение пересечения соединений

Рассмотрим процесс определения пересечений соединений между собой как множественное объединение обручей.

Например, соединение (х₁,х₁₇) представлено выше как обруч c₈₆ ⊕ c₁₀₇ ⊕ c₁₀₈ ⊕ c₁₁₇, а соединение (х₆,х₃₅) — как обруч с₂ ⊕ c₈₆ ⊕ c₁₀₇. Также эти соединения можно записать как множества (х₁,х₁₇) = = <c₈₆,c₁₀₇,c₁₀₈,c₁₁₇> и (х₆,х₃₅) = <c₈₆,c₁₀₇,c₂>. Определим пересечение этих множеств:

(х1,х17) ∩ (х6,х35) = <c86,c107,c108,c117> ∩ <c86,c107,c2> = {c86,c107}.

Пересечение не пусто. Следовательно, возможно пересечение соединений. Объединим общие циклы для этих двух соединений (рис. 1):

соединения (х1,х17) и (х6,х35) = c86 ⊕ c107 ⊕ c108 ⊕ c117 ⊕ c2 = < x2,х1,х7,х36,х35,х41 > ⊕

⊕ < x20,х19,х23,х38,х37,х36,х7 > ⊕ < x19,х18,х24,х23 > ⊕ < x18,х17,х26,х25,х24 > ⊕ < x21,х20,х7,х6 > =
= (x2,х1) + (x1,х7) + (x7,х36) + (x36,х35) + (x35,х41) + (x41,х2) + (x20,х19) + (x19,х23) + (x23,х38) +
+ (x38,х37) + (x37,х36) + (x36,х7) + (x7,х20) + (x19,х18) + (x18,х24) + (x24,х23) + (x23,х19) + (x18,х17) +
+ (x17,х26) + (x26,х25) + (x25,х24) + (x24,х18) + (x21,х20) + (x20,х7) + (x7,х6) + (x6,х21) =
= (x2,х1) + (x1,х7) + (x7,х6) + (x6,х21) + (x21,х20) + (x20,х19)+ (x19,х18) + (x18,х17) + (x17,х26) +
+ (x26,х25) + (x25,х24) + (x24,х23) + (x23,х38) + (x38,х37) + (x37,х36) + (x36,х35) + (x35,х41) + (x41,х2) =
= < x2,х1,х7,х6,х21,х20,х19,х18,х17,х26,х25,х24,х23,х38,х37,х36,х35,х41 >.

Будем рассматривать ориентированный внешний контур обруча < x₂,х₁,х₇,х₆,х₂₁,х₂₀,х₁₉,х₁₈,х₁₇,х₂₆,х₂₅,х₂₄,х₂₃,х₃₈,х₃₇,х₃₆,х₃₅,х₄₁ > как координатно-базисную систему согласно [9–11].

Тогда соединение (х₁,х₁₇) имеет две проекции на координатно-базисную систему (КБС):

(х1,х17)а = < x1,х7,х6,х21,х20,х19,х18,х17 >;
(х1,х17)b = < x17,х26,х25,х24,х23,х38,х37,х36,х35,х41,х2,х1 >.

Соединение (х₆,х₃₅) также имеет две проекции на координатно-базисную систему (КБС):

(х6,х35)а = < х6,х21,х20,х19,х18,х17,х26,х25,х24,х23,х38,х37,х36,х35 >;
(х6,х35)b = < х35,х41,х2,х1,х7,х6 >.

Рассмотрим пересечение проекций:

(х1,х17)а ∩ (х6,х35)а = < x1,х7,х6,х21,х20,х19,х18,х17 > ∩ < х6,х21,х20,х19,х18,х17,х26,х25,х24,х23,х38,х37,х36,х35 > = {х6,х21,х20,х19,х18,х17};
(х1,х17)а ∩ (х6,х35)b = < x1,х7,х6,х21,х20,х19,х18,х17 > ∩ < х35,х41,х2,х1,х7,х6 > = {x1,х7,х6};
(х1,х17)b ∩ (х6,х35)а = < x17,х26,х25,х24,х23,х38,х37,х36,х35,х41,х2,х1 > ∩ < х6,х21,х20,х19,х18,х17,х26,х25,х24,х23,х38,х37,х36,х35 > = {x17,х26,х25,х24,х23,х38,х37,х36,х35};
(х1,х17)b ∩ (х6,х35)b = < x17,х26,х25,х24,х23,х38,х37,х36,х35,х41,х2,х1 > ∩ < х35,х41,х2,х1,х7,х6 > = {х35,х41,х2,х1}.

Пересечение проекций есть. Следовательно, соединения пересекаются (рис. 3).

Рис. 3. Построение КБС и определение пересечения соединений (х₁,х₁₇) и (х₆,х₃₅)

Представим соединение (х₁,х₁₇) как обруч = c₈₆ ⊕ c₁₀₇ ⊕ c₁₀₈ ⊕ c₁₁₇, а соединение (х₂₈,х₃₅) как обруч = с₅₈ ⊕ c₈₆ ⊕ c₁₀₇. Это можно записать как множества (х₁,х₁₇) = <c₈₆,c₁₀₇,c₁₀₈,c₁₁₇> и (х₆,х₃₅) = <c₈₆,c₁₀₇,c₅₈>. Определим пересечение этих множеств (рис. 2):

(х1,х17) ∩ (х28,х35) = <c86,c107,c108,c117> ∩ <c86,c107,c58> = {c86,c107}.

Пересечение не пусто. Следовательно, возможно пересечение соединений. Объединим общие циклы для этих двух соединений:

соединения (х1,х17) и (х28,х35) = c86 ⊕ c107 ⊕ c108 ⊕ c117 ⊕ c58 =
= < x2,х1,х7,х36,х35,х41 > ⊕ < x20,х19,х23,х38,х37,х36,х7 > ⊕
⊕ < x19,х18,х24,х23 > ⊕ < x18,х17,х26,х25,х24 > ⊕ < x39,х38,х23,х22,х28,х27 > = (x2,х1) + (x1,х7) + (x7,х36) + (x36,х35) + (x35,х41) + (x41,х2) + (x20,х19) +
+ (x19,х23) + (x23,х38) + (x38,х37) + (x37,х36) + (x36,х7) + (x7,х20) + (x19,х18) + (x18,х24) + (x24,х23) + (x23,х19) + (x18,х17) + (x17,х26) + (x26,х25) +
+ (x25,х24) + (x24,х18) + (x39,х38) + (x38,х23) + (x23,х22) + (x22,х28) + (x28,х27) + (x27,х39) = (x2,х1) + (x1,х7) + (x7,х20) + (x20,х19)+ (x19,х18) +
+ (x18,х17) + (x17,х26) + (x26,х25) + (x25,х24) + (x24,х23) + (x23,х22) + (x22,х28) + (x28,х27) + (x27,х39) + (x39,х38) + (x38,х37) + (x37,х36) +
+ (x36,х35) + (x35,х41) + (x41,х2) = < x2,х1,х7,х20,х19,х18,х17,х26,х25,х24,х23,х22,х28,х27,х39,х38,х37,х36,х35,х41 >.

Будем рассматривать ориентированный внешний контур обруча:

< x2,х1,х7,х20,х19,х18,х17,х26,х25,х24,х23,х22,х28,х27,х39,х38,х37,х36,х35,х41 >

как координатно-базисную систему.

Тогда соединение (х₁,х₁₇) имеет две проекции на координатно-базисную систему (КБС):

(х1,х17)а = < x1,х7,х20,х19,х18,х17 >;
(х1,х17)b = < x17,х26,х25,х24,х23,х22,х28,х27,х39,х38,х37,х36,х35,х41,х2,х1 >.

Соединение (х₂₈,х₃₅) также имеет две проекции на координатно-базисную систему (КБС):

(х28,х35)а = < x28,х27,х39,х38,х37,х36,х35 >;
(х28,х35)b = < х35,х41,х2,х1,х7,х20,х19,х18,х17,х26,х25,х24,х23,х22,х28 >.

Рассмотрим пересечение проекций:

(х1,x17)а ∩ (х28,x35)а = < x1,x7,x20,x19,x18,x17 > ∩ < x28,x27,x39,x38,x37,x36,x35 > = ∅;
(х1,x17)а ∩ (х28,x35)b = < x1,x7,x20,x19,x18,x17 > ∩ < х35,x41,x2,x1,x7,x20,x19,x18,x17,x26,x25,x24,x23,x22,x28 > = {x1,x7,x20,x19,x18,x17};
(х1,x17)а ∈ (х28,x35)b;
(х1,x17)b ∩ (х28,x35)а = < x17,x26,x25,x24,x23,x22,x28,x27,x39,x38,x37,x36,x35,x41,x2,x1 > ∩ < x28,x27,x39,x38,x37,x36,x35 > = {x28,x27,x39,x38,x37,x36,x35};
(х1,x17)b ∈ (х28,x35)a;
(х1,x17)b ∩ (х28,x35)b = < x17,x26,x25,x24,x23,x22,x28,x27,x39,x38,x37,x36,x35,x41,x2,x1 > ∩ < х35,x41,x2,x1,x7,x20,x19,x18,x17,x26,x25,x24,x23,x22,x28 > = {(x17,x26,x25,x24,x23,x22,x28) & (х35,x41,x2,x1)}.

Таким образом, проекции либо не пересекаются, либо одна проекция включается в другую, либо разбиваются на составляющие. Наличие такого поведения проекций говорит об их непересечении. Следовательно, соединения не пересекаются (рис. 4).

Рис. 4. Построение КБС и определение пересечения соединений (х₁,х₁₇) и (х₂₈,х₃₅)

Представим соединение (х₁,х₁₇) как c₈₆ ⊕ ⊕ c₁₀₇ ⊕ c₁₀₈ ⊕ c₁₁₇, а соединение (х₂₈,х₃₄) как с₅₈ ⊕ c₄₆ ⊕ c₉₂. Это можно записать как множества (х₁,х₁₇) = <c₈₆,c₁₀₇,c₁₀₈,c₁₁₇> и (х₂₈,х₃₄)  = <c₄₆,c₉₂,c₅₈>. Определим пересечение этих множеств:

(х1,х17) ∩ (х28,х34) = <c86,c107,c108,c117> ∩ <c46,c98,c58> = ∅.

Так как пересечение единичных циклов пусто, то соединения не пересекаются (рис. 5).

Рис. 5. Пересечение соединений (х₁,х₁₇) и (х₂₈,х₃₄)

Представим соединение (х₁,х₁₇) как c₈₆ ⊕⊕ c₁₀₇ ⊕ c₁₀₈ ⊕ c₁₁₇, а соединение (х₈,х₂₁) как с₁₆ ⊕ c₄₆ ⊕ c₇₈ ⊕ с₅₀. Это можно записать как множества (х₁,х₁₇) = <c₈₆,c₁₀₇,c₁₀₈,c₁₁₇> и (х₈,х₂₁) = <с₁₆,c₄₆,c₇₈,c₅₀>. Определим пересечение этих множеств:

(х1,х17) ∩ (х8,х21) = <c86,c107,c108,c117> ∩ <с16,c46,c78,c50> = ∅.

Поскольку пересечение единичных цик-лов пусто, то соединения не пересекаются (рис. 6).

Рис. 6. Пересечение соединений (х₁,х₁₇) и (х₈,х₂₁)

В результате определим множество пар пересечений соединений:

пересечение соединения (х6,х35) с соединением (х28,х35) = ∅;
пересечение соединения (х6,х35) с соединением (х28,х34) = ∅;
пересечение соединения (х6,х35) с соединением (х8,х21) = ∅;
пересечение соединения (х6,х35) с соединением (х12,х25) = ∅;
……………………………………………………………………
пересечение соединения (х11,х18) с соединением (х5,х13) ≠ ∅;
пересечение соединения (х1,х17) с соединением (х26,х31) = ∅;
пересечение соединения (х1,х17) с соединением (х5,х37) ≠ ∅;
пересечение соединения (х1,х17) с соединением (х5,х13) = ∅;
пересечение соединения (х26,х31) с соединением (х5,х37) = ∅;
пересечение соединения (х26,х31) с соединением (х5,х13) = ∅;
пересечение соединения (х5,х37) с соединением (х5,х13) = ∅.

Построение графа пересечений

Поставим в соответствие соединениям вершины графа пересечений. Определив попарное пересечение соединений, построим граф пересечений. Будем рассматривать пересечение как существование ребра между вершинами, если соединения пересекаются. Выделим независимые подмножества вершин графа и известными алгоритмами (например, [14]) раскрасим вершины (рис. 7). Тем самым раскрасим удаленные в процессе планаризации соединения. Так, алгоритм раскраски вершин графа пересечений произвел раскраску вершин графа пересечений в три цвета: зеленый (пунктирные отрезки) — 2‑й слой, красный (точечные отрезки) — 3‑й слой и фиолетовый (штрихпунктирные отрезки) — 4‑й слой (рис. 8). Напомним, что 1‑й слой — это выделенная плоская часть графа.

Рис. 7. Раскраска соединений

Рис. 8. Расположение и раскраска соединений

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

Так как проведение соединений является комбинаторной задачей [12], то естественно, что другой выбор деревьев для клик, характеризующих гиберребра, произведет другое расположение соединений и другую раскраску (рис. 9).

Рис. 9. Пример другого расположения соединений и его раскраска

Например, выбранные ветви дерева для другого рисунка соединений:

для цепи 42: ребра (x6,х35), (x28,х35), (x34,х28), (х8,х21);
для цепи 43: ∅;
для цепи 44: ребра (x12,х25), (x40,х25);
для цепи 45: ребра (x2,х16);
для цепи 46: ребра (x22,х15);
для цепи 47: ∅;
для цепи 48: ребра (x38,х30);
для цепи 49: ребра (x11,х18);
для цепи 50: ребра (x1,х17), (x31,х17);
для цепи 51: ребра (x5,х37), (х5,х13).

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

Опишем алгоритм определения пересечений соединений, удаленных при планаризации.

Шаг 0. Инициализация

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

Шаг 1. Определение пересечения двух соединений

Для каждой пары соединений строится КБС как объединение единичных циклов и определяется их пересечение. Множество пересечений опишем как PS{ps₁, ps₂, …, ps_z}, где ps_i — номер пары соединений (1 < i ≤ z), z — количество пар соединений.

Шаг 2. Построение графа пересечений соединений

Строим граф пересечений соединений. Известными алгоритмами производим раскраску соединений. Исходя из раскраски определяем количество слоев. Множество слоев будем описывать как SL{sl₁, sl₂, …, sl_zl}, где zl — количество слоев для выбранной плоской части графа и выбранного множества деревьев цепей.

Шаг 3. Построение топологического рисунка проведения соединений для заданного слоя

Строим топологический рисунок для каждого слоя относительно выбранной плоской части графа. Конец работы алгоритма.

Выводы

В данной работе представлен алгоритм определения пересечений соединений, удаленных в процессе планаризации. Завершением работы алгоритма является получение расслоения соединений и построение рисунка графа каждого слоя (рис. 10–12).

Рис. 10. Соединения 2-го слоя

Рис. 11. Соединения 3-го слоя

Рис. 12. Соединения 4-го слоя