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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

53
Суммируя матрицы S (G) и S
2
(G), получим матрицу:
1 2 3 4 5
aa ee a ab ed e 1
a aa bb b bc ae 2
S (G) + S
2
(G) = ba b bb cc c cd 3
de cb c cc dd d 4
e ea dc d ee dd 5
в которой отсутствуют пустые элементы, что означает существование
цепи длиной 1 или 2 между любой парой вершин графа G. Следователь-
но, рассматриваемый граф является связным графом, т.е. имеет одну
компоненту связности.
Понятие цепи используется при изучении метрических свойств не-
ориентированного графа.
Длина кратчайшей цепи из всех цепей, соединяющих вершины v
i
и v
j
,
называется расстоянием между вершинами v
i
и v
j
и обозначается r (v
i
, v
j
):
),(min),(
jik
k
ji
vvlvvr = ,
где l
k
(v
i
, v
j
) – длина k-й цепи, соединяющей вершины v
i
и v
j
.
Введённая на множестве пар вершин (v
i
, v
j
) графа G функция r(v
i
, v
j
)
удовлетворяет трём аксиомам:
(∀ v
i
, v
j
∈ V) (r (v
i
, v
j
) = 0) ↔ v
i
= v
j
,
(∀ v
i
, v
j
∈ V) (r (v
i
, v
j
) = r (v
j
, v
i
)),
(∀ v
i
, v
j
, v
k
∈ V) (r (v
i
, v
j
) + r (v
j
, v
k
) ≥ r (v
i
, v
k
))
и определяет его метрику.
Последнюю аксиому обычно называют неравенством треугольника.
Максимальное расстояние между вершинами графа G называется
диаметром графа G и обозначается d (G):
),(max)(
,
ji
ji
vvrGd =
.
Матрица называется k-клеточной, если она имеет клеточный вид с
k клетками или преобразуется к такому виду в результате перестановки
строк и соответствующей перестановки столбцов. Каждая клетка матри-
цы клеточного вида не содержит пустых элементов, за исключением,
быть может, элементов её главной диагонали.
Теорема. Граф G состоит из k компонент связности тогда и толь-
ко тогда, когда его матрица достижимости
∑
=
=
)(
1
)]([)(
Gd
i
i
GSGD
,

Страницы