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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

числа компонент связности, рассмотренный для случая неориентированного графа, основан на исполь-
зовании предыдущей теоремы.
Определим сильную связность ориентированного графа, представленного на
рис. 20.
Матрица смежности этого графа имеет вид:
1 2 3 4 5 6
e m
1
k n
2
S(G) =
d p
3
b
4
c
5
a
6
Максимальная степень, в которую необходимо возвести матрицу смежности
S графа G, равна диаметру d(G) этого графа:
,),(minmax)(
,
jik
k
ji
vvlGd
=
где ),(
jik
vvl – длина k-го пути от вершины v
i
к вершине v
j
.
В рассматриваемом примере диаметр d(G) графа G равен 3. Матрицу дости-
жимости D(G) вычисляем как
∑
=
3
1
)]([
i
i
GS :
1 2 3 4 5 6
ekd e ek m en mb
ekp enc
mbc
1
kd kde k
kdm kpa
nca
n kp nc
2
D(G)
=
d de dek dm pa
den dmb
pab
p
3
bca b bc
4
ca cab c
5
a ab abc
6
Компоненте сильной связности в матрице достижимости соответствует под-
матрица максимального размера, каждый элемент которой не равен пустой строке символов. Элементы,
показывающие связь между подматрицами, могут быть не пустыми строками.
В данном примере имеем две компоненты сильной связности с носителями
{1, 2, 3} и {4, 5, 6} соответственно.
Задачи и упражнения
1 Определить множество концевых вершин цепи:
а) ({1, 2}, {2, 3}, {3, 4}, {4, 5});
б) ({2, 3}, {1, 2}, {1, 5}, {2, 5}, {2, 4});
в) ({1, 2}, {2, 3}, {3, 4}, {4, 5}, {2, 5});
г) ({3, 4}, {4, 5}, {1, 5}, {1, 2}, {2, 3});
д) ({1, 2}, {1, 3}, {3, 5}, {1, 5}, {1, 3}, {3, 4});
е) ({2, 5}, {1, 5}, {1, 2}, {2, 3}, {3, 4}, {2, 4}).
1
2
3
4
5
a
b
c
d
e
Рис. 20
6
k
m
n
p

Страницы