XI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям

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

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

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

Список литературы

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