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

UptoLike

ВУЗ: 

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

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

Рубрика: 

71
Если граф имеет кратные дуги, то элемент r
ij
матрицы смежности-
равен числу дуг, исходящих из вершины x
i
и заходящих в вершину x
j
.
Для рассмотренного в примерах 2.1.1 и 2.1.2 графа матрица смеж-
ности имеет вид
x
1
x
2
x
3
x
4
x
5
1
2
5
3
5
4
5
10101
00000
11001
10000
11111
ij
x
x
r
x
x
x




==




R
Обозначим каждую дугу < x
i
, x
j
> графа символом u
k
, k = 1(1)m.
Определение 2.1.9. Матрица
ij
s=
S
размерности n × m, каж-
дой строке которой сопоставлена вершина x
i
, i = 1(1)n, а каждому
столбцу – дуга u
j
, j = 1(1)m графа G, и элементы s
ij
которой равны 1,
если дуга u
j
исходит из вершины x
i
; –1, если дуга u
j
заходит в вершину
x
i
, и 0, если дуга u
j
не инцидентна вершине x
i
или является петлей, т. е.
1, если дуга исходит из вершины ;
0, если дуга не инцидентна вершине или является петлей;
–1, если дуга заходит в вершину ,
ji
ij j i
ji
ux
su x
ux
=
называется матрицей инцидентности (инциденций) графа G.
Для рассмотренного в примерах 2.1.1 и 2.1.2 графа матрица инци-
дентности имеет вид
1 2 3 4 5 6 7 8 9 10 11 12
1
2
12
3
5
4
5
011100110000
00 0 0 1 0 0 0 1 0 00
=
010111000100
00 0 0 0 0 1 0 0 0 10
001001011110
ij
uu u u u u u u u u u u
x
x
s
x
x
x
−−−


−−


=
−−

−


−−

S

Страницы