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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 3. Арифметические свойства сильно связного графа. Циклические классы. 33
Предположим, что вершины графа разбиты на циклические клас-
сы, как описано в теореме 1. Перенумеруем вершины, присвоив пер-
вые номера вершинам из C
0
, последующие — вершинам из C
1
, и так
далее. При такой нумерации матрица смежности получает вид, ясно
отображающий циклический характер переходов из класса в класс:
A =
0 A
12
0 ... 0
0 0 A
23
... 0
.. .. .. .. ..
0 0 0 0 A
d−1,d
A
d1
0 0 0 0
. (4)
Блок A
12
содержит информацию о переходах из C
0
в C
1
, блок A
23
— о переходах из C
1
в C
2
и так далее, наконец, блок A
d1
сообщает о
дугах, ведущих из C
d−1
в C
0
. Таким образом, справедливо
Предложение 5. Для любого сильно связного графа существу-
ет такая нумерация вершин, при которой его матрица смежности
имеет блочную форму (4), где блочный порядок d равен индексу им-
примитивности графа.
Описанную выше нумерацию вершин сильно связного графа, от-
ражающую их разбиение на циклические классы и характер перехо-
дов из класса в класс, будем называть нормальной, а о соответствую-
щей матрице (4) смежности графа будем говорить, что она имеет нор-
мальный вид (нормальную форму). Если граф примитивен, то будем
считать, что его матрица смежности всегда находится в нормальной
форме.
Если матрица смежности находится в нормальной форме, то и её
cтепени имеют прозрачную блочную структуру. А именно, матрица
A
k
(k = 1, 2, . . . , d−1) содержит ровно один ненулевой блок в каждой
блочной строке и каждом блочном столбце. Ненулевые блоки занима-
ют две блочные диагонали, которые сдвигаются вправо и вверх при
увеличении степени, а при k = d сливаются в одну диагональ — глав-
ную. Точнее, матрица A
d
имеет блочно-диагональный вид:
A
d
=
A
(d)
11
A
(d)
22
.
.
.
A
(d)
dd
, где
A
(d)
11
= A
12
A
23
. . . A
d1
,
A
(d)
22
= A
23
. . . A
d1
A
12
,
. . . . . . . . . . . .
A
(d)
dd
= A
d1
A
12
. . . A
d−1,d
.
Нетрудно понять, что матрицы A
k
и A
d+k
имеют одну и ту же
блочную структуру для любого показателя k . Блочные структуры
§ 3. Арифметические свойства сильно связного графа. Циклические классы. 33


    Предположим, что вершины графа разбиты на циклические клас-
сы, как описано в теореме 1. Перенумеруем вершины, присвоив пер-
вые номера вершинам из C0 , последующие — вершинам из C1 , и так
далее. При такой нумерации матрица смежности получает вид, ясно
отображающий циклический характер переходов из класса в класс:
                                             
                        0 A12 0 ...       0
                      0     0 A23 ...    0 
                                             
                A =  ..     ..   .. ..   ..  .             (4)
                      0     0    0 0 Ad−1,d  
                       Ad1 0      0 0     0
   Блок A12 содержит информацию о переходах из C0 в C1 , блок A23
— о переходах из C1 в C2 и так далее, наконец, блок Ad1 сообщает о
дугах, ведущих из Cd−1 в C0 . Таким образом, справедливо
   Предложение 5. Для любого сильно связного графа существу-
ет такая нумерация вершин, при которой его матрица смежности
имеет блочную форму (4), где блочный порядок d равен индексу им-
примитивности графа.
    Описанную выше нумерацию вершин сильно связного графа, от-
ражающую их разбиение на циклические классы и характер перехо-
дов из класса в класс, будем называть нормальной, а о соответствую-
щей матрице (4) смежности графа будем говорить, что она имеет нор-
мальный вид (нормальную форму). Если граф примитивен, то будем
считать, что его матрица смежности всегда находится в нормальной
форме.
    Если матрица смежности находится в нормальной форме, то и её
cтепени имеют прозрачную блочную структуру. А именно, матрица
Ak (k = 1, 2, . . . , d−1) содержит ровно один ненулевой блок в каждой
блочной строке и каждом блочном столбце. Ненулевые блоки занима-
ют две блочные диагонали, которые сдвигаются вправо и вверх при
увеличении степени, а при k = d сливаются в одну диагональ — глав-
ную. Точнее, матрица Ad имеет блочно-диагональный вид:
          (d)                        
                                              (d)
             A11                             A11 = A12 A23 . . .  Ad1 ,
                      (d)                   (d)
                     A22                   A = A23       . . . Ad1 A12 ,
    Ad =                  .           , где 22
                            . .             ...   ...    ...     ...
                                  (d)         (d)
                                 Add         Add = Ad1 A12 . . . Ad−1,d .
   Нетрудно понять, что матрицы Ak и Ad+k имеют одну и ту же
блочную структуру для любого показателя k. Блочные структуры

Страницы