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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

47
0 0 1 1 0 0 0 x
1
0 0 1 0 1 0 0 x
2
0 0 0 1 1 0 0
ϕ
ш
S(G) =
0 0 0 0 0 1 0 , W(G) =
ϕ
ш
.
0 0 0 0 0 1 0
ϕ
ш
0 0 0 0 0 0 1
ϕ
ш
0 0 0 0 0 0 0 f
Заметим, что все ненулевые элементы матрицы S(G) равны 1, так как
дуги этого графа не взвешены.
Между графами G = 〈V, U〉 и G′ = 〈V′, U′〉 имеет место изоморфизм,
если существует такое взаимно-однозначное соответствие между верши-
нами из множеств V и V′, что вершины v
i
и v
j
соединены дугой (v
i
, v
j
) в
графе G тогда и только тогда, когда соответствующие им вершины
i
v
′
и
j
v
′
соединены дугой (
ji
vv
′
′
,
) в графе G′. Графы, между которыми имеет
место изоморфизм, называются изоморфными графами. Например, изо-
морфными графами являются графы, изображённые на рис. 20, а и б.
Матрицы инциденций и смежности задают графы с точностью до
изоморфизма.
С учётом обозначения через (A
+
)
т
транспонированной матрицы A
+
,
связь между матрицами инциденций и смежности, а также матрицей ве-
сов дуг может быть представлена следующим равенством:
S = (A
+
)
т
× P × (A
−
).
При помощи матрицы смежности можно задавать и неориентиро-
ванные графы. Так, например, граф на рис. 19, б без учёта ориентации его
дуг (назовём его графом G) будет описывать матрица смежности:
а)
'
v
1
5
v
4
v
3
v
2
v
1
v
6
v
'
v
5
'
v
3
'
v
6
'
v
2
'
v
4
б)
Рис. 20

Страницы