Дискретная математика. Громов Ю.Ю - 45 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

45
Элемент матрицы инциденций A(G) = [a
ij
]
m × n
графа G, содержащего
n вершин и m дуг, определяется следующим образом:
−−=
.дугенакоинцидентневершинаесли,0
;дугиконецвершинаесли,1
;дугиначалом являетсявершинаесли,1
ij
ij
ij
ji
uv
uv
uv
a
Если граф G имеет петли, т.е. дуги вида (v
i
, v
i
), некоторые элементы
матрицы A(G) одновременно должны быть равны и 1, и –1, что приводит
к неоднозначности. Поэтому для задания графа G с петлями матрицу ин-
циденций «расщепляют» на две матрицы: начальную матрицу инциден-
ций A
+
(G) = [
+
ij
a ]
m × n
, в которой элемент
−
=
+
случаепротивномв0
;дугиначаловершинаесли,1
ij
ji
uv
a
и конечную матрицу инциденций A
−
(G) = [
−
ij
a
]
m × n
, где элемент
−
=
−
случае.противномв0
;дугиконецвершинаесли,1
ij
ji
uv
a
Для графа без петель справедливо равенство A(G) = A
+
(G) − A
−
(G).
Заметим, что матрицы A(G), A
+
(G) и A
−
(G) описывают граф G без учёта
весов его вершин и дуг.
Зададим веса вершин графа G в виде матрицы-столбца W(G), а веса
дуг − в виде диагональной матрицы P(G):
x
1
x
2
f (x
1
, x
2
)
1
1
1
1
v
1
v
2
v
3
v
4
v
5
v
6
v
7
x
1
x
2
ϕ
ш
ϕ
ш
ϕ
ш
ϕ
ш
f
а)
б)
Рис. 19

Страницы