Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Проектирование технического объекта - создание, преобразование и представление в принятой форме образа этого еще не существующего объекта. Образ объекта или его составных частей может создаваться в воображении человека в результате творческого процесса или генерироваться в соответствии с некоторыми алгоритмами в процессе взаимодействия человека и ЭВМ. В любом случае инженерное проектирование начинается при наличии выраженной потребности общества в некоторых технических объектах, которыми могут быть объекты строительства, промышленные изделия или процессы. Проектирование включает в себя разработку технического предложения (ТП) и (или) технического задания (ТЗ), отражающих эти потребности, и реализацию ТЗ в виде проектной документации.
Обычно ТЗ представляют в виде некоторых документов, и оно является исходным (первичным) описанием объекта. Результатом проектирования, как правило, служит полный комплект документации, содержащий достаточные сведения для изготовления объекта в заданных условиях. Эта документация и есть проект, точнее окончательное описание объекта. Более коротко, проектирование - процесс, заключающийся в получении и преобразовании исходного описания объекта в окончательное описание на основе выполнения комплекса работ исследовательского, расчетного и конструкторского характера.
Преобразование исходного описания в окончательное порождает ряд промежуточных описаний, подводящих итоги решения некоторых задач и используемых для обсуждения и принятия решений для окончания или продолжения проектирования. Такие промежуточные описания называют проектными решениями.
Проектирование, при котором все проектные решения или их часть получают путем взаимодействия человека и ЭВМ, называют автоматизированным проектированием, в отличие от ручного (без использования компьютера) или автоматического (без участия человека на промежуточных этапах). Система, реализующая автоматизированное проектирование, представляет собой систему автоматизированного проектирования (САПР, в англоязычном написании CAD System - Computer Aided Design System).
Автоматическое проектирование возможно лишь в отдельных частных случаях для сравнительно несложных объектов. Превалирующим в настоящее время является автоматизированное проектирование.
Как и любая сложная система, САПР состоит из подсистем. Различают подсистемы проектирующие и обслуживающие.
Проектирующие подсистемы непосредственно выполняют проектные процедуры. Примерами проектирующих подсистем могут служить подсистемы геометрического трехмерного моделирования механических объектов, изготовления конструкторской документации, схемотехнического анализа, трассировки соединений в печатных платах.
Обслуживающие подсистемы обеспечивают функционирование проектирующих подсистем, их совокупность часто называют системной средой (или оболочкой) САПР. Типичными обслуживающими подсистемами являются подсистемы управления проектными данными, подсистемы разработки и сопровождения программного обеспечения CASE (Computer Aided Software Engineering), обучающие подсистемы для освоения пользователями технологий, реализованных в САПР.
По приложениям наиболее представительными и широко используемыми являются следующие группы САПР.
Кроме того, известно большое число специализированных САПР, или выделяемых в указанных группах, или представляющих самостоятельную ветвь в классификации. Примерами таких систем являются САПР больших интегральных схем (БИС); САПР летательных аппаратов; САПР электрических машин и т.п.
Структурирование САПР по различным аспектам обусловливает появление видов обеспечения САПР. Принято выделять семь видов обеспечения:
В данном курсе рассматривается математическое обеспечение САПР.
ПЕРЕХОД К КОНСТРУКТОРСКОМУ ПРОЕКТИРОВАНИЮ
При решении задач конструкторского проектирования можно условно выделить этапы:
Из всего комплекса задач технического проектирования самой важной является задача разбиения электрических схем на конструктивно законченные части. От результата решения данной задачи зависит качество решения последующих задач технического проектирования.
В качестве математической модели электрической схемы проектируемых устройств используется теория графов. С помощью этой теории удобно строить алгоритмы оптимизации, пригодные для реализации на компьютере. Под построением формальной модели схемы имеется в виду переход от схемы к графу.
Граф G состоит из множества вершин Х (точек) и множества ребер U (линий) соединяющих между собой все или часть вершин. Обозначение графа G=(X;U). Запись uijU означает, что ребро графа uij=(xi,xj) образовано парой вершин xi и xj, xiX, xjX. Таким образом, ребра - это упорядоченные пары вершин.
С помощью графов можно отразить наиболее общие свойства объектов (топологические свойства), отвлекаясь от их геометрических форм и размеров.
Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом. Для такого графа ukj=(xk,xj)(xj,xk)=ujk - это различные ребра
Если ребра не имеют ориентации, граф называется неориентированным.
Для него ukj=(xk,xj)=(xj,xk)=ujk.
Пример:
Вершины: здания; ребра: прямые улицы
В нашем курсе изучаются неориентированные графы. Две вершины xi и xj называются смежными, если существует ребро uijU, соединяющее эти вершины. Другими словами, смежными называются вершины, прилегающие к одному и тому же ребру.
Ребро uij инцидентно вершинам xi, xj, если оно связывает эти вершины. Ребра ukl, ulm называются смежными, если они имеют общую вершину (в примере вершина l).
Мультиграф – граф, любые две вершины которого связаны более чем одним ребром. В таком графе ребра, связывающие одну и ту же пару вершин, называются кратными. Мультичисло - наибольшее число кратных ребер в графе.
Петли – ребра графа, у которых обе концевые вершины совпадают, то есть uij=(xi,xj), i=j (рис. 1.2).
Число ребер, инцидентных некоторой вершине, называют степенью вершины, обозначается p(x). Для графа на рис 1(а) p(x5)=3, p(x1)=1. Легко увидеть, что если сложить степени всех вершин графа, то получится четное число равное удвоенному числу ребер, так как каждое ребро участвует в сумме 2 раза. Этот результат называют леммой Эйлера о рукопожатиях (если несколько человек обменялись рукопожатием, то число пожатых рук – четно). Из этой леммы следует, что
в любом графе число вершин нечетной степени всегда четно.
Лемма о рукопожатиях. Число вершин в графе (или мультиграфе без петель), имеющих нечетную степень, четно.
Доказательство леммы. Заметим, что сумма степеней всех вершин в графе (или мультиграфе без петель) должна быть четной. Это следует из того, что если взять вершины, вообще не связанные друг с другом, то сумма степеней этих вершин равна нулю. Прибавляя любое ребро, которое связывает две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин четна. Удаляя из этой суммы степени четных вершин, получим, что сумма степеней нечетных вершин, должна быть четной. Это значит, что само число таких вершин должно быть четным. Лемма доказана.
Графы на рис. 1.3 все выглядят как различные, но каждый из них можно перерисовать так, чтобы он стал (если не обращать внимание на обозначение вершин) идентичен другому. То есть все эти графы в некотором смысле «эквивалентны», имеют одинаковую структуру. Определим более точно характер этой «эквивалентности».
(а) (б) (в)
Рис. 1.3. Изоморфные графы
Графы G=(X,U) и G'=(X',U') изоморфны (пишут GG'), если существует взаимно-однозначное соответствие между множествами X и X', сохраняющее смежность вершин (т.е. такое соответствие, при котором вершины xi и xj из множества X смежны тогда и только тогда, когда смежны соответствующие им вершины x'i и x'j из множества X').
Изоморфизм графа рис. 1.3 (а), к графу рис.1.3 (б) обнаруживается, если задать следующее соответствие между вершинами:
|
а1-б1, а2-б5, а3-б6, а4-б3, а5-б2, а6-б4 |
(1.1) |
Посмотрим, как это делается.
Для рис. 1.3(а) перечень неповторяющихся ребер:
|
(а1,а4) (а1,а5) (а1,а6) (а2,а4) (а2,а5) (а2,а6) (а3,а4) (а3,а5) (а3,а6) |
(1.2) |
Для рис. 1.3(б) перечень неповторяющихся ребер:
|
(б1,б3) (б1,б2) (б1,б4) (б5,б3) (б5,б2) (б5,б4) (б6,б3) (б6,б2) (б6,б4) |
(1.3) |
Если к (1.2) применить выражение (1.1), то получится выражение (1.3), т.е. графы на рис. 1.3 (а) и рис. 1.3(б) изоморфны.
Установить изоморфизм графа рис. 1.3(в), к графам на рис. 1.3 (а) и рис. 1.3(б) предлагается самостоятельно, определив надлежащее соответствие между их вершинами.
Для рис. 1.3(в) перечень неповторяющихся ребер:
|
(в1,в2) (в1,в4) (в1,в5) (в3,в2) (в3,в4) (в3,в5) (в6,в2) (в6,в4) (в6,в5) |
(1.4) |
При сопоставлении выражений (1.2) и (1.4), получается выражение (1.5) устанавливающее изоморфизм графа на рис. 1.3(в), к графу на рис. 1.3 (а):
|
а1-в1, а2-в3, а3-в6, а4-в2, а5-в4, а6-в5 |
(1.5) |
При сопоставлении выражений (1.3) и (1.4), получается выражение (1.6) устанавливающее изоморфизм графа на рис. 1.3(в), к графу на рис. 1.3 (а):
|
б1-в1, б2-в4, б3-в2, б4-в5, б5-в3, б6-в6 |
(1.6) |
Полный граф – граф, у которого все вершины попарно смежные (рис. 1.4.). Так как для полного графа p(x1)= p(x2)= …= p(xn)=n-1, то число ребер в таком графе
|
(1.4) |
Связный граф - неориентированный граф, у которого из любой вершины есть путь в любую другую вершину (путь может состоять из любого количества рёбер). На рис. 1.5 граф является связным.
Несвязанный граф – граф, состоящий из отдельных фрагментов. Если у графа на рис 1.5 удалить ребро между вершинами 4 и 5, то связным он не будет - из вершины 5 нельзя будет попасть ни в какую другую вершину.
Изолированная вершина – вершина, которой не инцидентно ни одно ребро.
Пустой граф – граф, состоящий только из изолированных вершин.
Висячая вершина – вершина степень, степень которой равна 1.
Граф G'=(X',U') называется частью графа G=(X,U), если X'X, U'U и обозначается G'G, т.е. часть графа – это граф, полученный из исходного графа исключением некоторых вершин и некоторых ребер.
Часть графа G'=(X',U') называют подграфом графа G=(X,U), если X'X, а множество ребер U'U образовано всеми ребрами, соединяющими между собой только вершины из X', т.е. подграф - граф, полученный из исходного графа исключением некоторых вершин и всех инцидентных им ребер.
Часть графа G'=(X',U') называют суграфом графа G=(X,U), если X'=X, а U'U, т.е. суграф - граф, полученный из исходного графа исключением некоторых ребер.
Объект Gi=(Xi,Ui), называется куском графа G=(X,U), если XiX, UiU, причем Ui=UiiUij, где Uii-множество ребер соединяющих вершины из Xi между собой, а Uij - множество ребер, один конец которых принадлежит Xi, а второй X\Xi, т.е. Xi - подмножество X, а в Ui входят все ребра из U, инцидентные Xi. Другими словами, кусок графа G(Z,U) – это граф Q(X,Y), являющийся частью исходного графа такой, что X — подмножество Z, а в Y входят все ребра из U, инцидентные X.
Пример:
Двигаясь по ребрам графа G(X,U), можно переходить из вершины в вершину. Любая последовательность ребер, получаемая при этом, называется маршрутом, то есть последовательность (x0,x1)(x1,x2)…(xn,xn-1), в которой любые два соседних ребра смежные - маршрут.
Цепь – маршрут, в котором все ребра различны.
Простая цепь – цепь, в которой все вершины различны.
Цикл - цепь, в которой совпадают начальная и конечная вершины.
Дерево - связный граф без циклов. В дереве любые две вершины связаны единственной цепью. Дерево, построенное на n вершинах, имеет n-1 ребер.
Лес - совокупность деревьев.
Пример:
В графах выделяют два замечательных цикла: эйлеров и гамильтонов.
Граф называется эйлеровым, если для всякой вершины графа найдется маршрут начинающейся и заканчивающейся в этой вершине и проходящий через каждое ребро только один раз. Такой маршрут называется эйлеровым циклом.
Задача возникла из следующего примера. В XIII веке жители Кенигсберга, прогуливаясь по мостам реки, Прегель пытались решить задачу: можно ли обойти все мосты, проходя по каждому из них только один раз (рис. 1.8)
Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра - с мостами, которыми связаны эти части.
Эйлеру удалось доказать, что искомого маршрута обхода города не существует.
Ответ может быть получен на основе следующей теоремы.
Теорема. Граф является эйлеровым тогда и только тогда, когда степени всех его вершин четные.
Как следует из рисунка, у графа, моделирующего схему мостов, все вершины имеют нечетную степень. Следовательно, эйлерова цикла в этом графе не существует.
Пример графа, имеющего эйлеров, цикл показан на рис. 1.9.
Граф называется гамильтоновым, если для каждой вершины графа найдется маршрут начинающейся и заканчивающей в этой вершине и проходящий через все вершины только один раз (при этом могут участвовать не все ребра). Такой маршрут называется гамильтоновым циклом.
В полном графе с числом вершин n»2 всегда существует гамильтонов цикл. Пример такого цикла приведен на рис. 1.10 - (x1,x4) (x4,x2) (x2,x5) (x5,x3) (x3,x1).
Гамильтоновы графы применяются для моделирования многих практических задач, например, служат моделью при составлении расписания движения поездов. Основой всех таких задач служит классическая задача коммивояжера: коммивояжер должен совершить поездку по городам и вернуться обратно, побывав в каждом городе ровно один раз, сведя при этом затраты на передвижения к минимуму.
Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра - связывающие их дороги. Кроме того, каждое ребро оснащено весом, обозначающим транспортные затраты, необходимые для путешествия по соответствующей дороге, такие, как, например, расстояние между городами или время движения по дороге. Для решения задачи необходимо найти гамильтонов цикл минимального общего веса.
Графу G(X,U), имеющему n вершин, можно поставить в соответствие квадратную матрицу R=║rij║nxn, элементы которой rij соответствуют числу ребер, соединяющих вершину xi с вершиной xj. Это матрица смежности. Она задает в числовом виде связь смежных вершин. Элемент rii определяет число петель вершины xi.
Для графа, представленного на рис. 1.11 матрица смежности записывается в виде:
|
R = |
x1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
|
x1 |
0 |
1 |
0 |
0 |
1 |
|
|
x2 |
1 |
0 |
0 |
2 |
1 |
|
|
x3 |
0 |
0 |
0 |
1 |
0 |
|
|
x4 |
0 |
2 |
1 |
0 |
1 |
|
|
x5 |
1 |
1 |
0 |
1 |
0 |
Матрица смежности обладает следующими свойствами:
Матрица инцидентности S=║sij║nxm - матрица, строки которой соответствуют вершинам графа G(X,U), столбцы – его ребрам:
|
|
, если i вершина инцидентна j-му ребру uj; , если i вершина не инцидентна j-му ребру uj; |
где n – число вершин графа (n = card X);
m – число ребер графа (m = card U).
Для графа G (рис. 1.11) матрица инцидентности имеет вид:
|
U1 |
U2 |
U3 |
U4 |
U5 |
U6 |
U7 |
||
|
x1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
S= |
x2 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
|
x3 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
x4 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|
|
x5 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
В общем случае S не квадратная матрица. В каждом столбце матрицы S имеется две единицы, так как каждое ребро соединяет 2 вершины. Матрицы R и S однозначно задают информацию о графе.
Введение 1
Понятие проектирования 1
Структура САПР 3
Классификация САПР по приложениям 3
Виды обеспечения САПР 4
Лекция 1 7
Основные понятия теории графов 7
Изоморфизм графов 10
Классификация графов 12
Цепи и циклы в графах 16
Описание графов матрицами 21