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

§ 1. Первые понятия теории графов                              9


на множестве {1, 2, . . . , n}, что для любых i, j
                              aij = bσ(i)σ(j) .
Сопоставим перестановке σ перестановочную матрицу P = (pij ) по-
рядка n, где           ½
                         1, если j = σ(i),
                 pij =                                       (3)
                         0 в противном случае.
Прямыми вычислениями проверяется, что
                              A = P BP T .
    Итак, если графы изоморфны, то их матрицы смежности пере-
становочно подобны. Наоборот, если матрицы смежности перестано-
вочно подобны, то графы изоморфны, причем изоморфизм σ опре-
деляется по матрице подобия P из равенств (3). Суммируем наши
рассуждения.
    Предложение 3. Графы изоморфны тогда и только тогда, ко-
гда их матрицы смежности перестановочно подобны.
    Замечание 1. После нумерации σ вершин графа (или перенуме-
рации, если вершины уже нумерованы) получается, формально гово-
ря, другой граф, изоморфный данному, с некоторой матрицей смеж-
ности A. Но поскольку по существу это тот же граф, мы будем в
этой ситуации говорить так: после нумерации σ матрица смежности
графа равна A. По той же причине перестановочно подобные (0,1)-
матрицы естественно рассматривать как матрицы смежности одного
графа при различных нумерациях вершин.
    В заключение параграфа отметим, что иногда используются гра-
фы, в которых, как на рис. 2, две вершины соединены несколькими
рёбрами (из называют кратными рёбрами) или имеются рёбра с сов-
падающими концами (их называют петлями).




                                    Рис. 2


   В нашем курсе, без существенного ущерба для содержания тео-
рии, рассматриваются графы без кратных рёбер и петель. Исклю-
чением является первая теорема следующего параграфа — теорема