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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

32 Глава 2. Ориентированные графы
Предложение 4. Пусть i ∼ u. Тогда t
ij
= t
uv
⇔ j ∼ v.
Д о к а з а т е л ь с т в о. Из (1) выводится сравнение
t
ij
+ t
jv
+ t
vu
≡ t
iu
≡ 0 (mod d). (3)
Если теперь t
ij
= t
uv
, то
t
ij
+ t
vu
≡ t
uv
+ t
vu
≡ t
uu
≡ 0 (mod d),
следовательно, t
jv
= 0, то есть, j ∼ v.
Обратно, подставляя t
jv
= 0 в (3), получаем
t
ij
+ t
vu
≡ 0 (mod d),
а поскольку
t
uv
+ t
vu
≡ 0 (mod d),
то t
ij
= t
uv
. ¤
На языке классов отношения ∼ предложение 4 означает, что
класс, в который приводит путь, однозначно определяется классом,
в котором лежит начало пути, а также остатком от деления длины
пути на число d. Если эти остатки для двух путей различны, то пути
приводят в различные классы. Отсюда следует, что имеется ровно d
классов отношения ∼ и что переходы из класса в класс совершаются
циклически. Произведём нормальную нумерацию классов: выберем
произвольно некоторый класс и обозначим его C
0
. Через C
1
обозна-
чим тот класс, в который ведут дуги из C
0
, через C
2
— класс, в ко-
торый ведут дуги из C
1
и так далее. Из класса C
d−1
все дуги ведут в
C
0
. Таким образом, доказана
Теорема 1. Если НОД длин (простых) контуров сильно связ-
ного графа равен d, то множество вершин можно так разбить на
d классов
C
0
, C
1
, ..., C
d−1
,
что дуги с началом в C
0
ведут в C
1
, дуги с началом в C
1
ведут в
C
2
и т.д., наконец, дуги с началом в C
d−1
ведут в C
0
.
Классы эквивалентности отношения ∼ называются циклически-
ми классами.
Упражнение 1. Докажите, что факторграф сильно связного
графа по разбиению на циклические классы есть простой контур.
Разумеется, картина, описанная в теореме 1, содержательна лишь
при d > 1. Число d циклических классов называется индексом им-
примитивности сильно связного графа. При d > 1 граф называется
импримитивным, а при d = 1 — примитивным.
32                                       Глава 2. Ориентированные графы


     Предложение 4. Пусть i ∼ u. Тогда tij = tuv ⇔ j ∼ v.
     Д о к а з а т е л ь с т в о. Из (1) выводится сравнение
                   tij + tjv + tvu ≡ tiu ≡ 0 (mod d).               (3)
Если теперь tij = tuv , то
                tij + tvu ≡ tuv + tvu ≡ tuu ≡ 0 (mod d),
следовательно, tjv = 0, то есть, j ∼ v.
   Обратно, подставляя tjv = 0 в (3), получаем
                         tij + tvu ≡ 0 (mod d),
а поскольку
                         tuv + tvu ≡ 0 (mod d),
то tij = tuv . ¤
     На языке классов отношения ∼ предложение 4 означает, что
класс, в который приводит путь, однозначно определяется классом,
в котором лежит начало пути, а также остатком от деления длины
пути на число d. Если эти остатки для двух путей различны, то пути
приводят в различные классы. Отсюда следует, что имеется ровно d
классов отношения ∼ и что переходы из класса в класс совершаются
циклически. Произведём нормальную нумерацию классов: выберем
произвольно некоторый класс и обозначим его C0 . Через C1 обозна-
чим тот класс, в который ведут дуги из C0 , через C2 — класс, в ко-
торый ведут дуги из C1 и так далее. Из класса Cd−1 все дуги ведут в
C0 . Таким образом, доказана
     Теорема 1. Если НОД длин (простых) контуров сильно связ-
ного графа равен d, то множество вершин можно так разбить на
d классов
                            C0 , C1 , ..., Cd−1 ,
что дуги с началом в C0 ведут в C1 , дуги с началом в C1 ведут в
C2 и т.д., наконец, дуги с началом в Cd−1 ведут в C0 .
     Классы эквивалентности отношения ∼ называются циклически-
ми классами.
     Упражнение 1. Докажите, что факторграф сильно связного
графа по разбиению на циклические классы есть простой контур.
     Разумеется, картина, описанная в теореме 1, содержательна лишь
при d > 1. Число d циклических классов называется индексом им-
примитивности сильно связного графа. При d > 1 граф называется
импримитивным, а при d = 1 — примитивным.

Страницы