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

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

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

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

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

При современном уровне развития электронно-вычислительных средств эта задача может решаться в автоматизированном режиме. Для автоматизации процесса решения задачи компоновки необходимо принципиальную электрическую схему РЭС заменить некоторой адекватной математической моделью. Наиболее подходящей такой моделью является граф G = (X, U), у которого множество вершин X ассоциируется с множеством РЭК, а множество рёбер U – с множеством соединений между РЭК (цепей) в соответствии принципиальной электрической схемой[1, 2]. Разделение принципиальной электрической схемы на отдельные части моделируется разрезанием графа на требуемое количество связанных между собой подграфов с заданным количеством вершин в каждой из них.

С учётом стандартизации узлов и блоков РЭС по типоразмерным параметрам разрезание графа на подграфы часто осуществляют, не задаваясь конкретным количеством вершин n_i в каждом подграфе, ограничивая при этом только минимальное N_min и максимальное N_max допустимое количество вершин в формируемых подграфах. Одновременно стремятся к тому, чтобы каждая часть содержала приблизительно одинаковое количество вершин, а количество соединительных рёбер между подграфами (внешних связей) было минимальным [2]. Принимая во внимание эти обстоятельства, оптимально будет разрезать граф на два подграфа, но получаемое при этом количество вершин может превысить допустимое значение N_max для размещения на платах. По этой причине в процессе разрезания графа необходимо фиксировать возможные варианты и выбирать вариант с минимальным количеством соединений между сформированными подграфами.

Разработанный в процессе изучения дисциплины «Системы автоматизированного проектирования» метод разрезания графа основан на выявлении двухэлементных подмножеств вершин {x_i, x_j} графа с кратными рёбрами, то есть вершин, связанных более чем одним ребром, и последующее объединение пересекающихся подмножеств таким образом, чтобы выполнялось условие

N_min ≤ n_i ≤ N_max.                                     (1)

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

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

Шаг 1. Построить матрицу смежности и определить локальную степень каждой вершины графа. Перейти на шаг 2.

Шаг 2. Отыскать в матрице смежности максимальный элемент r(x_i, x_j), расположенный на пересечении строки x_i и столбца x_j, и соответствующие ему вершины x_i и x_j назначить в подмножество X_i вершин формируемого подграфа. Перейти на шаг 3.

Шаг 3. Проверить выполнение условия N_max = 2.

Если условие выполняется, то перейти на шаг 4.

Если выполняется условие (1), то отыскать в матрице смежности все элементы r(x_i, x_j)>1 и составить список двухэлементных подмножеств вершин с кратными рёбрамиX₁, X₂, …, X_i …, X_n, соответствующих элементам r(x_i, x_j), расположенным не пересечении i-й строки и j-го столбца. Перейти на шаг 5.

Шаг 4. Формирование подграфа на этом закончено.

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

Если сформированный подграф был предпоследним подграфом заданного разрезания, то перейти на шаг8.

Шаг 5. Выбрать из списка два пересекающихся подмножества и объединить их. Будет получено четырёхэлементное подмножество вершин. Перейти на шаг 6.

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

Если |X_i| = N_max, то перейти на шаг 4.

Если N_min ≤ |X_i| ≤ N_max,то определить коэффициент разрезания формируемого подграфа и зафиксировать его текущее значение. Перейти на шаг 7.

Шаг 7. Объединить подмножество вершин X_i формируемого подграфа с ещё одним двухэлементным подмножеством X_j из имеющегося списка. Выбирать для объединения следует то двухэлементное подмножество X_j, которое пересекается с подмножеством X_i. При X_i ∩ X_j = 0 выбирать следует подмножество X_j, вершины которого имеют максимальное количество связей с вершинами подмножества X_i.

Если в результате получилось, что |X_i| > N_max, то из подмножества X_i следует удалить одну вершину. Для удаления выбирать следует вершину x_j с максимальной связностью с подмножеством X_i.

Если в множестве X_j имеется вершина с единственной связью с вершинами множества X_i, то дополнить множество X_i нужно только этой вершиной даже в ущерб минимизации внешних связей, в противном случае такая вершина будет изолированной в одном из подграфов, то есть она не будет иметь связей с вершинами «своего» подграфа. Перейти на шаг 4.

Шаг 8. Вывод результатов разрезания. Перейти на шаг 9.

Шаг 9. Конец работы алгоритма.

Реализацию данного алгоритма можно рассмотреть на следующем примере. На рис. 1 представлен граф принципиальной электрической схемы, который необходимо разрезать на произвольное количество подграфов с минимальным количеством внешних связей. Заданы ограничения на количество вершин в подграфах: N_min = 3; N_max = 6.

Рисунок 1 – Граф принципиальной электрической схемы (условный)

Решение

1. Матрица смежности графа имеет вид:

		x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12	x13	x14	x15	x16	𝜌(xi)
	x1	0	1	1	5	1	0	0	0	0	0	0	0	0	0	0	0	8
	x2	1	0	3	0	2	0	0	0	0	0	0	0	0	0	0	0	6
	x3	1	3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	4
	x4	5	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	6
	x5	1	2	0	0	0	3	0	1	0	0	0	0	0	0	0	0	7
	x6	0	0	0	0	3	0	0	0	1	0	0	0	0	0	0	0	4
R=	x7	0	0	0	1	0	0	0	3	0	0	0	0	0	0	0	0	4
	x8	0	0	0	0	1	0	3	0	1	1	0	1	0	0	0	0	7
	x9	0	0	0	0	0	1	0	1	0	0	0	0	0	0	0	0	2
	x10	0	0	0	0	0	0	0	1	0	0	1	0	0	1	0	0	3
	x11	0	0	0	0	0	0	0	0	0	1	0	4	0	1	0	0	6
	x12	0	0	0	0	0	0	0	1	0	0	4	0	4	0	3	0	12
	x13	0	0	0	0	0	0	0	0	0	0	0	4	0	0	0	0	4
	x14	0	0	0	0	0	0	0	0	0	1	1	0	0	0	1	0	3
	x15	0	0	0	0	0	0	0	0	0	0	0	3	0	1	0	1	5
	x16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1

2. После выполнения шагов 1-3 описанного алгоритма был получен список двухэлементных подмножеств вершин с кратными рёбрами. Для удобства восприятия и изложения материала результат выполнения данного действия представлен в таблице 1. Пересекающиеся пары вершин сгруппированы в одну строку таблицы, а остальные пары вершин занимают в таблице отдельные строки.

Таблица 1 – Список подмножеств с кратными рёбрами

Номер подмножества	Пересекающиеся подмножества	Внешние связи	Количество связей
1		x1-x2 x1-x3 x1-x5 x4-x7	1 1 1 1
2		x2-x1 x3-x1 x5-x1 x5-x8 x6-x8	1 1 1 1 1
3		x7-x4	1
4		x11-x10 x11-x14 x12-x8 x15-x14 x15-x16	1 1 1 1 1

Прежде всего, следует обратить внимание на группы подмножеств №№ 2 и 4. Так как эти подмножества содержат одинаковое количество пар вершин, то начать формирование первого подграфа можно с анализа любого из этих подмножеств, но для определённости при решении задачи автоматизированным методом с использованием ЭВМ следует задать критерий выбора конкретной пары вершин. Таким критерием может стать номер подмножества. Предположим, что для выбора подмножества из нескольких подмножеств с равными оценками задан минимальный номер подмножества. Тогда рассмотрим подмножество, расположенное во второй строке таблицы и учитывая наличие двух кратных рёбер между вершинами x2 и x5подмножества {x₂,x₅} и {x₅,x₆}следует объединить. Получим: X₁ = {x₂,x₃, x₅,x₆} (рис. 2).

Рисунок 2 – Первый вариант первого подграфа

Рисунок 3 – Сформированный первый подграф

3. Мощность полученного подмножества |X₁| = 4, следовательно, можно продолжить пополнение формируемого подграфа другим подмножеством или отдельной вершиной, добиваясь минимизации внешних связей. Коэффициент разрезания полученного варианта подграфа составляет Δ(G) = 8/5.

4. Из третьего столбца таблицы 1 видно, что вершина x₁X\X₁связана с вершинами x₂X₁ и x₅X₁, поэтому пару вершин x₁и x₄ можно добавить в подмножество X₁ и в результате получим: X₁ = {x₂, x₃,  x₅, x₆, x₁, x₄}. Мощность очередного варианта полученного подмножества |X₁| = 6, а коэффициент разрезания очередного варианта подграфа составляет Δ(G) = 16/3 (рис. 3). Так как |X₁| =6 = N_max, то пополнять множество X₁ не нужно. Из двух полученных вариантов первого подграфа следует выбрать второй как имеющий большее значение коэффициента разрезания.

Рисунок 4 – Первый вариант второго формируемого подграфа

Рисунок 5 - Второй вариант второго формируемого подграфа

5. Рассмотреть группу подмножеств № 4 (табл. 1). Все пары вершин пересекающиеся, поэтому их можно объединить в подмножество вершин второго формируемого подграфа и в результате получим: X₂ = {x₁₁, x₁₂, x₁₃, x₁₅}. Мощность подмножества |X₂|=4 < N_max. Коэффициент разрезания формируемого подграфа (рис. 4): Δ(G) = 11/4.

6. Подмножество X₂ дополним вершиной x₁₄, так как с ней связаны две вершины: x₁₁X₂ и x₁₅X₂. Мощность подмножества второго варианта формируемого второго подграфа |X₂|=5<N_max, а коэффициент разрезания этого подграфа Δ(G) = 13/4 (рис. 5).

Рисунок 6 – Сформированный второй подграф

7. Подмножество X₂ можно дополнить ещё одной вершиной – x₁₀, так как эта вершина связана с двумя вершинами подмножества X₂: x₁₁, x₁₂ (см. матрицу смежности). Коэффициент разрезания формируемого подграфа при этом увеличится, но количество внешних связей останется прежним. Включение вершины x₁₀ в подмножество X₂ возможно, но в подмножестве нераспределённых вершин имеется одна вершина x₁₆, связанная только с вершиной x₁₅ и в этом случае в очередном формируемом подграфе эта вершина будет изолированной, то есть не будет иметь ни одной связи с вершинами «своего» подмножества. Обе вершины включить в подмножество X₂ нельзя из-за ограничения на максимальное количество вершин в подграфах, следовательно, в подмножество X₂ нужно включить вершину x₁₆. Так как |X₂|=6=N_max, то второй подграф считается сформированным (рис. 6).

8. Нераспределённым осталось подмножество X₃ = {x₇, x₈, x₉,x₁₀}. Мощность этого множества N_min < |X₃| = 4 < N_max. Это подмножество вершин образует третий подграф.

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

Рисунок 7 – Результат разрезания графа

Коэффициент разрезания графа Δ(G) = 35/6. Для конфигурации заданного графа, содержащего 41 ребро, только шесть рёбер являются внешними. Полученное решение поставленной задачи является оптимальным.   

Список использованных источников

1. Шандриков, А.С. Учёт конфигурации принципиальных электрических схем в процессе построения их математических моделей [Текст] / А.С. Шандриков // Современные проблемы математики и вычислительной техники : материалы VI республиканской научной конференции: Брест, 26-28 ноября 2009 г. : в 2 ч. Ч. 1 / УО «Брестский государственный технический университет. – Брест: УО «БГТУ». – 2005. С. 112-115.

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