САПР в задачах конструкторского проектирования. Тюрин И.В. - 8 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

При этом должны выполняться следующие ограничения на компоновку: число вершин в каждой части должно быть за-
дано; одна вершина должна принадлежать лишь одной части; объединение всех частей должно быть равно исходному графу.
Сущность последовательного алгоритма состоит в поочередной компоновке частей графа от первой до последней. При
формировании j-й части G
j
(V
j
, R
j
) из рассматриваемого множества
i
j
i
vV
1
1
\
−
=
U
вершин выбирается v
(j)
, имеющая минимальную
степень S(v
(j)
). К вершине v
(j)
добавляются смежные с ней вершины, в результате образуется подмножество V
(j)
, мощность
которого сопоставляется с требуемым числом N
j
. Если V
(j)
= N
j
, то добавляется или удаляется необходимое число вершин,
затем переходят к формированию следующей (j + 1)-й части и т.д.
Рассмотрим основные этапы последовательного алгоритма компоновки.
1. Исходный мультиграф G
(V, R) представляется матрицей смежности S.
2. Выбирается вершина v
(1)
, степень которой минимальна, т.е.
(
)
{
}
VvvSvS
v
∈= ),(min
)1(
. Если вершин с минимальной
степенью несколько, то выбирается вершина с максимальным числом кратных ребер.
3.
Формируется первоначальное подмножество вершин V
(1)
для первой части, в которое включается вершина v
(1)
и
смежные с ней вершины.
4.
На основе подмножества V
(1)
образуется множество вершин V
1
, первой части. Если мощность полученного подмноже-
ства равна заданному числу вершин первой части, т.е. V
(1)
= N
1
, то V
1
= V
(1)
. В случае V
(1)
> N
1
необходимое число вершин
удаляется, а при V
(1)
< N
1
– добавляется. В результате компонуется первая часть G
1
(V
1
, R
1
).
5.
Из графа G (V, R) удаляется сформированная часть G
1
(V
1
, R
1
).
Для оставшегося графа G
(V, R) / G
1
(V
1
, R
1
) аналогично выделяется вторая часть G
2
(V
2
, R
2
) и т.д.
Наибольшую трудность выполнения работы представляют расчеты четвертого этапа для случая V
(1)
≠ N
1
. Чтобы опре-
делить, какую вершину v
удалять из V
(1)
(или добавлять к V
(1)
), для каждой вершины v
i
∈ V
(1)
(или v ∈ V / V
(1)
) определяется ее относительный вес
∑
∈
−=δ
1
,
)()(
Jj
jiii
SvSv ,
где S
(v)
– степень вершины v; J
1
– множество номеров вершин v
i
∈ V
(1)
. Относительный вес δ(v) вершины v характеризует
приращение числа внешних ребер части G
1
(V
1
, R
1
) при включении вершины v в часть V
1
. Из множества вершин V
1
удаляется
вершина, для которой вес δ(v) максимален, или добавляется вершина v
∈ V/ V
(1)
с минимальным значением δ(v).
СОДЕРЖАНИЕ ОТЧЕТА
1. Название лабораторной работы.
2.
Цель работы.
3.
Исходные данные согласно варианту.
4.
Представление исходного графа матрицей смежности.
5.
Выполнение этапов последовательного алгоритма разбиения графа.
6.
Расчет критерия оптимальности.
7.
Вывод по результатам работы.
8.
Список использованной литературы.
Контрольные вопросы
1. В каком порядке составляется матрица смежности?
2.
Что понимается под степенью вершины?
3.
Какие основные ограничения накладываются на компоновку вершин?
4.
Что характеризует относительный вес вершины?
5.
Какой параметр определяет эффективность решения задачи компоновки последовательным алгоритмом?
ЛАБОРАТОРНАЯ РАБОТА 4
Решение задачи разбиения последовательно-итерационным алгоритмом
Цель работы. Ознакомиться с последовательно-итерационным алгоритмом разбиения и решить задачу компоновки пу-
тем представления графа, соответствующего электрической принципиальной схеме, матрицей смежности и определить чис-
ло внешних связей между скомпонованными частями.
Исходные данные. В качестве исходных данных используются результаты лабораторной работы 3, т.е. схема электриче-
ская принципиальная, заданная в виде мультиграфа G(V, R) с числом вершин (мощностью) V, разбитая на n = 3 части по-
следовательным алгоритмом.
Требуется провести итерационное улучшение и сравнить число внешних связей между скомпонованными частями, полу-
ченное в результате выполнения последовательного алгоритма, с числом внешних связей после применения итерационного
алгоритма.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ РАБОТЫ
В соответствии с заданием требуется разрезать (разбить) граф G(V, R) на n частей G
1
(V
1
, R
1
), …, G
n
(V
n
, R
n
) с N
i
верши-
нами в каждой так, чтобы число ребер, соединяющих вершины разных частей, было минимальным, т.е. критерий оптималь-
ности

Страницы