Изоморфизм графов

Пусть и - графы и - взаимно-однозначное соответствие. (Заметим, что ). Отображение называется изоморфизмом графов и , если для любых вершин и графа их образы и смежные в графе тогда и только тогда, когда и смежные в . Если такое отображение существует, то графы и называются изоморфными.

Очевидно, что отношение изоморфизма графов является отношением эквивалентности.

Другими словами: графы и изоморфны, если существует такое взаимно-однозначное соответствие между множеством вершин и , что любые две вершины одного графа смежные тогда и только тогда, когда соответствующие им вершины другого графа также смежны. На рис. 2.8. приведены изоморфные графы: и ; и .

Рис. 2.8

Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежностей можно получить одну из другой одинаковыми перестановками строк и столбцов.

Доказательство.

Пусть заданы два изоморфных графа. и . Перенумеруем вершины графов и целыми числами от 0 до . . и - матрицы смежностей графов и соответственно. Если , то все доказано. В противном случае графы и отличаются лишь нумерацией вершин. Значит, существует такая подстановка на множестве вершин , которая сохраняет смежность, т.е. если , то . Тогда получаем , где . Теорема доказана.

Следует заметить, что теорема об изоморфизме графов остается справедливой, если рассматривать не матрицы смежностей, а матрицы Кирхгофа.