Размещено на http://www.allbest.ru/

УДК 621.3.049.73.75:001.2(024)

Разрезание мультиграфа формированием локальных максимумов

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

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

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

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

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

Предлагаемый алгоритм разрезания мультиграфа содержит следующие шаги.

Шаг 1. Построить матрицу смежности разрезаемого мультиграфа. Перейти на шаг 2.

Шаг 2. Отыскать в матрице смежности элемент r_ij, расположенный на пересечении x_i строки и x_j столбца и удовлетворяющий условию r_ij = max r_ij.

Если таких элементов несколько, то из них следует выбрать тот, у которого соответствующие ему вершины x_i и x_j имеют меньшую сумму локальных степеней. Перейти на шаг 3.

Шаг 3. Назначить выбранные вершины x_i и x_j в формируемый кусок. В результате будет получено множество X_i = {x_i, x_j}. Перейти на шаг 4.

Шаг 4. Проверить выполнение условия |X_i| = n_min или |X_i| = n_i, где n_min - количество вершин, заданное для минимального на данном этапе куска при разрезании мультиграфа на неравные по количеству вершин куски; n_i - количество вершин, заданное для каждого куска при разрезании мультиграфа на равные по количеству вершин куски.

Если выполняется условие |X_i| = n_min, то перейти на шаг 7.

Если выполняется условие |X_i| = n_i, то перейти на шаг 10.

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

Шаг 5. В строках x_i и x_j матрицы смежности отыскать элемент r_im или r_in, имеющий максимальное значение. Если таких элементов несколько, то из них следует выбрать тот, у которого соответствующие ему вершины имеют большее количество связей с вершинами множества X_i или меньшую сумму локальных степеней. Перейти на шаг 6.

Шаг 6. Назначить вершину, соответствующую выбранному элементу, в множество X_i. Перейти на шаг 4.

Шаг 7. Полученный результат следует считать предварительным. Определить и зафиксировать коэффициент разрезания сформированного куска. Перейти на шаг 8.

Шаг 8. Продолжить формирование следующего по количеству вершин куска, считая его минимальным по количеству вершин, для чего перейти на шаг 5.

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

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

Если данный кусок был предпоследним куском заданного разрезания, то перейти на шаг 11, иначе - на шаг 2.

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

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

В качестве иллюстрации на рис. 1 представлен мультиграф, содержащий 12 вершин и 36 рёбер, а на рис. 2 - результат разрезания данного мультиграфа на три куска по 3, 4. 5 вершин описанным алгоритмом. Коэффициент разрезания Д(G) = 32/4 = 8.

Рис. 1

Рис. 2

Литература

1. Шандриков, А.С. Особенности построения графа принципиальной электрической схемы, влияющие на результаты компоновки РЭС [Текст] / А.С. Шандриков // Современная радиоэлектроника: научные исследования, подготовка кадров: материалы международной научно-практической конференции : в 3 ч. Ч 1, Минск, 20-21 апреля 2006 г. / Минский государственный высший радиотехнический колледж. - Минск : МГВРК, 2006. - С. 354-358.

2. Шандриков, А.С. Оптимизация компоновки радиоэлектронных средств на стадии построения математической модели [Текст] / А.С. Шандриков // Вестник УО «Витебский государственный технологический университет». Двенадцатый выпуск. / УО «ВГТУ». - Витебск, 2007. - С. 140-146.

3. Шандриков, А.С. Минимизация межблочных соединений радиоэлектронных средств на этапе построения математических моделей принципиальных электрических схем [Текст] / А.С. Шандриков // Материалы девятой научно-методической конференции «Информатика: проблемы, методология, технологии», Воронеж, 12-13 февраля 2009 г. : в 2 т. Т. 2 / Федеральное агентство по образованию Российской Федерации, Воронежский государственный университет, НОЦ «Волновые процессы в неоднородных и нелинейных средах». - Воронеж : ВГУ, 2009. С. 919-926.

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

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

Размещено на Allbest.ru