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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

36 Глава 2. Ориентированные графы
булевых матриц утверждает, что при k ≥ k
0
каждый блок A
(k)
pq
мат-
рицы A
k
либо целиком состоит из единиц, либо целиком из нулей.
1)
Матрицы такого типа полностью определяются расположением
ненулевых блоков, для них совпадение блочных структур означает
равенство самих матриц. Поэтому, начиная с A
k
0
, в последователь-
ности степеней матрицы A происходит периодическое повторение с
периодом, равным d. Мы пришли к следующему выводу.
Теорема 3. Пусть A — нормальная форма матрицы смежно-
сти сильно связного графа. Тогда при k ≥ k
0
ненулевые блоки мат-
рицы A
k
целиком состоят из единиц. Число k
0
равно предпериоду
матрицы A, а индекс импримитивности d графа — периоду этой
матрицы.
Поскольку любая неприводимая булева матрица A может рас-
сматриваться как матрица смежности сильно связного графа, тео-
рема 3 допускает следующую переформулировку.
Следствие 1. Предпериод k
0
неприводимой булевой матрицы
есть наименьшее число, такое, что для графа этой матрицы при
k ≥ k
0
верно утверждение теоремы 2. Период неприводимой буле-
вой матрицы совпадает с индексом импримитивности графа этой
матрицы.
Дадим определение нормальной формы неприводимой булевой
матрицы, не использующее явно графовых терминов. Скажем, что
неприводимая булева матрица находится в нормальной форме, если
она имеет блочный вид (4), причём ненулевые блоки в степенях этой
матрицы, начиная с некоторой степени, целиком состоят из единиц.
Упражнение 2. Докажите, что неприводимая булева матрица
блочного вида (4) находится в нормальной форме в точности тогда,
когда её блочный порядок равен её периоду.
Как и в случае приводимых матриц, полезно распространить
определение нормальной формы на комплексные матрицы и считать,
что неприводимая комплексная матрица имеет нормальную форму,
если её портрет имеет нормальную форму. Стандартным рассужде-
нием, как в §2, обосновывается
Предложение 7. Любая неприводимая булева (комплексная)
матрица некоторым перестановочным подобием приводится к нор-
мальной форме.
Из теоремы 3 и предложения 2 §2 следует
1)
Точнее, A
(k)
pq
= I ⇔ p + k ≡ q(mod d).
36                                          Глава 2. Ориентированные графы


                                                                  (k)
булевых матриц утверждает, что при k ≥ k0 каждый блок Apq мат-
рицы Ak либо целиком состоит из единиц, либо целиком из нулей.1)
   Матрицы такого типа полностью определяются расположением
ненулевых блоков, для них совпадение блочных структур означает
равенство самих матриц. Поэтому, начиная с Ak0 , в последователь-
ности степеней матрицы A происходит периодическое повторение с
периодом, равным d. Мы пришли к следующему выводу.
   Теорема 3. Пусть A — нормальная форма матрицы смежно-
сти сильно связного графа. Тогда при k ≥ k0 ненулевые блоки мат-
рицы Ak целиком состоят из единиц. Число k0 равно предпериоду
матрицы A, а индекс импримитивности d графа — периоду этой
матрицы.
   Поскольку любая неприводимая булева матрица A может рас-
сматриваться как матрица смежности сильно связного графа, тео-
рема 3 допускает следующую переформулировку.
   Следствие 1. Предпериод k0 неприводимой булевой матрицы
есть наименьшее число, такое, что для графа этой матрицы при
k ≥ k0 верно утверждение теоремы 2. Период неприводимой буле-
вой матрицы совпадает с индексом импримитивности графа этой
матрицы.
   Дадим определение нормальной формы неприводимой булевой
матрицы, не использующее явно графовых терминов. Скажем, что
неприводимая булева матрица находится в нормальной форме, если
она имеет блочный вид (4), причём ненулевые блоки в степенях этой
матрицы, начиная с некоторой степени, целиком состоят из единиц.
   Упражнение 2. Докажите, что неприводимая булева матрица
блочного вида (4) находится в нормальной форме в точности тогда,
когда её блочный порядок равен её периоду.
    Как и в случае приводимых матриц, полезно распространить
определение нормальной формы на комплексные матрицы и считать,
что неприводимая комплексная матрица имеет нормальную форму,
если её портрет имеет нормальную форму. Стандартным рассужде-
нием, как в §2, обосновывается
   Предложение 7. Любая неприводимая булева (комплексная)
матрица некоторым перестановочным подобием приводится к нор-
мальной форме.
       Из теоремы 3 и предложения 2 §2 следует
 1)            (k)
      Точнее, Apq = I ⇔ p + k ≡ q(mod d).

Страницы