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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

),,(min),(
jik
k
ji
vvlvvr
=
где l
k
(v
i
, v
j
) – длина k-й цепи.
Максимальное расстояние между вершинами графа G называется диамет-
ром графа d(G):
).,(max)(
,
ji
ji
vvrGd
=
Введенная на множестве всех пар вершин (v
i
, v
j
) графа G функция
r(v
i
, v
j
) удовлетворяет трем аксиомам:
(∀ v
i
, v
j
) (r(v
i
, v
j
) = 0) ↔ v
i
= v
j
;
(∀ v
i
, v
j
) (r(v
i
, v
j
) = r(v
j
, v
i
));
(∀ v
i
, v
j
, v
k
) (r(v
i
, v
j
) + r(v
j
, v
k
) ≥ r(v
i
, v
k
))
и определяет его метрику.
Последнюю аксиому обычно называют неравенством треугольника.
Матрица называется k-клеточной, если в результате перестановки строк и
столбцов она преобразуется к клеточному виду с k клетками. Каждая клетка при этом не содержит ну-
левых элементов, кроме, быть может, диагональных.
Теорема. Граф G состоит из k компонент связности тогда и только то-
гда, когда его матрица достижимости
∑
=
=
)(
1
)]([)(
Gd
i
i
GSGD ,
где S(G) – матрица смежности графа G; d(G) – диаметр графа G, является k-клеточной.
Граф, состоящий из одной вершины, называется тривиальным. Удаление
вершины из нетривиального графа G приводит к подграфу G\v, содержащему все вершины графа G,
кроме v, и все ребра графа G, не инцидентные v. Аналогично, удаление ребра x приводит к подграфу,
содержащему все вершины (остовному подграфу) и ребра, за исключением ребра x, т.е. G\x.
Связностью χ (G) графа G называется наименьшее число вершин, удаление
которых делает граф несвязным или тривиальным. Из этого определения следует, что для любого не-
связного графа χ (G) = 0.
Если χ (G) ≥ n, то граф G называют n-связным.
Реберной связностью λ (G) графа G называется наименьшее количество ре-
бер, удаление которых приводит к несвязному или тривиальному графу. Для несвязного или тривиаль-
ного графа λ (G) = 0.
Рассмотрим ориентированный граф и его свойство быть сильно связным.
Понятие путь определяется как последовательность дуг (δ
1
, δ
2
, ..., δ
n
) вида δ
i
= (v
i
, v
i+1
), i = 1, 2, ..., n. Вершины пути могут иметь степень, равную 1. Вершина v
i
со степенью, равной
1, называется концевой. При этом вершина v
1
, коинцидентная дуге δ
1
, называется начальной, а вершина
v
n+1
, коинцидентная дуге δ
n
– конечной. Число дуг, образующих путь, называется длиной пути. Путь на-
зывается составным, если в нем повторяется хотя бы одна дуга, сложным – хотя бы одна вершина, и
простым – в противном случае.
Контуром называется путь, концевые вершины которого совпадают. Все
вершины контура имеют степень s(v
i
) ≥ 2.
Граф G = 〈V, U〉 называется сильно связным, если любая пара его вершин со-
единена путем.
Максимальный по включению вершин сильно связный подграф графа назы-
вается его компонентой сильной связности. Граф называется несильно связным, если число его компо-
нент сильной связности больше 1.
Рассмотрим алгоритм определения сильной связности графа и числа его
компонент сильной связности. Этот алгоритм, также как и алгоритм определения связности графа и

Страницы