Математические модели объекта проектирования

В зависимости от отображаемых свойств объекта различают:

- структурные модели

- геометрические модели

- функциональные модели

Структурные модели

Структурные модели отражают взаимное расположение и наличие связей между элементами объекта проектирования. Наибольшее распространение в САПР находят структурные модели в виде графов. Достоинствами – графовых моделей являются простота и наглядность представления структуры объекта в виде графа, возможность постановки большого числа различных формальных задач на графах, простота представления графов в ЭВМ.

Граф – это множество вершин X= {x1, …, xi, …, xn} и множество ребер

U= {u1, …, uj, …,um}, соединяющих вершины. Каждое ребро uj есть пара вида (х_i,x_j). Вершины связанные ребром, называются смежными. Наличие ребра между вершинами xi и x_j означает наличие связи между элементами

xi и x_j (логическую, электрическую, механическую). Кроме связей важно бывает предоставить направление этой связи. Направление моделируется ребром со стрелкой – это ориентированный граф. Если есть несколько связей между вершинами, то это мультиграф.

Часто необходимо задать дополнительную информацию о ребрах или вершинах (например, расстояние). Эта дополнительная информация задается с помощью цифровых меток, которые присваиваются рёбрам или вершинам. Метки называются весами, а граф – называется взвешенним.

Для представления графа в ЭВМ удобно использовать специальные матрицы – смежности и инцидентности (Bn×m)

Матрица смежности А – квадратная размерности n с элементами a_ij определяемыми по следующему правилу:

Матрица инцидентности В – прямоугольная матрица размерности nxm, элементы в_ik которой находятся по следующему правилу:

Бинарный характер матриц А и В позволяет экономно записывать матрицы в память ЭВМ, отводя на каждый элемент по одному двоичному разряду машинного слова. Это дает возможность хранить и обрабатывать матрицы очень большой размерности.

Путем или маршрутом в графе называется последовательность смежных ребер вида ....( х_i,x_j), (х_j,x_k),( х_k,x_l).....Цепью называется маршрут, в которой нет повторяющихся ребер. Циклом называется замкнутая цепь. Граф, у которого нет циклов, называется ациклическим (деревом).