Практическая работа №2

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

Порядок выполнения работы:

На рис. 1 представлен граф принципиальной электрической схемы сверхгенератора. Граф содержит 12 вершин и 19 рёбер, соединяющих вершины графа друг с другом.

Рис. 1. Граф принципиальной электрической схемы изделия РЭС

VT1

Cумма

R =

VT1

1) Составляем матрицу смежности графа

2) Определить локальную степень каждой вершины графа. Локальные степени вершин графа приведены в дополнительном столбце матрицы смежности R (5).

3) Сформировать первый кусок G₁ графа G. Для этого необходимо выбрать вершину с наименьшей локальной степенью. Таких вершин в графе G два: R1 и X1 у которых r(R1) = r(X1) = 2 = min. Из этих вершин следует выбрать вершину X1.

4) Построить множество G_X₁:

G_X₁={X1, C1, R4} (6)

Мощность полученного множества

|G_X₁| = 3 < n₁ = 4 (7)

5) Из (7) следует, что множество G_C₁ нужно дополнить ещё одной вершиной. С этой целью необходимо построить множество G_C₁:

G_C₁ = {C1, C2, R4, X1} (8)

6) Объединить множества G_X₁ и G_C₁:

G₁ = G_X₁ È G_C₁ = {X1, C1, C2, R4} (9)

Мощность полученного множества G₁

|G₁| = n₁ = 4 (10)

Так как мощность полученного множества G₁ равна заданному количеству вершин n₁ первого куска G₁ графа G, то первый кусок G₁= (X₁, U₁) сформирован, где X₁= {X1, C1, C2, R4}.

7) Из графа G удалить кусок G₁. В результате будет получен граф G⁽¹⁾, представленный на рис. 2.

Рис. 2. Граф, полученный после удаления первого сформированного куска

8) Построить матрицу смежности R⁽¹⁾ графа G⁽¹⁾.

	R1	R2	L1	VT1	R3	C3	C4	C5	Cумма
	R1
	R2
	L1
R⁽¹⁾ =	VT1
	R3
	C3
	C4
	C5

9) Определить локальную степень каждой вершины графа G⁽¹⁾. Локальные степени вершин графа приведены в дополнительном столбце матрицы R⁽¹⁾.

10) Сформировать второй кусок G₂ графа G. Для этого из двух вершин R1 и R2 с минимальной локальной степенью необходимо выбрать вершину R1 как имеющую младший индекс.

11) Построить множествоG_R₁:

G_R₁ = {R1, L1, VT1} (12)

Мощность полученного множества

G_R₁ = 3 < n₂ = 4 (13)

12) Множество G_R₁ необходимо дополнить ещё одной вершиной. Для этого необходимо построить множествоG_L₁:

G_L₁ = {L1, R1, C3, C4} (14)

13) Объединить множества G_R₁ и G_L₁:

G₂ = G_R₁ È G_L₁= {R1, L1, VT1, C3, C4} (15)

Мощность полученного множества G₂:

|G₂| = 5 > n₂ = 4 (16)

14) Из множества G₂ необходимо удалить одну вершину. С этой целью поочерёдно для каждой вершины множества G₂, кроме вершин R1 и L1, уже вошедших в множество G₂ (п. 11), определить количество рёбер z(x_j), связывающее эту вершину со всеми оставшимися вершинами множества G₂:

z(VT1) = 2; z(C3) = 1; z(C4) = 2 (17)

Так как вершина C3 имеет минимальное значение z(C3) = 1, то её следует удалить из множества G₂. В результате будет получено множество G₂^*:

G₂⁽¹⁾ = {R1, L1, VT1, C4} (18)

Мощность полученного множества G₂⁽¹⁾:

|G₂⁽¹⁾ | = 4 = n₂ (19)

На этом формирование второго куска G₂ = (X₂, U₂) закончено, где X₂ = {R1, L1, VT1, C4}.

15) Вершины, не вошедшие в сформированные куски G₁ и G₂, образуют третий кусок G₃ = (X₃, U₃) графа G, где X₃ = {C3, C5, R3, R2}. Результат разрезания графа G на три куска по четыре вершины в каждом представлен на рис. 3

Рис. 3. Результат разрезания графа

16) Количество рёбер внутри сформированных кусков: L₁ = 4, L₂ = 3, L₃ = 3.

17) Количество внешних связей между кусками: K₁₂ = 0, K₂₃ = 6, K₁₃ = 3.

18) Коэффициент разрезания графа G: D(G) = SL_l/ SK_l = 10/9 = 1,11

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

Литература

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

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

3. Шандриков А.С. Минимизация внешних связей в процессе разрезания графа последовательным методом [Электронный ресурс] / А.С. Шандриков // VIII Всероссийская научная конференция по математическому моделированию и информационным технологиям: Новосибирск, 27-29 ноября 2007 г. / Ин-т вычислительного моделирования Сибирского отд. Российской Академии наук – Режим доступа http://www.ict.ncs.ru/wc/history.php?ru+168+8609.

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

Рис. 4. Распределение радиоэлектронных компонентов по блокам РЭС