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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

8 Глава 1. Неориентированные графы
Матрицы над булевой алгеброй складывают и умножают по обыч-
ным правилам, при этом сохраняются известные свойства операций
с матрицами (с теми же доказательствами). Но нужно забыть о вы-
читании матриц. Впрочем, оно и не потребуется.
Условимся называть (0,1)-матрицу булевой, если с её элементами
мы намерены обращаться по правилам булевой алгебры. Приведём
“булевский” вариант предложения 1.
Предложение 2. Если A — булева матрица смежности графа,
то a
(k)
ij
= 1 тогда и только тогда, когда в этом графе существует
(i, j)-маршрут длины k.
Через I будем обозначать прямоугольную булеву матрицу, все
элементы которой равны 1, а размеры таковы, что формулы, в ко-
торых она участвует, имеют смысл. Буква E, как обычно, обознача-
ет квадратную матрицу, диагональные элементы которой равны 1, а
прочие равны 0.
Задача 2. Пусть граф с n вершинами задан булевой матрицей
смежности A. Докажите, что
a) (E + A)
m
= E + A + . . . + A
m
, m = 1, 2, . . . ;
b) вершины i, j связаны ⇔ (ij)-элемент матрицы (E + A)
n−1
равен 1;
c) граф связен ⇔ (E + A)
n−1
= I.
Задача 3. Пусть A — матрица смежности графа. Чему – в гра-
фовых терминах – равно число tr A
2
?
Графы (V, E) и (V
0
, E
0
) называются изоморфными, если суще-
ствует такая биекция σ : V → V
0
, что (u, v) ∈ E ⇔ (σ(u), σ(v)) ∈ E
0
.
С точки зрения теории изоморфные графы представляют, по суще-
ству, один граф, но с различными обозначениями вершин.
Изоморфизм графов можно определить в матричных терминах.
Предварительно введём понятие перестановочного подобия матриц.
Оно формулируется одинаково для булевых матриц и матриц над
полем.
Квадратная (0, 1)-матрица P называется перестановочной, если
она имеет в каждой строке и каждом столбце ровно одну единицу.
Легко проверить, что тогда P P
T
= P
T
P = E, то есть P
T
= P
−1
.
Матрицы A и B называются перестановочно подобными, если A =
P BP
T
для некоторой перестановочной матрицы P . Содержательный
смысл этого определения заключается в том, что A получается из B
одинаковыми перестановками строк и столбцов.
Пусть графы с n вершинами, заданные матрицами смежности A
и B, изоморфны, то есть существует такая биекция (перестановка) σ
8                                      Глава 1. Неориентированные графы


     Матрицы над булевой алгеброй складывают и умножают по обыч-
ным правилам, при этом сохраняются известные свойства операций
с матрицами (с теми же доказательствами). Но нужно забыть о вы-
читании матриц. Впрочем, оно и не потребуется.
     Условимся называть (0,1)-матрицу булевой, если с её элементами
мы намерены обращаться по правилам булевой алгебры. Приведём
“булевский” вариант предложения 1.
     Предложение 2. Если A — булева матрица смежности графа,
       (k)
то aij = 1 тогда и только тогда, когда в этом графе существует
(i, j)-маршрут длины k.
     Через I будем обозначать прямоугольную булеву матрицу, все
элементы которой равны 1, а размеры таковы, что формулы, в ко-
торых она участвует, имеют смысл. Буква E, как обычно, обознача-
ет квадратную матрицу, диагональные элементы которой равны 1, а
прочие равны 0.
     Задача 2. Пусть граф с n вершинами задан булевой матрицей
смежности A. Докажите, что
     a) (E + A)m = E + A + . . . + Am , m = 1, 2, . . . ;
     b) вершины i, j связаны ⇔ (ij)-элемент матрицы (E + A)n−1
равен 1;
     c) граф связен ⇔ (E + A)n−1 = I.
     Задача 3. Пусть A — матрица смежности графа. Чему – в гра-
фовых терминах – равно число tr A2 ?
     Графы (V, E) и (V 0 , E 0 ) называются изоморфными, если суще-
ствует такая биекция σ : V → V 0 , что (u, v) ∈ E ⇔ (σ(u), σ(v)) ∈ E 0 .
С точки зрения теории изоморфные графы представляют, по суще-
ству, один граф, но с различными обозначениями вершин.
     Изоморфизм графов можно определить в матричных терминах.
Предварительно введём понятие перестановочного подобия матриц.
Оно формулируется одинаково для булевых матриц и матриц над
полем.
     Квадратная (0, 1)-матрица P называется перестановочной, если
она имеет в каждой строке и каждом столбце ровно одну единицу.
Легко проверить, что тогда P P T = P T P = E, то есть P T = P −1 .
Матрицы A и B называются перестановочно подобными, если A =
P BP T для некоторой перестановочной матрицы P . Содержательный
смысл этого определения заключается в том, что A получается из B
одинаковыми перестановками строк и столбцов.
     Пусть графы с n вершинами, заданные матрицами смежности A
и B, изоморфны, то есть существует такая биекция (перестановка) σ

Страницы