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

Первая часить статьи.

Введение

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

Рис. 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 >.

Обод плоской части графа:

с₀ = с₂ ⊕ c₁₆ ⊕ c₄₆ ⊕ c₅₀ ⊕ c₅₈ ⊕ c₆₁ ⊕ c₇₈ ⊕ c₈₆ ⊕ c₉₂ ⊕ c₁₀₇ ⊕ c₁₀₈ ⊕  c₁₁₇ ⊕ c₁₃₂ ⊕ c₁₃₃ ⊕ c₁₃₄ ⊕ c₁₃₅ ⊕ c₁₃₆ ⊕ c₁₃₇ = {u₄,u₅,u₇,u₇₈,u₇₉,u₈₀,u₈₂} → < x₄₁,x₄₀,x₃₉,x₄₃,x₃,x₂,x₄₅ >.

Плоская часть графа представлена на рис. 2.

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

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

Выделение дерева в клике цепи

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

Рис. 3. Гиперребро

Рис. 4. Вершина графа Кенига для гиперребра

Рис. 5. Различные деревья для гиперребра

Составим список соответствия цепей и полюсов циклических фрагментов:

цепь 42: полюса {x6,x8,x21,x28,x34,x35};
цепь 43: полюса {x3,x14,x27,x32,x39};
цепь 44: полюса {x12,x25,x40};
цепь 45: полюса {x2,x9,x16,x41};
цепь 46: полюса {x4,x10,x15,x22,x29};
цепь 47: полюса {x7,x20,x36};
цепь 48: полюса {x19,x23,x30,x38};
цепь 49: полюса {x11,x18,x24};
цепь 50: полюса {x1,x17,x26,x31};
цепь 51: полюса {x5,x13,x33,x37}.

Выделим соединенные полюса:

цепь 42: полюса {x6,x21};
цепь 43: полюса {x3,x14,x27,x32,x39};
цепь 44: Ø
цепь 45: полюса {x2,x9,x16,x41};
цепь 46: полюса {x4,x10,x15,x29};
цепь 47: полюса {x7,x20,x36};
цепь 48: полюса {x19,x23,x38};
цепь 49: полюса {x18,x24};
цепь 50: полюса {x17,x26};
цепь 51: полюса {x13,x33}.

Соединения могут быть определены как ветви дерева графа для клики электрической цепи алгоритмом Прима [4, 7]. Построим клику, характеризующую гиперребро, и выделим минимальное дерево для каждой цепи [7, 9]. На рис. 6–7 представлены выбранные ветви дерева.

Рис. 6. Дерево для цепи 42

Рис. 7. Дерево для цепи 43

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

для цепи 42: ребра (x6,x35), (x28,x35), (x34,x28), (х8,х21);
для цепи 43: Ø;
для цепи 44: ребра (x12,x25), (x40,x25);
для цепи 45: ребра (x2,x16);
для цепи 46: ребра (x22,x15);
для цепи 47: Ø;
для цепи 48: ребра (x23,x30);
для цепи 49: ребра (x11,x18);
для цепи 50: ребра (x1,x17),(x31,x26);
для цепи 51: ребра (x5,х37),(х5,x13).

Проведение соединений, удаленных в процессе планаризации

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

Алгоритмом поиска в ширину будем находить минимальные пути на графе циклов (рис. 8–9).

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

Рис. 9. Выбор минимального пути для соединения (x28,x35)

Результаты проведения соединений представлены на рис. 10–13.

Рис. 10. Проведение соединения (x6,x35)

Рис. 11. Проведение соединения (x28,x35)

Рис. 12. Проведение соединения (x28,x34)

Рис. 13. Проведение соединения (x8,x21)

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

Например, обруч образуется в результате проведения следующих соединений и может храниться в памяти ЭВМ в виде маршрута, состоящего из циклов:

соединение (х₆,х₃₅) = с₂с₈₆с₁₀₇ = < x₂₁,x₂₀,x₇,x₆ >< x₂,x₁,x₇,x₃₆,x₃₅,x₄₁ >< x₂₀,x₁₉,x₂₃,x₃₈,x₃₇,x₃₆,x₇ > = <x₂₁,x₂₀> + <x₂₀,x₇> + <x₇,x₆> + <x₆,x₂₁> + <x₂,x₁> + <x₁,x₇> + <x₇,x₃₆> + <x₃₆,x₃₅> + <x₃₅,x₄₁> + <x₄₁,x₂> +  <x₂₀,x₁₉> + <x₁₉,x₂₃> + <x₂₃,x₃₈> + <x₃₈,x₃₇> + <x₃₇,x₃₆> + <x₃₆,x₇> + <x₇,x₂₀> = <x₂₁,x₂₀> + <x₂₀,x₁₉> +  <x₁₉,x₂₃> + <x₂₃,x₃₈> + <x₃₈,x₃₇> + <x₃₇,x₃₆> + <x₃₆,x₃₅> + <x₃₅,x₄₁> + <x₄₁,x₂> + <x₂,x₁> + <x₁,x₇> + <x₇,x₆> + <x₆,x₂₁> = < x₂₁,x₂₀,x₁₉,x₂₃,x₃₈,x₃₇,x₃₆,x₃₅,x₄₁,x₂,x₁,x₇,х₆ >;

соединение (х₂₈,х₃₅) = с₈₆с₁₀₇с₅₈ = < x₂,x₁,x₇,x₃₆,x₃₅,x₄₁ >< x₂₀,x₁₉,x₂₃,x₃₈,x₃₇,x₃₆,x₇ >< x₃₉,x₃₈,x₂₃,x₂₂,x₂₈,x₂₇ > = <x₂,x₁> + <x₁,x₇> + <x₇,x₃₆> + <x₃₆,x₃₅> + <x₃₅,x₄₁> + <x₄₁,x₂> +  <x₂₀,x₁₉> + <x₁₉,x₂₃> + <x₂₃,x₃₈> + <x₃₈,x₃₇> + <x₃₇,x₃₆> + <x₃₆,x₇> + <x₇,x₂₀> + <x₃₉,x₃₈> + <x₃₈,x₂₃> + <x₂₃,x₂₂> + <x₂₂,x₂₈> + <x₂₈,x₂₇> + <x₂₇,x₃₉> = <x₂,x₁> + <x₁,x₇> + <x₇,x₂₀> + <x₂₀,x₁₉> + <x₁₉,x₂₃> + <x₂₃,x₂₂> + <x₂₂,x₂₈> + <x₂₈,x₂₇> + <x₂₇,x₃₉> + <x₃₉,x₃₈> + <x₃₈,x₃₇> + <x₃₇,x₃₆> + <x₃₆,x₃₅> + <x₃₅,x₄₁> + <x₄₁,x₂> = < x₂,x₁,x₇,x₂₀,x₁₉,x₂₃,x₂₂,x₂₈,x₂₇,x₃₉,x₃₈,x₃₇,x₃₆,x₃₅,x₄₁ >;

соединение (х₂₈,x₃₄) = c₅₈ ⊕ c₄₆ ⊕ c₉₂ = < x₃₉,x₃₈,x₂₃,x₂₂,x_x28,x₂₇ > < x₃₂,x₃₁,x₃₀,x₂₉,x₁₀,x₁₅,x₄,x₃,x₃₉,x₂₇ > < x₂₉,x₃₄,x₃₃,x₁₃,x₁₂,x₁₁,x₁₀ > = <x₃₉,x₃₈> + <x₃₈,x₂₃> + <x₂₃,x₂₂> + <x₂₂,x₂₈> + <x₂₈,x₂₇> + <x₂₇,x₃₉> + <x₃₂,x₃₁> + <x₃₁,x₃₀> + <x₃₀,x₂₉> + <x₂₉,x₁₀> + + <x₁₀,x₁₅> + <x₁₅,x₄> + <x₄,x₃> + <x₃,x₃₉> + <x₃₉,x₂₇> + <x₂₇,x₃₂> + <x₂₉,x₃₄> + <x₃₄,x₃₃> + <x₃₃,x₁₃> + <x₁₃,x₁₂> + <x₁₂,x₁₁> + <x₁₁,x₁₀> +  <x₁₀,x₂₉> = <x₃₉,x₃₈> + <x₃₈,x₂₃> + <x₂₃,x₂₂> + <x₂₂,x₂₈> + <x₂₈,x₂₇> + <x₂₇,x₃₂> + <x₃₂,x₃₁> + <x₃₁,x₃₀> + <x₃₀,x₂₉> + <x₂₉,x₃₄> + <x₃₄,x₃₃> + <x₃₃,x₁₃> + <x₁₃,x₁₂> ++ <x₁₂,x₁₁> + <x₁₁,x₁₀> + <x₁₀,x₁₅> + <x₁₅,x₄> + <x₄,x₃> + <x₃,x₃₉> = < x₃₉,x₃₈,x₂₃,x₂₂,x₂₈,x₂₇,x₃₂,x₃₁,x₃₀,x₂₉,x₃₄,x₃₃,x₁₃,x₁₂,x₁₁,x₁₀,x₁,x₄,x₃ >;

соединение (x₈,x₂₁) = c₁₆ ⊕ c₄₆ ⊕ c₇₈ ⊕ c₅₀ = < x₆,x₅,x₄,x₁₅,x₂₁ >< x₃₂,x₃₁,x₃₀,x₂₉,x₁₀,x₁₅,x₄,x₃,x₃₉,x₂₇ > < x₁₆,x₁₅,x₁₀,x₉ >< x₂₇,x₂₆,x₁₇,x₁₆,x₉,x₈,x₁₄,x₃₂ > = <x₆,x₅> + <x₅,x₄> + <x₄,x₁₅> ++ <x₁₅,x₂₁> + <x₂₁,x₆> + <x₃₂,x₃₁> + <x₃₁,x₃₀> + <x₃₀,x₂₉> + <x₂₉,x₁₀> ++ <x₁₀,x₁₅> + <x₁₅,x₄> + <x₄,x₃> + <x₃,x₃₉> + <x₃₉,x₂₇> + <x₂₇,x₃₂> ++ <x₁₆,x₁₅> + <x₁₅,x₁₀> + <x₁₀,x₉> + <x₉,x₁₆> + <x₂₇,x₂₆> + <x₂₆,x₁₇> ++ <x₁₇,x₁₆> + <x₁₆,x₉> + <x₉,x₈> + <x₈,x₁₄> + <x₁₄,x₃₂> + <x₃₂,x₂₇> == <x₆,x₅> + <x₅,x₄> + <x₄,x₃> + <x₃,x₃₉> + <x₃₉,x₂₇> + <x₂₇,x₃₂> ++ <x₃₂,x₃₁> + <x₃₁,x₃₀> + <x₃₀,x₂₉> + <x₂₉,x₁₀> + <x₁₀,x₉> + <x₉,x₈> ++ <x₈,x₁₄> + <x₁₄,x₃₂> + <x₃₂,x₂₇> + <x₂₇,x₂₆> + <x₂₆,x₁₇> + <x₁₇,x₁₆> + <x₁₆,x₁₅> + <x₁₅,x₂₁> + <x₂₁,x₆> = < x₆,x₅,x₄,x₃,x₃₉,x₂₇,x₃₂,x₃₁,x₃₀,x₂₉,x₁₀,x₉,x₈,x₁₄,x₃₂,x₂₇,x₂₆,x₁₇,x₁₆,x₁₅,x₂₁ >.

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

Данное соединение характеризуется минимальным маршрутом c₁₆ ⊕ c₄₆ ⊕ c₇₈ ⊕ c₅₀ в выбранной последовательности. В начале определяется ребро (x₄,x₁₅), как пересечение циклов c₁₆ и с₄₆. Далее следует определение ребра (x₁₀,x₁₅), как пересечения циклов c₄₆ и с₇₈. И наконец, определяется ребро (x₉,x₁₆), как пересечение циклов c₇₈ и с₅₀. Данные ребра должны быть исключены из формирования контура обруча (они выделены на рис. 14 пунктирной линией). Поскольку ребро (x₂₇,x₃₂), выделенное в результате пересечения циклов c₄₆ и с₅₀, не относится к выделенному маршруту, то ориентированные ребра <x₂₇,x₃₂> и <x₃₂,x₂₇> не могут быть исключены из процесса образования обруча.

Рис. 14. Контур обруча c16 ⊕ с46 ⊕ c78 ⊕ c50

Алгоритм проведения соединений, удаленных в процессе планаризации

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

• Шаг 0. [Инициализация.] Выделено подмножество единичных циклов, характеризующее плоскую часть графа, и произведено назначение элементов по посадочным местам с учетом их ориентации.
• Шаг 1. [Построение клик цепей.] Строим клики для каждой цепи и каждому ребру в данном подграфе ставим в соответствие вес, равный расстоянию между двумя конечными вершинами.
• Шаг 2. [Построение минимального дерева.] Алгоритмом Прима строим минимальное дерево для каждой электрической цепи. Множество деревьев опишем как D{d_s1, d_s2, …, d_sz}, где si — номер цепи 1 < i ≤ z, где z — количество цепей в принципиальной электрической схеме. Относительно выбранного дерева определяем номера полюсов соединений, удаленных в процессе планаризации.
• Шаг 3. [Построение обруча для соединения.] Строим граф циклов и алгоритмом поиска в ширину, выбирая минимальный маршрут, строим последовательность циклов для проведения соединений. На основании выделенной последовательности циклов строим обруч для каждого соединения. Множество обручей будем описывать как Q{q₁, q₂, …, q_h}, где h количество соединений, удаленных в процессе планаризации. Конец работы алгоритма.

В нашем примере обручи соединений имеют вид (см. слева).

Выводы

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

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

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