Материал: способы задания графов
ТЕОРИЯ ГРАФОВ
Изоморфизм графов
Изоморфизм графов
Один и тот же граф может иметь несколько графических изображений, которые можно получить, изменяя расположение вершин и придавая ребрам разную геометрическую форму и длину
С другой стороны, два одинаковых, на первый взгляд, изображения могут задавать разные графы. Так, графы ниже геометрически одинаковы, но они отличаются нумерацией вершин.
В таких ситуациях необходимо четко определить понятие изоморфизма графов.
Изоморфизм графов
Изоморфизм графов
Замечание 1. Графы, содержащие различное число вершин или ребер, не являются
изоморфными.
Замечание 2. Графы, отличающиеся только
нумерацией вершин, являются изоморфными.
Замечание 3. Изоморфизм неориентированных графов есть отношение эквивалентности, так
как обладает свойствами рефлексивности,
симметричности и транзитивности.
При замене графа любым ему изоморфным все
свойства графа сохраняются.
Изоморфизм графов
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежности можно
получить одну из другой одинаковыми
перестановками строк и столбцов.
Чтобы проверить по матрице смежности изоморфность графов с числом вершин n ,
потребуется в общем случае n! перестановок.