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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 5. Некоторые алгоритмические вопросы 39
сы, следовательно, в разные вершины. Это видно из циклического
характера движения из класса в класс, описанного в теореме 1 §3. ¤
Лемма 1. Если из двух вершин можно синхронно перейти в
одну вершину за k шагов, то это можно сделать и за k + 1 шагов.
Д о к а з а т е л ь с т в о. Пути длины k, ведущие в общую
вершину, можно продолжить, добавив к ним любую дугу. ¤
Переведём лемму 1 на язык булевой матрицы смежности A. На-
личие путей длины k из вершин i, j в некоторую общую вершину
записывается так:
a
(k)
il
= a
(k)
jl
= 1 для некоторого l, или, равносильно, (A
k
(A
k
)
T
)
ij
= 1.
Введём сокращение A
k
(A
k
)
T
= B
k
. Лемма 1 тогда означает, что
(B
k
)
ij
= 1 ⇒ (B
k+1
)
ij
= 1. Выразим это свойство как неравенство
B
k
≤ B
k+1
. Рассмотрим цепочку неравенств
B
1
≤ . . . ≤ B
k
≤ . . . .
В этой цепочке каждая матрица получается из предыдущей по прави-
лу B
k+1
= AB
k
A
T
. Поэтому как только в цепочке встретятся равные
матрицы, то и дальше будут только равенства. А поскольку матрицы
B
k
— симметричные и с единицами на главной диагонали, то раз-
личных матриц в цепочке не больше, чем
n(n−1)
2
. Отсюда вытекает
критерий, позволяющий вычислить циклические классы с помощью
умножения булевых матриц.
Предложение 2. Вершины i, j сильно связного графа с матри-
цей смежности A принадлежат одному циклическому классу то-
гда и только тогда, когда (ij)-элемент матрицы A
n(n−1)
2
(A
n(n−1)
2
)
T
равен 1.
Перейдём ко второму вопросу. Как видно из теоремы 3 §3, пара-
метр k
0
сильно связного графа с матрицей смежности A равен предпе-
риоду последовательноcти A, A
2
, . . . . Ясно, что для любой матрицы
порядка n это число не больше числа 2
n
2
всех булевых n × n-матриц.
Но это — грубая оценка. Известна более точная оценка:
Предложение 3. Для любой булевой матрицы порядка n
k
0
≤
n
2
d
− 2n + 3d.
Достаточно сложное доказательство этого неравенства мы не при-
водим, однако выведем оценку для k
0
в важном частном случае, когда
матрица примитивна.
§ 5. Некоторые алгоритмические вопросы                             39


сы, следовательно, в разные вершины. Это видно из циклического
характера движения из класса в класс, описанного в теореме 1 §3. ¤
    Лемма 1. Если из двух вершин можно синхронно перейти в
одну вершину за k шагов, то это можно сделать и за k + 1 шагов.
    Д о к а з а т е л ь с т в о. Пути длины k, ведущие в общую
вершину, можно продолжить, добавив к ним любую дугу. ¤
    Переведём лемму 1 на язык булевой матрицы смежности A. На-
личие путей длины k из вершин i, j в некоторую общую вершину
записывается так:
 (k)    (k)
ail = ajl = 1 для некоторого l, или, равносильно, (Ak (Ak )T )ij = 1.
Введём сокращение Ak (Ak )T = Bk . Лемма 1 тогда означает, что
(Bk )ij = 1 ⇒ (Bk+1 )ij = 1. Выразим это свойство как неравенство
Bk ≤ Bk+1 . Рассмотрим цепочку неравенств
                        B1 ≤ . . . ≤ Bk ≤ . . . .
В этой цепочке каждая матрица получается из предыдущей по прави-
лу Bk+1 = ABk AT . Поэтому как только в цепочке встретятся равные
матрицы, то и дальше будут только равенства. А поскольку матрицы
Bk — симметричные и с единицами на главной диагонали, то раз-
личных матриц в цепочке не больше, чем n(n−1)   2 . Отсюда вытекает
критерий, позволяющий вычислить циклические классы с помощью
умножения булевых матриц.
    Предложение 2. Вершины i, j сильно связного графа с матри-
цей смежности A принадлежат одному циклическому классу то-
                                                        n(n−1) n(n−1)
гда и только тогда, когда (ij)-элемент матрицы A 2 (A 2 )T
равен 1.
    Перейдём ко второму вопросу. Как видно из теоремы 3 §3, пара-
метр k0 сильно связного графа с матрицей смежности A равен предпе-
риоду последовательноcти A, A2 , . . . . Ясно, что для любой матрицы
                                          2
порядка n это число не больше числа 2n всех булевых n × n-матриц.
Но это — грубая оценка. Известна более точная оценка:
    Предложение 3. Для любой булевой матрицы порядка n
                               n2
                          k0 ≤    − 2n + 3d.
                               d
   Достаточно сложное доказательство этого неравенства мы не при-
водим, однако выведем оценку для k0 в важном частном случае, когда
матрица примитивна.

Страницы