Основы математического моделирования. Псигин Ю.В - 13 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

12
Пр и раскрытии темы наряду с понятием множества как совокупности
элементов необходимо раскрыть важное понятие упорядоченного множества,
или кортежа. Кортежем называется последовательнос ть элементов, т. е.
совокупность элементов, в которой каждый элемент занимает определенное
место и, в отличие от обычного множества, эта совокупность может иметь
одинаковые элементы.
Пр и написании контрольной работы по данной
теме необходимо
привести примеры, графическое пояснение (если это возможно) и четкие
определения таких понятий, как прямое произведение множеств, с оответс твие,
отображение и отношение.
2. 2. 3. Тема № 3. Основы теории графов
Раскрывая тему, содержащую основы теор ии графов, необходимо
представить граф как некоторое множество точек плоскости X, называемых
вершинами, и множество направленных отрезков U, соединяющих все или
некоторые из вершин и называемых дугами (рис. 2, а). Матема тич ес ки граф G
можно определить как пар
у
множеств X и U: G = (X, U).
Иногда бывает удобно дать графу другое определение. Можно считать,
что множество направленных дуг U, соединяющих элементы множества X,
отображает это множество само в себя. Поэтому можно считать граф заданным,
если дано множество его вершин X и способ отображения Г множества X в X.
Таким образом, граф G есть пара (X, Г), состоящая из множества X и
отображения Г, заданного на этом множестве: G = (X, Г).
Далее необходимо на конкретном примере показать, что тако е
определение графа совпадает с определением отношения на множестве и
появляется возможность предс тавления графа в виде матриц смежности и
инциденций (рис. 3, 4). Следует пояснить, что две вершины графа х и у
являются смежными, если они различны и если
существует дуга u, идущая из х
в у; дуга u называется инцидентной вершине x, если она заходит в эту вершину
или выходит из нее.
Любой граф G=(x, y) с m вершинами может быть представлен матрицей
смежности размера mm × при условии, что вершинам графа приписаны
некоторые (произвольные) метки. Если вершины графа помечены метками x
1
,
x
2
, …x
n
, то матрица смежности А(G) определяется следующим образом:
],a[)G(A
ij
=
где
ij
a = 1, ес ли имеется дуга, соединяющая вершину x
i
c вершиной x
j
;
ij
a = 0, – в противном случае.
В качестве примера приведем граф и матрицу его смежности для оценки
геометрической структуры детали ( рис. 3 ).
Второй метод представления графа использует матрицу инцидентности

Страницы