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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

34 Глава 2. Ориентированные графы
степеней A меняются периодически с периодом d, так что блочная
структура матрицы A
k
, k = ld + r (0 ≤ r ≤ d − 1), совпадает с
блочной структурой A
r
. Но что происходит внутри блоков? Чтобы
выяснить это, продолжим изучение арифметических свойств сильно
связного графа.
Два контура длины l и m, проходящие через вершину i, можно
соединить в один контур длины l + m, проходящий через i. Следо-
вательно, если l, m ∈ N
ii
, то и l + m ∈ N
ii
, то есть, N
ii
образует
полугруппу относительно сложения. Докажем полезное свойство та-
ких числовых множеств.
Лемма 1. Пусть множество M натуральных чисел содержит
сумму любых двух своих элементов, и d — наибольший общий де-
литель чисел из M. Тогда M содержит все достаточно большие
числа, кратные d.
Замечание 2. Выражение “все достаточно большие числа” озна-
чает: все числа, начиная с некоторого числа.
Д о к а з а т е л ь с т в о. Существуют такие числа a
1
, . . . , a
k
∈ M,
что d равно их НОД. Из элементарной теории делимости известно
1)
,
что НОД набора целых чисел можно представить в виде
d = c
1
a
1
+ c
2
a
2
+ ... + c
k
a
k
,
где c
1
, . . . , c
k
— подходящие целые числа. Сложив отдельно положи-
тельные и отрицательные члены этой комбинации, получим представ-
ление
d = b − c, b, c ∈ M.
Теперь рассмотрим число h, кратное d и записанное в виде
h = qc + r, 0 ≤ r ≤ c − 1.
Поскольку h и c делятся на d, то r тоже делится, значит r = fd,
0 ≤ f ≤ c − 1. Следовательно,
h = qc + r = qc + fd = qc + f(b − c) = (q − f)c + fb.
Если h ≥ (c − 1)c, то q ≥ c−1, а это значит, что q − f ≥ 0 и h ∈ M. ¤
Предложение 6. Пусть индекс импримитивности графа ра-
вен d. Найдется такое число q
0
, что при любом q > q
0
для любых
вершин i, j существует (i, j)-путь длины qd + t
ij
.
1)
См., напр., Калужнин Л.А. Введение в общую алгебру. — М.: Наука, 1973.
34                                                   Глава 2. Ориентированные графы


степеней A меняются периодически с периодом d, так что блочная
структура матрицы Ak , k = ld + r (0 ≤ r ≤ d − 1), совпадает с
блочной структурой Ar . Но что происходит внутри блоков? Чтобы
выяснить это, продолжим изучение арифметических свойств сильно
связного графа.
    Два контура длины l и m, проходящие через вершину i, можно
соединить в один контур длины l + m, проходящий через i. Следо-
вательно, если l, m ∈ Nii , то и l + m ∈ Nii , то есть, Nii образует
полугруппу относительно сложения. Докажем полезное свойство та-
ких числовых множеств.
   Лемма 1. Пусть множество M натуральных чисел содержит
сумму любых двух своих элементов, и d — наибольший общий де-
литель чисел из M . Тогда M содержит все достаточно большие
числа, кратные d.
   Замечание 2. Выражение “все достаточно большие числа” озна-
чает: все числа, начиная с некоторого числа.
   Д о к а з а т е л ь с т в о. Существуют такие числа a1 , . . . , ak ∈ M ,
что d равно их НОД. Из элементарной теории делимости известно1) ,
что НОД набора целых чисел можно представить в виде
                             d = c1 a1 + c2 a2 + ... + ck ak ,
где c1 , . . . , ck — подходящие целые числа. Сложив отдельно положи-
тельные и отрицательные члены этой комбинации, получим представ-
ление
                             d = b − c, b, c ∈ M.
Теперь рассмотрим число h, кратное d и записанное в виде
                             h = qc + r,      0 ≤ r ≤ c − 1.
Поскольку h и c делятся на d, то r тоже делится, значит r = f d,
0 ≤ f ≤ c − 1. Следовательно,
            h = qc + r = qc + f d = qc + f (b − c) = (q − f )c + f b.
Если h ≥ (c − 1)c, то q ≥ c − 1, а это значит, что q − f ≥ 0 и h ∈ M. ¤
    Предложение 6. Пусть индекс импримитивности графа ра-
вен d. Найдется такое число q0 , что при любом q > q0 для любых
вершин i, j существует (i, j)-путь длины qd + tij .
 1)
      См., напр., Калужнин Л.А. Введение в общую алгебру. — М.: Наука, 1973.

Страницы