ВУЗ:
Составители:
Рубрика:
Под умножением двух ненулевых элементов матриц понимается конкатена-
ция – соединение соответствующих строк символов. Сложение элементов матриц понимается как объе-
динение соответствующих строк.
Тогда элемент (i, j) матрицы S
n
будет представлять собой множество цепей
длины n, соединяющих вершины v
i
, v
j
.
Рассмотрим распределение цепей в неориентированном графе, представлен-
ном на рис. 19.
Матрица смежности этого графа имеет вид:
1 2 3 4 5
a e
1
a b
2
S =
b c
3
c d
4
e d
5
Матрица смежности S определяет распределение ребер (цепей единичной
длины). Для определения цепей длины 2 возведем эту матрицу в квадрат:
1 2 3 4 5
aa ee ab ed
1
aa
bb
bc ae
2
S
2
=
ba bb cc cd
3
de cb cc dd
4
ea dc ee dd
5
Суммируя матрицы S и S
2
, получим:
1 2 3 4 5
aa ee a ab ed e
1
a aa
bb
b bc ae
2
S + S
2
=
ba b bb cc c cd
3
de cb c cc dd d
4
e ea dc d ee dd
5
В матрице S + S
2
отсутствуют нулевые элементы, что означает существова-
ние цепи длины 1 или 2 между любой парой вершин графа. Следовательно, рассматриваемый граф име-
ет одну компоненту связности, т.е. является связным.
Понятие цепи используется при изучении метрических свойств графа.
Минимальная длина цепи, соединяющей вершины v
i
и v
j
, называется рас-
стоянием r(v
i
, v
j
) между вершинами v
i
и v
j
:
1
2
3
4 5
a
b
c
d
e
Рис. 19
Страницы
- « первая
- ‹ предыдущая
- …
- 36
- 37
- 38
- 39
- 40
- …
- следующая ›
- последняя »
