Дискретная математика: графы и автоматы. Альпин Ю.А - 7 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 1. Первые понятия теории графов 7
Упражнение 1. Пусть V
1
, . . . , V
s
— компоненты графа. Пере-
нумеруем сначала вершины из V
1
, затем вершины из V
2
и так далее.
Докажите, что при такой нумерации матрица смежности графа имеет
блочно-диагональный вид:
A
1
.
.
.
A
s
,
где A
i
, i = 1, . . . , s, — матрицы смежности компонент.
Элементы степеней матрицы смежности имеют прозрачный гра-
фовый смысл.
Предложение 1. Если A — матрица смежности графа, то
(ij)-элемент a
(k)
ij
матрицы A
k
равен количеству (i, j)-маршрутов
длины k в этом графе.
Д о к а з а т е л ь с т в о. Для элементов k-й степени матрицы A
имеет место равенство
a
(k)
ij
=
X
a
il
1
a
l
1
l
2
. . . a
l
k−1
,j
, (2)
где суммирование производится по всевозможным последовательно-
стям индексов l
1
, l
2
, . . . , l
k−1
. (Формула (2) выводится индукцией по
параметру k.) Очевидно, произведение a
il
1
a
l
1
l
2
. . . a
l
k−1
j
равно единице,
если существует маршрут i, l
1
, l
2
, . . . , l
k−1
, j, и равно нулю в против-
ном случае. Отсюда и следует утверждение. ¤
Если нам требуется знать не количество (i, j)-маршрутов, а лишь
выяснить, существует ли хотя бы один маршрут, то удобнее считать
символы 0 и 1 не натуральными числами, а элементами двухэлемент-
ной булевой алгебры, в которой сложение и умножение задаются сле-
дующими таблицами:
⊕ 0 1
0 0 1
1 1 1
,
¯ 0 1
0 0 0
1 0 1
.
Можно непосредственно проверить, что операции в этой двухэле-
ментной алгебре обладают привычными свойствами ассоциативности,
коммутативности и дистрибутивности умножения относительно сло-
жения, но относительно сложения булева алгебра не является группой
(вычитание не определено).
Для упрощения записи вместо a⊕b и a¯b мы будем писать a+b и
ab, так как из контекста видно, когда действия происходят в булевой
алгебре.
§ 1. Первые понятия теории графов                                          7


   Упражнение 1. Пусть V1 , . . . , Vs — компоненты графа. Пере-
нумеруем сначала вершины из V1 , затем вершины из V2 и так далее.
Докажите, что при такой нумерации матрица смежности графа имеет
блочно-диагональный вид:
                                     
                           A1
                             ...     ,
                                   As
где Ai , i = 1, . . . , s, — матрицы смежности компонент.
    Элементы степеней матрицы смежности имеют прозрачный гра-
фовый смысл.
    Предложение 1. Если A — матрица смежности графа, то
                   (k)
(ij)-элемент aij матрицы Ak равен количеству (i, j)-маршрутов
длины k в этом графе.
    Д о к а з а т е л ь с т в о. Для элементов k-й степени матрицы A
имеет место равенство
                             (k)
                                  X
                            aij =   ail1 al1 l2 . . . alk−1 ,j ,  (2)
где суммирование производится по всевозможным последовательно-
стям индексов l1 , l2 , . . . , lk−1 . (Формула (2) выводится индукцией по
параметру k.) Очевидно, произведение ail1 al1 l2 . . . alk−1 j равно единице,
если существует маршрут i, l1 , l2 , . . . , lk−1 , j, и равно нулю в против-
ном случае. Отсюда и следует утверждение. ¤
    Если нам требуется знать не количество (i, j)-маршрутов, а лишь
выяснить, существует ли хотя бы один маршрут, то удобнее считать
символы 0 и 1 не натуральными числами, а элементами двухэлемент-
ной булевой алгебры, в которой сложение и умножение задаются сле-
дующими таблицами:
                        ⊕ 0 1       ¯ 0 1
                        0 0 1 , 0 0 0 .
                        1 1 1       1 0 1
    Можно непосредственно проверить, что операции в этой двухэле-
ментной алгебре обладают привычными свойствами ассоциативности,
коммутативности и дистрибутивности умножения относительно сло-
жения, но относительно сложения булева алгебра не является группой
(вычитание не определено).
    Для упрощения записи вместо a⊕b и a¯b мы будем писать a+b и
ab, так как из контекста видно, когда действия происходят в булевой
алгебре.

Страницы