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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

55
Задача определения числа компонент сильной связности ориентиро-
ванного графа аналогична рассмотренной выше задаче определения чис-
ла компонент связности неориентированного графа. Решим её для гра-
фа G, представленного на рис. 21.
Матрица смежности этого графа имеет следующий вид:
1 2 3 4 5 6
e m 1
k n 2
S(G) = d p 3
b 4
c 5
a 6
Получим матрицу достижимости графа G. Поскольку диаметр d(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
Заметим, что компонентам сильной связности в матрице достижи-
мости ориентированного графа соответствуют квадратные подматрицы,
лежащие на её главной диагонали. Каждый элемент такой подматрицы, за
исключением, быть может, элементов главной диагонали, является не-
пустой строкой символов. При этом в матрице достижимости могут су-
ществовать непустые элементы и вне упомянутых подматриц. Такие эле-
менты характеризуют связи между компонентами сильной связности.
В нашем примере матрица D(G) имеет на главной диагонали две
клетки. Они соответствуют компонентам сильной связности графа G с
множествами вершин {1, 2, 3} и {4, 5, 6}. Непустая область (1, 4) − (3, 6)
матрицы характеризует существующие пути из вершин первой компо-
ненты сильной связности в вершины второй компоненты.

Страницы