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

§ 3. Арифметические свойства сильно связного графа. Циклические классы. 31


   Предложение 1. di = dj для всех i, j.
    Д о к а з а т е л ь с т в о. Если k ∈ Nii , l ∈ Nij , m ∈ Nji ,
то существуют контуры длины k + l + m и l + m, проходящие через
вершину j. Следовательно,
             k + l + m ≡ 0 (mod dj ), l + m ≡ 0 (mod dj ),
и потому k ≡ 0 (mod dj ). Мы доказали, что dj делит произвольное
число k из Nii , значит, dj ≤ di . Меняя в этом рассуждении i и j
местами, получаем di ≤ dj . Значит, di = dj . ¤
   Итак, согласно доказанному, число d = di равно НОД длин всех
контуров графа и, одновременно, для любой вершины i равно НОД
длин контуров, проходящих через i.
   Замечание 1. Согласно лемме 1 §2 каждый контур является
простым или содержит простые контуры, поэтому его длина равна
сумме длин простых контуров. Отсюда следует, что число d равно
НОД длин простых контуров графа.
   Поскольку множество простых контуров конечно, это замечание
существенно упрощает вычисление параметра d.
     Предложение 2. Для любых вершин i, j длины различных
(i, j)-путей сравнимы по модулю d.
   Д о к а з а т е л ь с т в о. Пусть k, l ∈ Nij , m ∈ Nji . Тогда
k + m, l + m ∈ Nii , значит,
     k + m ≡ 0 (mod d), l + m ≡ 0 (mod d) ⇒ k ≡ l (mod d). ¤
    Обозначим через tij (0 ≤ tij ≤ d − 1) остаток от деления на d
длины любого из (i, j)-путей.
    Из элементарных свойств делимости целых чисел следует полез-
ное сравнение
                       tik + tkj ≡ tij (mod d).               (1)
   Введём бинарное отношение ∼ на множестве вершин:

                            i ∼ j ⇔ tij = 0,                          (2)
то есть, i ∼ j , если длины всех (i, j)-путей кратны d.
   Предложение 3. Отношение ∼ является отношением экви-
валентности.
   Доказательство рекомендуем как упражнение.