2015-01-07
1527
Графы G 1= (X 1, A 1)и G 2= (X 2, A 2) изоморфны, если существует взаимно однозначное соответствие между множествами вершин X 1и X 2, такое, что любые две вершины одного графа соединены тогда и только тогда, когда соответствующие вершины соединены в другом графе.
Пример 3.9
Графы, изображенные на рис. 3.4 являются изоморфными.
Рис. 3.4
Изоморфные графы отличаются только нумерацией вершин. Матрицы смежности двух изоморфных графов могут быть получены одна из другой перестановкой строк и столбцов. Чтобы узнать, являются ли два графа изоморфными, нужно произвести все возможные перестановки строк и столбцов матрицы смежности одного из графов. Если после какой-нибудь перестановки получится матрица смежности второго графа, то эти графы изоморфны. Чтобы убедиться, что графы неизоморфны, надо выполнить все n! возможных перестановок строк и столбцов.
