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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

51
9. СВЯЗНОСТЬ И СИЛЬНАЯ СВЯЗНОСТЬ ГРАФА
Понятия связности и сильной связности относятся к неориентиро-
ванным и ориентированным графам соответственно.
Рассмотрим неориентированный граф 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
}, …, {
1−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. Цикл, в котором степень
каждой вершины равна двум, называется простым циклом, в противном
случае − сложным циклом.
Рассмотрим неориентированный граф, изображённый на рис. 20.
В нём, например, цепь (a, b, c, d) соединяет вершины 1 и 5, имеет длину 4
и может быть представлена в виде ({1, 2}, {2, 3}, {3, 4}, {4, 5}). Она явля-
ется простой цепью, имеет концевые вершины 1 и 5, из них 1 − началь-
ная, а 5 − конечная вершина. Цепь (a, b, c, d, e) является сложной цепью и
простым циклом.
Неориентированный граф G называется связным графом, если лю-
бая пара его вершин соединена цепью. Максимальный по включению
вершин связный подграф графа G называется его компонентой связно-
сти. Граф G называется несвязным
графом, если он имеет более одной
компоненты связности. Например,
граф, состоящий из двух несмеж-
ных вершин, имеет две компонен-
ты связности и является несвязным
графом.
Рассмотрим задачу определе-
ния числа компонент связности не-
ориентированного графа.
1
2
3
4 5
a
b
c
d
e
Рис. 20

Страницы