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

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

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

РАЗРЕЗАНИЕ МУЛЬТИГРАФА ПОСЛЕДОВАТЕЛЬНЫМ МЕТОДОМ

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

1) В формируемый кусок назначается начальная пара вершин, имеющая наибольшее количество кратных рёбер r(x­_i,x_j).

2) Для пополнения формируемого куска недостающими вершинами или удаления лишних вершин используется число связности [1].

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

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

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

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

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

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

Шаг 4. Проверить выполнение условия |X_i| = n_k,где n_k – количество вершин, заданное для одного из кусков требуемого разрезания.

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

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

Примечание: предпоследний кусок заданного разрезания пополняется оставшейся вершиной только в том случае, если вершина x_m или x_n имеет положительное число связности.

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

Шаг 7. Проверить выполнение условия |X_i| = n_max.

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

Шаг 8. Поверить выполнение условия n_k = n_l-1, где l – количество кусков заданного разрезания.

Если условие выполняется, то перейти на шаг 9, в противном случае – на шаг 11.

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

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

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

Шаг 12. Вывод результатов разрезания с указанием:

- состава сформированных кусков (блоков);

- количества внутренних связей;

- количества внешних связей;

- коэффициента разрезания.

Перейти на шаг 13.

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

Пример. На рис. 1 представлен граф G = (X,U), у которого |X| = 12, |U| = 28. Требуется разрезать граф G на три куска G₁,G₂ и G₃ по 4, 3 и 5 вершин соответственно.

Решение

1) Построить матрицу смежности графа G.

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

3) Отыскать в матрице смежности элемент r_ij, имеющий максимальное значение. В матрице 4.11 данному условию удовлетворяет элемент

r(x₁₁,x₁₂) = 3.

4) Назначить в формируемый кусок мультиграфа двухэлементное множество X⁽²⁾ = {x₁₁,x₁₂}.

5) Мощность данного множества |X₁⁽²⁾| = 2 <n_min = 3, заданного для наименьшего по количеству вершин куска, следовательно, данное множество необходимо пополнить ещё одной вершиной. Для этого в строках x₁₁ и x₁₂ найти элемент r_11-mr_12-nс максимальным значением (кроме элемента r(x₁₁,x₁₂)). Таких элементов пять: r(x₁₁, x₁) = 1; r(x₁₁, x₅) = 1; r(x₁₂, x₂) = 1; r(x₁₂, x₈) = 1; r(x₁₂, x₁₀) = 1.

Дополнить множествоX⁽²⁾ вершиной x₂, так как она имеет минимальное число связности α(x₂) = –1. Получим трёх элементное множество
X⁽³⁾ = {x₁₁,x₁₂, x₂}.

6) Мощность полученного множества |X₁⁽³⁾| = n_min = 3, что соответствует количеству вершин второго куска. Будем считать, что второй кусок заданного разрезания предварительно сформирован, но так как граф разрезается на неравные по количеству вершин куски, то данный результат не следует принимать как окончательный.

7) Коэффициент разрезания полученного куска Δ(G⁽³⁾) = 4/5 = 0,8.

8) Продолжить пополнение формирование множестваX₁⁽³⁾ до четырёх вершин. Для этого в строкеx₂ отыскать максимальный элемент. Таких элементов два: r(x₂,x₁₀) = 1 и r(x₂,x₁₂) = 1.

9) Вершина x₁₂ уже вошла в состав формируемого куска, следовательно, назначаем в множествоX₁⁽³⁾ вершину x₁₀. Получим: X₁⁽⁴⁾ = {x₁₁,x₁₂,x_2­,x₁₀}.

10) Мощность полученного множества |X₁⁽⁴⁾| = 4, что соответствует количеству вершин, заданному для первого куска. Как и в предыдущем случае (п. 6)), будем считать, что первый кусок заданного разрезания сформирован, но полученный результат – предварительный.

11) Коэффициент разрезания полученного куска Δ(G⁽⁴⁾) = 6/4 = 1,5.

12) Продолжить пополнение формирование множестваX₁⁽⁴⁾ до пяти вершин. Для этого в строке x₁₀отыскать максимальный элемент. Таких элементов три: r(x₁₀,x₂) = 1; r(x₁₀,x₇) = 1; r(x₁₀,x₁₂) = 1.

13) Вершины x₂ и x₁₂ уже вошли в состав формируемого куска, следовательно, назначаем в множествоX₁⁽⁴⁾ вершину x₇. Получим:

X₁⁽⁵⁾ = {x₁₁,x₁₂,x_2­,x₁₀,x₇}.

14) Коэффициент разрезания полученного куска Δ(G⁽⁵⁾) = 7/7 = 1.

15) Из трёх полученных коэффициентов разрезания максимальное значение имеет Δ(G⁽⁴⁾) = 1,5, следовательно, окончательно сформированным считаем кусок G₁ = (X₁,U₁), где X₁ = {x₂,x₁₀,x_11­,x₁₂}.

16) Удалить из матрицы смежности (1) строки и столбцы, соответствующие вершинам, назначенным во второй кусок. Получим:

17) Отыскать в матрице смежности элемент r_ij, имеющий максимальное значение. В матрице (2) таких элементов пять:

r(x₁,x₇) = 2; ρ(x₁) + ρ(x₇) = 4 + 5 = 9;

r(x₁,x₉) = 2; ρ(x₁) + ρ(x₉) = 4 + 5 = 9;

r(x₃,x₅) = 2; ρ(x₃) + ρ(x₅) = 5 + 5 = 10;

r(x₄,x₈) = 2; ρ(x₄) + ρ(x₈) = 5 + 5 = 10;

r(x₅,x₇) = 2; ρ(x₅) + ρ(x₈) = 5 + 5 = 10.

18) Множества {x₁,x₇} и {x₁,x₉} имеют наименьшую сумму локальных степеней. Назначить в формируемый кусок мультиграфа множество X₂⁽²⁾ = {x₁,x₇}, имеющее младший индекс.

19) Мощность данного множества |X₁⁽²⁾| = 2 <n_min = 3, заданного для наименьшего по количеству вершин куска, следовательно, данное множество необходимо дополнить ещё одной вершиной. Для этого в строках x₁ и x₇ найти элемент r_1m и r_7nс максимальным значением. Таких элементов три:

r(x₁,x₉) = 2; ρ(x₁) + ρ(x₉) = 4 + 5 = 9;

r(x₃,x₅) = 2; ρ(x₃) + ρ(x₅) = 5 + 5 = 10;

r(x₅,x₇) = 2. ρ(x₅) + ρ(x₈) = 5 + 5 = 10.

Дополнить множествоX₂⁽²⁾ вершиной x₉. Получим: X₂⁽³⁾ = {x₁,x₇,x₉}.

20) Предварительно сформирован второй кусок заданного разрезания. Коэффициент разрезания полученного куска Δ(G⁽³⁾) = 5/4 = 1,25.

21) Продолжить пополнение множества X₂⁽³⁾ до пяти вершин. В строке x₉ отыскать максимальный элемент r_9n. Так как вершины x₁ и x₇ уже вошли в формируемый кусок, то рассмотрим элементы:

r(x₉,x₃); ρ(x₉) + ρ(x₃) = 5 + 5 = 10;

r(x₉,x₄); ρ(x₉) + ρ(x₄) = 5 + 5 = 10;

22) Сумма локальных степеней у множеств {x₉,x₃} и {x₉,x₄} одинакова, поэтому назначаем вершинуx₃ как имеющую младший индекс. Получим:

X₂⁽⁴⁾ = {x₁,x₇,x₉,x₃}.

23) Полученное множество необходимо дополнить ещё одной вершиной. Для этого в строке x₃ отыскать максимальный элемент r_3n. Таким элементом является элемент r(x₃,x₅).

24) Назначить вершинуx₅ в формируемое множество. Получим:

X₂⁽⁵⁾ = {x₁,x₇,x₉,x₃,x₅}

25) Коэффициент разрезания полученного куска Δ(G⁽⁵⁾) = 10/7 = 1,43.

26) Окончательно сформированным считаем кусок G₃ = (X₃,U₃), где

X₃ = {x₁,x₇,x₉,x₃,x₅}

27) Вершины x₄,x₆ и x₈, не вошедшие в ранее сформированные куски, автоматически образуют второй кусок заданного разрезания: G₂ = (X₂,U₂), где X₂ = {x₄,x₆,x₈}.

28) Результат разрезания мультиграфа представлен на рис. 2. Коэффициент разрезания Δ(G) = 20/8 = 2,5. Ранее такой результат можно было получить только матричным методом разрезания мультиграфа.

Рис. 2

Литература

1. Шандриков, А.С. Математическое моделирование компоновки радиоэлектронных средств разрезанием графа последовательным методом // Академия развития творчества [Электрон. ресурс] – Режим доступа :https://www.art-talant.org/publikacii/42340-matematicheskoe-modelirovanie-komponovki-radioelektronnyh-sredstv-razrezaniem-grafa-posledovatelynym-metodom.

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

3. Методы разбиения схем РЭА на конструктивно законченные части / К.К. Морозов [и др.]; под ред. К.К. Морозова. – Москва : Сов. радио, 1978 – 136 с.

4. Шандриков, А.С.Формирование математических моделей принципиальных электрических схем радиоэлектронных средств методом // Академия развития творчества [Электрон. ресурс] – Режим доступа :https://www.art-talant.org/publikacii/42346-formirovanie-matematicheskih-modeley-principialynyh-elektricheskih-shem-radioelektronnyh-sredstv.