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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

54
где S(G) – матрица смежности графа G; d(G) – диаметр графа G; явля-
ется k-клеточной матрицей. ■
Отметим, что граф G на рис. 20 имеет диаметр d (G) = 2, а матрица
S(G) + S
2
(G) является его матрицей достижимости. Эта матрица однокле-
точная и, следовательно, граф G имеет одну компоненту связности, т.е.
является связным графом.
Рассмотрим далее ориентированный граф G и его свойство быть
сильно связным.
Путём в ориентированном графе G называется такая последова-
тельность его дуг (δ
1
, δ
2
, ..., δ
n
), что в каждой паре её соседних элементов
конец первой из дуг совпадает с началом второй дуги. Некоторый путь,
ведущий из вершины v
i
в вершину v
j
, может быть представлен в виде сле-
дующей последовательности:
((v
i
,
)
1
x
v
,
1
(
x
v
,
)
2
x
v
,
2
(
x
v
,
)
3
x
v
, …,
n
x
v(
, v
j
)).
При этом вершины v
i
и v
j
называются концевыми вершинами пути,
из них v
i
− начальная, а v
j
− конечная вершина пути. Число дуг в пути, ве-
дущем из вершины v
i
в вершину v
j
, называется длиной пути и обозначает-
ся l (v
i
, v
j
). Путь называется составным путём, если в нём повторяется
хотя бы одна дуга; сложным путём, если в нём повторяется хотя бы одна
вершина, и простым путём – в противном случае.
Контуром называется путь, концевые вершины которого совпадают.
Каждая вершина v контура имеет степень s(v) ≥ 2. Контур, в котором сте-
пень любой вершины равна двум, называется простым контуром, в про-
тивном случае − сложным контуром.
Рассмотрим ориентированный граф, изображённый на рис. 21. В нём,
например, путь (e, n, c) ведёт из вершины 1 в вершину 6, имеет длину 3 и
может быть представлен в виде ((1, 2), (2, 5), (5, 6)). Этот путь простой,
имеет концевые вершины 1 и 6, из них 1 − начальная, а 6 – конечная
вершина. Путь (d, e, k, d) является
составным путём, а сложный путь
(a, b, c) − простым контуром.
Ориентированный граф G называ-
ется сильно связным графом, если лю-
бая пара его вершин соединена путём.
Максимальный по включению вершин
сильно связный подграф графа называ-
ется его компонентой сильной связно-
сти. Граф называется несильно связным
графом, если он имеет более одной
компоненты сильной связности.
1
2
3
4
5
a
b
c
d
e
Рис. 21
6
k
m
n
p

Страницы