Дискретная математика. Кулаков Ю.В - 35 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

.)(,
0000000
1000000
0100000
0100000
0011000
0010100
0001100
)(
ш
ш
ш
ш
2
1
f
x
x
GWGS
ϕ
ϕ
ϕ
ϕ
==
Все ненулевые элементы матрицы S равны 1, так как дуги этого графа не взвешены.
Два графа G = 〈V, U〉 и G' = 〈V', U'〉 называются изоморфными, если сущест-
вует такое взаимно-однозначное соответствие между их вершинами V и V', что вершины v
a
, v
b
соедине-
ны дугой (v
a
, v
b
) в первом графе в том и только в том случае, когда соответствующие им вершины
ba
vv
′
′
,
соединены дугой (
ba
vv
′′
, ) во втором графе. Матрицы рассмотренных классов задают графы с точностью
до изоморфизма.
Обозначим через (A
+
)
т
транспонированную матрицу инциденций A
+
. Матри-
ца смежности, начальная A
+
и конечная A
−
матрицы инциденций, а также диагональная матрица весов
дуг связаны следующим равенством:
S = (A
+
)
т
⋅ P ⋅ (A
−
).
С помощью матриц смежности можно задавать и неориентированные графы.
Так, граф (рис. 17, б) без учета весов его вершин и ориентации дуг полностью описывает матрица
v
1
v
2
v
3
v
4
v
5
v
6
v
7
0 0 1 1 0 0 0
v
1
0 0 1 0 1 0 0
v
2
1 1 0 1 1 0 0
v
3
S(G)
=
1 0 1 0 0 1 0
v
4
.
0 1 1 0 0 1 0
v
5
0 0 0 1 1 0 1
v
6
0 0 0 0 0 1 0
v
7
Большие неориентированные графы, матрицы смежности которых слабо за-
полнены единицами, можно задавать более эффективно в смысле затрачиваемого объема информации,
используя при этом понятие мографа.
При этом связному неориентированному графу G = 〈V, U〉 без петель сопос-
тавляется модель Ψ = <M, S
1
, S
2
, ... , S
n
> с носителем M = V. Слово, определяемое отношением S
i
, состо-
ит из i букв: окрестности единичного радиуса O(v
α
), v
α
∈V мощности (i – 1) и самой вершины v
α
.
Матрица инцидентности Q(ψ) модели ψ в этом случае представляет собой
матрицу смежности S(G) графа G, в которой любой из элементов главной диагонали равен 1:
v
1
v
2
v
3
v
4
v
5
v
6
v
7
1 0 1 1 0 0 0 v
1
0 1 1 0 1 0 0 v
2
1 1 1 1 1 0 0 v
3
Q(ψ) =
1 0 1 1 0 1 0 v
4
.
0 1 1 0 1 1 0 v
5
0 0 0 1 1 1 1 v
6
0 0 0 0 0 1 1 v
7

Страницы