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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

38 Глава 2. Ориентированные графы
но их утверждения либо становятся тривиальными, либо приобрета-
ют настолько специальный вид, что заслуживают отдельных форму-
лировок. Мы приведём эти формулировки, а читателям рекомендуем
перечитать предыдущий параграф и обдумать, во что превращают-
ся содержащиеся в нём определения и утверждения в случае, когда
индекс импримитивности равен единице.
Предложение 1. Граф примитивен тогда и только тогда, ко-
гда существует такое число q
0
, что при k > q
0
из любой вершины
можно перейти в любую другую вершину за k шагов.
Неприводимая булева матрица называется примитивной, если её
период равен 1. Другими словами, булева матрица примитивна, ес-
ли примитивен её граф. Простейший пример — матрица I. Матрица
с неотрицательными элементами называется примитивной, если при-
митивен её булевский портрет, или, эквивалентно, если примитивен
её граф.
Предложение 2. Булева матрица примитивна тогда и толь-
ко тогда, когда её степени, начиная с некоторой, равны I.
Предложение 3. Если A — нормальная форма булевой матри-
цы с периодом d, то диагональные блоки матрицы A
d
— примитив-
ные матрицы.
Последние два предложения очевидным образом переформулиру-
ются для неотрицательных матриц.
§ 5. Некоторые алгоритмические вопросы
В этом параграфе для сильно связного графа
1) приводится способ вычисления циклических классов,
2) даются оценки параметра k
0
.
Предложение 1. Вершины i, j тогда и только тогда принад-
лежат одному циклическому классу, когда существуют пути оди-
наковой длины из этих вершин в одну и ту же вершину или, как
мы будем говорить, из них синхронно достижима одна и та же
вершина.
Д о к а з а т е л ь с т в о. Если вершины i, j лежат в одном классе,
то согласно предложению 6 §3 при достаточно большом l существуют
(i, i)-путь и (j, i)-путь длины ld.
Обратно, если вершины i, j принадлежат разным циклическим
классам, то из них синхронно можно перейти лишь в разные клас-
38                                        Глава 2. Ориентированные графы


но их утверждения либо становятся тривиальными, либо приобрета-
ют настолько специальный вид, что заслуживают отдельных форму-
лировок. Мы приведём эти формулировки, а читателям рекомендуем
перечитать предыдущий параграф и обдумать, во что превращают-
ся содержащиеся в нём определения и утверждения в случае, когда
индекс импримитивности равен единице.
    Предложение 1. Граф примитивен тогда и только тогда, ко-
гда существует такое число q0 , что при k > q0 из любой вершины
можно перейти в любую другую вершину за k шагов.
    Неприводимая булева матрица называется примитивной, если её
период равен 1. Другими словами, булева матрица примитивна, ес-
ли примитивен её граф. Простейший пример — матрица I. Матрица
с неотрицательными элементами называется примитивной, если при-
митивен её булевский портрет, или, эквивалентно, если примитивен
её граф.
   Предложение 2. Булева матрица примитивна тогда и толь-
ко тогда, когда её степени, начиная с некоторой, равны I.
   Предложение 3. Если A — нормальная форма булевой матри-
цы с периодом d, то диагональные блоки матрицы Ad — примитив-
ные матрицы.
   Последние два предложения очевидным образом переформулиру-
ются для неотрицательных матриц.

           § 5. Некоторые алгоритмические вопросы

     В этом параграфе для сильно связного графа
     1) приводится способ вычисления циклических классов,
     2) даются оценки параметра k0 .
   Предложение 1. Вершины i, j тогда и только тогда принад-
лежат одному циклическому классу, когда существуют пути оди-
наковой длины из этих вершин в одну и ту же вершину или, как
мы будем говорить, из них синхронно достижима одна и та же
вершина.
     Д о к а з а т е л ь с т в о. Если вершины i, j лежат в одном классе,
то согласно предложению 6 §3 при достаточно большом l существуют
(i, i)-путь и (j, i)-путь длины ld.
     Обратно, если вершины i, j принадлежат разным циклическим
классам, то из них синхронно можно перейти лишь в разные клас-

Страницы