ВУЗ:
Составители:
Рубрика:
52
Пусть S(G) – такая матрица смежности графа G, что её произволь-
ный элемент определяется следующим образом:
=
смежны.не,вершиныеслисимвол, пустой
;,вершиныгосоединяющеребра,символ
ji
ji
ij
vv
vv
s
При возведении матрицы S(G) в степень умножение будем понимать
как конкатенацию двух строк символов – присоединение второй строки
символов к первой, например:
«a» ⋅ «b» = «ab», «b» ⋅ «a» = «ba», «ab» ⋅ «c» = «abc».
Заметим, что если среди двух сомножителей окажется хотя бы одна
пустая строка символов, то произведение будет пустой строкой.
Под сложением будем понимать объединение множеств строк сим-
волов, например:
«a» + «b» = «b» + «a» = {«a», «b»}, «ab» + «c» = {«ab», «c»}.
При этом пустые строки символов не включаются в результат объе-
динения.
Для таких операций умножения и сложения элемент матрицы S
n
(G)
на пересечении i-й строки и j-го столбца будет представлять собой мно-
жество цепей длиной n, соединяющих вершины v
i
и v
j
.
Рассмотрим распределение цепей в неориентированном графе G,
представленном на рис. 20. Матрица смежности этого графа имеет сле-
дующий вид:
1 2 3 4 5
a e 1
a b 2
S (G) = b c 3
c d 4
e d 5
Заметим, что матрица S
(G) характеризует распределение рёбер
(цепей единичной длины) в графе G. Для определения цепей длиной 2
графа G возведём эту матрицу в квадрат:
1 2 3 4 5
aa ee ab ed 1
aa bb bc ae 2
S
2
(G) = ba bb cc cd 3
de cb cc dd 4
ea dc ee dd 5
Страницы
- « первая
- ‹ предыдущая
- …
- 50
- 51
- 52
- 53
- 54
- …
- следующая ›
- последняя »
