Математические модели в управлении. Заболотский В.П - 72 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

72
При составлении матрицы инцидентности были использованы сле-
дующие обозначения:
u
1
= < x
1
, x
1
>, u
2
= < x
1
, x
3
>, u
3
= < x
1
, x
5
>, u
4
= < x
3
, x
1
>,
u
5
= < x
3
, x
2
>, u
6
= < x
3
, x
5
>, u
7
= < x
4
, x
1
>, u
8
= < x
5
, x
1
>,
u
9
= < x
5
, x
2
>, u
10
= < x
5
, x
3
>, u
11
= < x
5
, x
4
>, u
12
= < x
5
, x
5
>.
Матрица инцидентности, как и матрица смежности, полностью
определяет соответствующий граф. Все три рассмотренных спосо-
ба задания графов являются эквивалентными. Геометрический спо-
соб обладает наибольшей наглядностью, матричный способ широко
применяется при компьютерной обработке графов.
Приведем еще несколько понятий и определений, которые потре-
буются в дальнейшем.
Две дуги графа называются противоположно ориентирован-
ными, если для каждой из них начальная вершина одной дуги явля-
ется конечной вершиной другой дуги, а сами дуги считаются эквива-
лентными (с точностью до ориентации дуг).
Каждой паре противоположно ориентированных дуг { < x
i
, x
j
>,
< x
j
, x
i
>} графа G = < X, U > можно сопоставить неупорядоченный
элемент (x
i
, x
j
), составленный из концевых вершин сопоставляе-
мой пары дуг и называемый ребром графа. Неупорядоченность
ребра означает, что любая его концевая вершина может быть приня-
та за начальную, тогда другая концевая вершина будет конечной и
наоборот. Поэтому понятия начальной и конечной вершин для ребра
не определяются, а само ребро рассматривается как неориентиро-
ванная дуга. С другой стороны, возможен подход, при котором дугу
рассматривают как ориентированное ребро, для которого определе-
ны начальная и конечная вершины.
Каждому ребру графа, в свою очередь, можно сопоставить пару
противоположно ориентированных дуг. Следовательно, между таки-
ми парами дуг и сопоставляемыми ребрами существует взаимно
однозначное соответствие, и поэтому любую пару противоположно
ориентированных дуг в графе можно заменить соответствующим реб-
ром и наоборот. Петли в графе всегда считаются ребрами.
Геометрически ребро графа изображается ненаправленным (нео-
риентированным) отрезком, соединяющим две вершины. Диаграмма

Страницы