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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

28 Глава 2. Ориентированные графы
Предложение 2. Невозвратные вершины — это в точно-
сти те вершины, которые принадлежат неминимальным компо-
нентам.
Назовём простой путь максимальным, если он не имеет простого
продолжения. Докажите самостоятельно
Предложение 3. Конец простого максимального пути всегда
принадлежит минимальной компоненте.
§ 2. Нормальная форма матрицы смежности
приводимого графа
Квадратную матрицу A (булеву матрицу или матрицу над полем)
называют приводимой, если она перестановочно подобна матрице ви-
да
µ
B 0
C D
, (1)
где B, D — квадратные матрицы. В противном случае говорят, что A
— неприводимая матрица. Приводимая матрица A имеет нормальную
форму, если она блочно-треугольная:
A =
A
1
.
.
.
A
l
A
l+1,1
. . . A
l+1,l
A
l+1
.
.
.
.
.
.
.
.
.
.
.
.
A
s,1
. . . A
s,l
A
s,l+1
. . . A
s
(2)
причём A
1
, A
2
, . . . , A
s
(1 ≤ l ≤ s) — неприводимые матрицы, а в
каждой строке, начиная с (l + 1)-го (при l < s), имеются ненулевые
блоки, расположенные левее диагонали.
Предложение 1. Орграф сильно связен тогда и только то-
гда, когда его матрица смежности неприводима. Если граф приво-
дим, то существует нумерация вершин, при которой его матрица
смежности имеет нормальную форму.
Д о к а з а т е л ь с т в о. Допустим, что орграф сильно связен,
но его матрица смежности приводима. Это значит, что при некото-
рой нумерации вершин графу соответствует матрица смежности вида
(1). Но тогда выходит, что из вершин с номерами 1, . . . , k нельзя пе-
рейти в вершины с номерами k + 1, . . . , n (где k — порядок B), —
противоречие с сильной связностью.
28                                      Глава 2. Ориентированные графы


   Предложение 2. Невозвратные вершины — это в точно-
сти те вершины, которые принадлежат неминимальным компо-
нентам.
   Назовём простой путь максимальным, если он не имеет простого
продолжения. Докажите самостоятельно
   Предложение 3. Конец простого максимального пути всегда
принадлежит минимальной компоненте.

         § 2. Нормальная форма матрицы смежности
                     приводимого графа

   Квадратную матрицу A (булеву матрицу или матрицу над полем)
называют приводимой, если она перестановочно подобна матрице ви-
да                        µ        ¶
                             B 0
                                     ,                       (1)
                             C D
где B, D — квадратные матрицы. В противном случае говорят, что A
— неприводимая матрица. Приводимая матрица A имеет нормальную
форму, если она блочно-треугольная:
                                                   
                    A1
                         ...                       
                                                   
                                A                  
            A=                      l
                  Al+1,1 . . . Al+1,l Al+1
                                                    
                                                             (2)
                  .              ..    ..          
                  ..              .     .  ...     
                    As,1 . . . As,l As,l+1 . . . As
причём A1 , A2 , . . . , As (1 ≤ l ≤ s) — неприводимые матрицы, а в
каждой строке, начиная с (l + 1)-го (при l < s), имеются ненулевые
блоки, расположенные левее диагонали.
    Предложение 1. Орграф сильно связен тогда и только то-
гда, когда его матрица смежности неприводима. Если граф приво-
дим, то существует нумерация вершин, при которой его матрица
смежности имеет нормальную форму.
    Д о к а з а т е л ь с т в о. Допустим, что орграф сильно связен,
но его матрица смежности приводима. Это значит, что при некото-
рой нумерации вершин графу соответствует матрица смежности вида
(1). Но тогда выходит, что из вершин с номерами 1, . . . , k нельзя пе-
рейти в вершины с номерами k + 1, . . . , n (где k — порядок B), —
противоречие с сильной связностью.

Страницы