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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 4. Примитивные графы и матрицы 37
Предложение 8. Если A — нормальная форма неприводимой
неотрицательной матрицы, то, начиная с некоторого показателя
k
0
, ненулевые блоки в матрице A
k
состоят из положительных чи-
сел.
Пример 1. Рассмотрим граф
Рис. 5
Он содержит три простых контура длины 3, 6, 6, следователь-
но, число циклических классов d равно 3. Пользуясь определени-
ем (2), вычисляем циклические классы: C
0
= {1, 4}, C
1
= {2, 5},
C
2
= {3, 6, 7}. После перенумерации 1 7→ 1, 4 7→ 2, 2 7→ 3, 5 7→
4, 3 7→ 5, 6 7→ 6, 7 7→ 7 матрица смежности приобретает нормаль-
ную форму
A =
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 1 1
0 0 0 0 0 1 0
0 1 0 0 0 0 0
1 0 0 0 0 0 0
0 1 0 0 0 0 0
.
Непосредственные вычисления показывают, что её предпериод k
0
ра-
вен 6. Общий способ вычисления циклических классов и оценка свер-
ху для предпериода k
0
произвольной булевой матрицы приведены в
§5.
§ 4. Примитивные графы и матрицы
Примитивный граф определён как сильно связный граф, у ко-
торого НОД длин контуров равен единице. Разумеется, доказанные
предыдущем параграфе теоремы верны и для примитивных графов,
§ 4. Примитивные графы и матрицы                               37


     Предложение 8. Если A — нормальная форма неприводимой
неотрицательной матрицы, то, начиная с некоторого показателя
k0 , ненулевые блоки в матрице Ak состоят из положительных чи-
сел.
   Пример 1. Рассмотрим граф




                                   Рис. 5


    Он содержит три простых контура длины 3, 6, 6, следователь-
но, число циклических классов d равно 3. Пользуясь определени-
ем (2), вычисляем циклические классы: C0 = {1, 4}, C1 = {2, 5},
C2 = {3, 6, 7}. После перенумерации 1 7→ 1, 4 7→ 2, 2 7→ 3, 5 7→
4, 3 7→ 5, 6 7→ 6, 7 7→ 7 матрица смежности приобретает нормаль-
ную форму                                 
                           0 0 1 0 0 0 0
                         0 0 0 1 0 0 0
                                          
                         0 0 0 0 1 1 1
                                          
                     A =  0 0 0 0 0 1 0 .
                         0 1 0 0 0 0 0
                                          
                         1 0 0 0 0 0 0
                           0 1 0 0 0 0 0
Непосредственные вычисления показывают, что её предпериод k0 ра-
вен 6. Общий способ вычисления циклических классов и оценка свер-
ху для предпериода k0 произвольной булевой матрицы приведены в
§5.

             § 4. Примитивные графы и матрицы

   Примитивный граф определён как сильно связный граф, у ко-
торого НОД длин контуров равен единице. Разумеется, доказанные
предыдущем параграфе теоремы верны и для примитивных графов,

Страницы