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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

30 Глава 2. Ориентированные графы
Следствие 2. Любая приводимая комплексная матрица неко-
торым перестановочным подобием приводится к нормальной фор-
ме.
Полезность нормальной формы приводимой комплексной матри-
цы, в частности, состоит в том, что вычисление её собственных зна-
чений сводится к вычислению собственных значений диагональных
блоков. Но наибольшее применение эта форма имеет в теории неот-
рицательных матриц (то есть, матриц с вещественными неотрица-
тельными элементами) и теории цепей Маркова.
Это объясняется, например, следующим легко доказываемым
фактом. Обозначим булевский портрет матрицы C символом Sg(C).
Предложение 2. Если P, Q — неотрицательные матрицы од-
ного порядка, то
Sg(P + Q) = Sg(P ) + Sg(Q),
Sg(P Q) = Sg(P )Sg(Q), следовательно, Sg(P
k
) = (Sg(P ))
k
.
Таким образом, если мы желаем знать, как расположены ненуле-
вые элементы в сумме (произведении) неотрицательных матриц, то
для этого достаточно вычислить сумму (произведение) их булевских
портретов.
Задача 1. Докажите, что в сильно связном турнире с n ≥ 3 вер-
шинами каждая вершина принадлежит контуру длины 3. Является
ли конденсация турнира турниром?
Задача 2. Опишите орграфы, для которых матрица смежности
A — нильпотентная матрица. Какова нормальная форма матрицы
смежности в этом случае? В частности, для каких графов A
2
= 0?
Задача 3. Опишите орграфы, для которых булева матрица
смежности A — идемпотентная матрица, то есть, A
2
= A. Какова
нормальная форма матрицы смежности в этом случае?
§ 3. Арифметические свойства сильно связного графа.
Циклические классы.
Пусть дан сильно связный орграф с вершинами 1, 2, . . . , n. Обо-
значим через N
ij
множество длин всевозможных (i, j)-путей. В част-
ности, N
ii
— множество длин контуров, проходящих через вершину i.
Пусть d
i
— наибольший общий делитель чисел из N
ii
.
30                                       Глава 2. Ориентированные графы


    Следствие 2. Любая приводимая комплексная матрица неко-
торым перестановочным подобием приводится к нормальной фор-
ме.
   Полезность нормальной формы приводимой комплексной матри-
цы, в частности, состоит в том, что вычисление её собственных зна-
чений сводится к вычислению собственных значений диагональных
блоков. Но наибольшее применение эта форма имеет в теории неот-
рицательных матриц (то есть, матриц с вещественными неотрица-
тельными элементами) и теории цепей Маркова.
   Это объясняется, например, следующим легко доказываемым
фактом. Обозначим булевский портрет матрицы C символом Sg(C).
    Предложение 2. Если P, Q — неотрицательные матрицы од-
ного порядка, то
                     Sg(P + Q) = Sg(P ) + Sg(Q),

      Sg(P Q) = Sg(P )Sg(Q), следовательно, Sg(P k ) = (Sg(P ))k .
   Таким образом, если мы желаем знать, как расположены ненуле-
вые элементы в сумме (произведении) неотрицательных матриц, то
для этого достаточно вычислить сумму (произведение) их булевских
портретов.
    Задача 1. Докажите, что в сильно связном турнире с n ≥ 3 вер-
шинами каждая вершина принадлежит контуру длины 3. Является
ли конденсация турнира турниром?
   Задача 2. Опишите орграфы, для которых матрица смежности
A — нильпотентная матрица. Какова нормальная форма матрицы
смежности в этом случае? В частности, для каких графов A2 = 0?
   Задача 3. Опишите орграфы, для которых булева матрица
смежности A — идемпотентная матрица, то есть, A2 = A. Какова
нормальная форма матрицы смежности в этом случае?

     § 3. Арифметические свойства сильно связного графа.
                      Циклические классы.

   Пусть дан сильно связный орграф с вершинами 1, 2, . . . , n. Обо-
значим через Nij множество длин всевозможных (i, j)-путей. В част-
ности, Nii — множество длин контуров, проходящих через вершину i.
Пусть di — наибольший общий делитель чисел из Nii .

Страницы