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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 3. Арифметические свойства сильно связного графа. Циклические классы. 35
Д о к а з а т е л ь с т в о . Согласно лемме 1 для каждого i найдется
такое l
i
, что ld ∈ N
ii
при всех l > l
i
. Положим l
0
= max
i
l
i
. Тогда
ld ∈ N
ii
при всех l > l
0
и любом i (напомним, что по предложению 1
НОД множеств N
ii
совпадают и равны d).
Рассмотрим простой (i, j)-путь. Его длина может быть представ-
лена в виде q
0
d + t
ij
, где q
0
зависит от i, j, но ввиду простоты пути
всегда не больше, чем n. Ясно, что при любом q > l
0
+ q
0
существует
(i, j)-путь длины qd+t
ij
. Учитывая неравенство q
0
≤ n, окончательно
получаем: для любых вершин i, j и любого q > q
0
= n + l
0
существует
(i, j)-путь длины qd + t
ij
. ¤
Ниже значок [i] употребляется для обозначения циклического
класса, содержащего вершину i.
Теорема 2. Существует такое число k
0
, что для любого k ≥ k
0
и любых классов [i], [j] верно одно из двух утверждений:
1) из любой вершины u класса [i] можно перейти за k шагов в
любую вершину v класса [j],
2) ни из какой вершины u ∈ [i] невозможен переход за k шагов
ни в какую вершину v ∈ [j].
Первое случится, если k ≡ t
ij
(mod d), второе — в противопо-
ложном случае.
Д о к а з а т е л ь с т в о. Прежде всего заметим, что t
uv
= t
ij
в
силу предложения 4. Теперь для доказательства первого утверждения
достаточно положить k
0
= q
0
d и применить предложение 6. Второе
утверждение вытекает непосредственно из определения числа t
ij
. ¤
Замечание 3. В дальнейшем обозначение k
0
закрепим за наи-
меньшим из чисел, существование которых доказано в теореме 2.
Рассмотрим последовательность степеней произвольной булев-
ской матрицы A. Поскольку множество булевских матриц порядка n
конечно, то существует наименьшее p с тем свойством, что A
p
= A
p+r
для некоторого r > 0. Число p называется предпериодом матрицы A,
а наименьшее r с указанным свойством — её периодом. Таким обра-
зом, последовательность степеней матрицы A имеет вид
A, ..., A
p−1
|A
p
, ..., A
p+r−1
|A
p
, ..., A
p+r−1
|...
Вернёмся к рассмотрению последовательности степеней матрицы
смежности. Мы остановились на том, что при нормальной нумерации
вершин графа степени его матрицы смежности имеют периодически
повторяющуюся блочную структуру. Теорема 2 в переводе на язык
§ 3. Арифметические свойства сильно связного графа. Циклические классы. 35


   Д о к а з а т е л ь с т в о . Согласно лемме 1 для каждого i найдется
такое li , что ld ∈ Nii при всех l > li . Положим l0 = max li . Тогда
                                                                       i
ld ∈ Nii при всех l > l0 и любом i (напомним, что по предложению 1
НОД множеств Nii совпадают и равны d).
     Рассмотрим простой (i, j)-путь. Его длина может быть представ-
лена в виде q 0 d + tij , где q 0 зависит от i, j, но ввиду простоты пути
всегда не больше, чем n. Ясно, что при любом q > l0 + q 0 существует
(i, j)-путь длины qd+tij . Учитывая неравенство q 0 ≤ n, окончательно
получаем: для любых вершин i, j и любого q > q0 = n + l0 существует
(i, j)-путь длины qd + tij . ¤
     Ниже значок [i] употребляется для обозначения циклического
класса, содержащего вершину i.
   Теорема 2. Существует такое число k0 , что для любого k ≥ k0
и любых классов [i], [j] верно одно из двух утверждений:
   1) из любой вершины u класса [i] можно перейти за k шагов в
любую вершину v класса [j],
   2) ни из какой вершины u ∈ [i] невозможен переход за k шагов
ни в какую вершину v ∈ [j].
   Первое случится, если k ≡ tij (mod d), второе — в противопо-
ложном случае.
   Д о к а з а т е л ь с т в о. Прежде всего заметим, что tuv = tij в
силу предложения 4. Теперь для доказательства первого утверждения
достаточно положить k0 = q0 d и применить предложение 6. Второе
утверждение вытекает непосредственно из определения числа tij . ¤
   Замечание 3. В дальнейшем обозначение k0 закрепим за наи-
меньшим из чисел, существование которых доказано в теореме 2.
    Рассмотрим последовательность степеней произвольной булев-
ской матрицы A. Поскольку множество булевских матриц порядка n
конечно, то существует наименьшее p с тем свойством, что Ap = Ap+r
для некоторого r > 0. Число p называется предпериодом матрицы A,
а наименьшее r с указанным свойством — её периодом. Таким обра-
зом, последовательность степеней матрицы A имеет вид
               A, ..., Ap−1 |Ap , ..., Ap+r−1 |Ap , ..., Ap+r−1 |...
   Вернёмся к рассмотрению последовательности степеней матрицы
смежности. Мы остановились на том, что при нормальной нумерации
вершин графа степени его матрицы смежности имеют периодически
повторяющуюся блочную структуру. Теорема 2 в переводе на язык

Страницы