МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ КОМПОНОВКИ РАДИОЭЛЕКТРОННЫХ СРЕДСТВ ПРИ НАЛИЧИИ ТЕХНОЛОГИЧЕСКИХ ОГРАНИЧЕНИЙ ПОСЛЕДОВАТЕЛЬНЫМ МЕТОДОМ

Шандриков А.С.

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

«Витебский государственный технологический университет»

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ КОМПОНОВКИ РАДИОЭЛЕКТРОННЫХ СРЕДСТВ ПРИ НАЛИЧИИ ТЕХНОЛОГИЧЕСКИХ ОГРАНИЧЕНИЙ ПОСЛЕДОВАТЕЛЬНЫМ МЕТОДОМ

Компоновка радиоэлектронных средств (РЭС) моделируется разрезанием графа принципиальной электрической схемы на требуемое количество подграфов с заданным количеством радиоэлектронных компонентов (РЭК) в каждом из них. ГрафG = (X, U) принципиальной электрической схемы представляет собой совокупность двух множеств: X – множества РЭК и U – множество связей между РЭК в соответствии с принципиальной электрической схемой.

Компоновка РЭС не допускает формального подхода к разрезанию графа, так как в противном случае спроектированный узел РЭС может оказаться неработоспособным. По этой причине в процессе выполнения компоновки РЭС с многоуровневой конструктивной иерархией очень часто приходится учитывать различные технологические ограничения, что накладывает свой отпечаток на оптимальность результата. Технологические ограничения призваны устранить взаимное влияние РЭК друг на друга по критериям электромагнитной и тепловой совместимости. Если при разрезании графа не учитывать факторы взаимного влияния РЭК друг на друга, то может сложиться ситуация, когда, например, конденсатор и катушка колебательного окажутся в разных узлах. Очевидно, что такое РЭС работать не будет из-за затухания сигнала в проводах, соединяющих полученные в результате компоновки узлы. В некоторых случаях и по другим соображениям определённые РЭК должны находиться в разных узлах. Указанные требования представляют собой технологические ограничения, накладываемые на разрезание графа в процессе моделирования компоновки.

Технологические ограничения могут быть двух видов: на расположение множества конкретных РЭК в разных узлах и на расположение множества конкретных РЭК в одном и том же узле. При выполнении компоновки с использованием математической модели в виде графа множество вершин, располагаемых в разных подграфах, определяется как множество запрещённых вершин. Ситуация, когда некоторое множество вершин должно располагаться в одном и том же подграфе, определяется как множество совместных вершин.

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

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

1. Сформировать множество S совместных вершин. Эти вершины считаются вошедшими в формируемый подграф.

2. Определить мощность полученного множества.

Если |S| = n_k, где n_k – заданное количество вершин для формируемого подграфа, то подграф считается сформированным и его следует удалить из исходного графа.

Если |S| < n_k, то множество S следует дополнить недостающим количеством вершин. С этой целью для каждой совместной вершины x_i,x_j, …, следует построить множество, содержащее вершину x_i и все смежные ей вершины. Полученные множества X_i,X_j, …, следует объединить и проверить выполнение условия |X_i  X_j  …| = n_k. Если условие выполняется, то подграф считается сформированным и его следует удалить из исходного графа. В противном случае для формирования подграфа на данном этапе можно воспользоваться любым известным методом разрезания графа. В процессе назначения вершин в формируемый подграф следует выполнять проверку на наличие запрещённых вершин. По окончании формирования полученный подграф удаляется из исходного графа.

Описанная на данной стадии процедура повторяется для следующего множества совместных вершин

3. Сформировать множество Z запрещённых вершин.

4. Для каждой запрещённой вершины построить множество, содержащее эту вершину и все смежные ей вершины.

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

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

Применение предлагаемого метода, учитывающего возможные варианты технологических ограничений, рассмотрим на следующем примере.

На рис. 1 представлен граф G = (X, U), у которого |X| = 12, |U| = 28.

1) Разрезать граф на три подграфа по 4, 3 и 5 вершин в каждом с учётом следующих технологических ограничений:

а) вершины x₃ и x₇ должны находиться в одном подграфе;

б) вершины x₄, x₈ и x₉ – в разных подграфах.

2) Определить коэффициент разрезания.

Решение

1) Построить матрицу смежности заданного графа. Данному графу соответствует матрица смежности (1).

2) Определить локальные степени вершин. Значения локальных степеней вершин показаны в дополнительном столбце матрицы смежности.

3) Построить множество совместных вершин:

S = {x₃, x₇}

4) Построить множество запрещённых вершин:

Z = {x₄, x₈,x₉}

5) Формирование первого подграфа целесообразно начать с подграфа, содержащего совместные вершины. Для этого необходимо построить множества Гx₃ и Гx₇:

Гx₃ = {x₃, x₄,x₅, x₈,x₉}; Гx₇ = {x₇, x₁,x₅, x₉,x₁₀}

6) Объединить множества Гx₃ и Гx₇:

S₁ = Гx₃Гx₇ = {x₃, x₇, x₄, x₅, x₈, x₉, x₁, x₁₀} (2)

7) Для формирования подграфов воспользуемся методом последовательного назначения вершин. С этой целью для каждой вершины множества S₁, кроме вершин x₃ и x₇, следует определить приращение внешних связей, которое будет получено при назначении вершины x_jS₁\x₃,x₇ в формируемый подграф:

(x₄) = (x₄) – z(x₄) = 5 – 1 = 4;

(x₅) = (x₅) – z(x₅) = 6 – 4 = 2;

(x₈) = (x₈) – z(x₈) = 6 – 5 = 1;

(x₉) = (x₉) – z(x₉) = 5 – 2 = 3;

(x₁) = (x₁) – z(x₁) = 5 – 2 = 3;

(x₁₀) = (x₁₀) – z(x₁₀) = 3 – 1 = 2;

Кандидатами для назначения в формируемый подграф являются вершины x₅ и x₁₀, у которых (x₅) = (x₁₀) = 2 = min(x_i). Из этих вершин выбираем вершину x₅ как имеющую бóльшее значение локальной степени. Получим:

S₁⁽³⁾ = {x₃,x₇, x₅} (3)

8) Мощность полученного множества |S₁⁽³⁾| = 3 = n₂, следовательно, полученное множество S₁⁽³⁾ можно считать множеством вершин, образующим второй подграф, но так как в требуемом разрезании заданы подграфы и с большим количеством вершин, то необходимо продолжить формирование подграфа до получения результатов |S₁⁽⁴⁾| = 4 = n₂ и |S₁⁽⁵⁾| = 5 = n₃. С этой целью для каждой вершины множества (2), кроме вершин x₃,x₇ и x₅, определить приращения внешних связей:

(x₄) = (x₄) – z(x₄) = 5 – 1 = 4;

(x₈) = (x₈) – z(x₈) = 6 – 2 = 4;

(x₉) = (x₉) – z(x₉) = 5 – 2 = 3;

(x₁) = (x₁) – z(x₁) = 5 – 2 = 3;

(x₁₀) = (x₁₀) – z(x₁₀) = 3 – 1 = 2.

Критерию (x_i) = min(x_i) удовлетворяет вершина x₁₀, но так как в данном примере мощность множества запрещённых вершин равна количеству формируемых подграфов, то выбрать следует одну из запрещённых вершин, а именно, ту, которая удовлетворяет используемому критерию. Такой вершиной является вершина x₉. Получим:

S₁⁽⁴⁾ = {x₃,x₇, x₅,x₉} (4)

Полученное множество до значения |S₁⁽⁵⁾| = 5 = n₃ может быть дополнено либо вершиной x₁, либо вершиной x₁₀, так как все остальные вершины являются запрещенными для формируемого подграфа. Определить для указанных вершин приращения внешних связей:

(x₁) = (x₁) – z(x₁) = 5 – 4 = 1;

(x₁₀) = (x₁₀) – z(x₁₀) = 3 – 1 = 2.

Выбираем вершину x₁ и назначаем её в формируемый подграф. Получим:

S₁⁽⁵⁾ = {x₃,x₇, x₅,x₉, x₁} (5)

9) Каждое из полученных множеств (2)-(5) образует множество вершин одного из заданных подграфов графа. Для окончательного выбора сформированного подграфа следует определить коэффициент разрезания ∆(G) каждого варианта и выбрать тот, у которого полученное значение ∆(G), будет максимальным. Коэффициент разрезания определяется по формуле

∆(G) = ΣL_ii/ΣK_ij

Вычисляем:

∆(G⁽³⁾) = 4/9 = 0,44;

∆(G⁽⁴⁾) = 6/10 = 0,6;

∆(G⁽⁵⁾) = 10/6 = 1,67.

По результатам вычислений коэффициента разрезания окончательно сформированным следует третий подграф G₃, содержащий вершины множества S₁⁽⁵⁾.

10) Удалить из множества запрещённых вершин Q вершину x₉, назначенную в сформированный подграф. Получим:

Q⁽¹⁾ = {x₄, x₈,}

11) Удалить из исходного графа сформированный подграф G₃. Применительно к матрице смежности это означает удаление строк и столбцов, соответствующих вершинам, назначенным в сформированный подграф. Получим:

12) Определить локальные степени вершин. Значения локальных степеней вершин показаны в дополнительном столбце матрицы смежности.

13) В множестве Z выбрать одну из запрещённых вершин. В качестве критерия выбора зададим минимальное значение локальной степени и выбираем вершину x₄.

14) Построить множество, содержащее выбранную вершину x₄ и все смежные её вершины.

Гx₄ = {x₄, x₆}

Вершина x₈ не включена в это множество как запрещённая.

15) Построить множество, содержащее вершину x₆ и все смежные ей вершины.

Гx₆ = {x₆, x₄}

Вершина x₈ не включена в множество как запрещённая.

Множества Гx₄ и Гx₆ равны. Это означает, что множество Гx₄ может быть дополнено вершиной (вершинами), не связанной ни с вершиной x₄, ни с вершиной x₆.

16) Выбрать вершину x₂ как имеющую минимальную локальную степень и назначить её в формируемый подграф. Получим:

X₂⁽³⁾ = {x₆, x₄,x₂}

17) Мощность полученного множества соответствует количеству вершин, заданных для первого формируемого подграфа. С целью получения оптимального разрезания следует дополнить множествоX₂⁽³⁾ до значенияX₂⁽⁴⁾ = 4 = n₂. Для этого необходимо построить множество, содержащее вершину x₂ и все смежные ей вершины.

Гx₂ = {x₂, x₁₀,x₁₂}

18) Объединить множества X₂⁽³⁾ и Гx₂. Получим:

Гx₂  X₂⁽³⁾ = {x₆, x₄,x₂, x₁₀,x₁₂}

19) Для вершин x₁₀ иx₁₂ полученного множества определить приращения внешних связей:

(x₁₀) = (x₁₀) – z(x₁₀) = 2 – 1 = 1;

(x₁₂) = (x₁₂) – z(x₁₂) = 6 – 1 = 5.

По критерию минимального приращения внешних связей выбираем вершину x₁₀ и назначаем её в формируемый подграф:

X₂⁽⁴⁾ = {x₆, x₄,x₂, x₁₀}

20) Определить коэффициенты разрезания множеств X₂⁽³⁾ и X₂⁽⁴⁾. Получим:

∆(G⁽¹⁾) = 1/5 = 0,2;

∆(G⁽²⁾) = 2/5 = 0,4.

По результатам вычислений коэффициента разрезания окончательно сформированным следует третий подграф G₂, содержащий вершины множества X₂⁽³⁾.

21) Вершины x₈, x₁₁ и x₁₂, не вошедшие во второй и третий подграфы, образуют множество вершин первого подграфа заданного разрезания.

Результат разрезания графа представлен на рис. 2.

Рис. 2

Коэффициент полученного разрезания ∆(G) = 16/12 = 1,33.

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

Литература

1.Мелихов, А.Н. Применение графов для проектирования дискретных устройств. / А.Н. Мелихов, Л.С. Бернштейн,В.М. Курейчик – М. : Наука, 1974.

2. Методы разбиения схем РЭА на конструктивно законченные части / К.К. Морозов, А.Н. Мелихов, Л.С. Бернштейн и др. ; Под ред. К.К. Морозова. – М.: Сов. радио, 1978.

3. Шандриков, А.С. Последовательный метод разрезания графа с минимизацией внешних связей // Вестник Учреждения образования «Витебский государственный университет» Пятый выпуск/УО «ВГТУ». – Витебск, 2003. С. 94-100.