Page 21 - 4386

а б

в

Рисунок 1.13 – Дві пари ізоморфних графів (а, б) та пара не

ізоморфних (в)

Графи ізоморфні тоді та тільки тоді, коли ізоморфні їхні

доповнення. Якщо ϕ – ізоморфізм графа G на G , то вершини v у
1
2
графі G та ϕ(v) у G мають однакові степені.
1
2
Графи G та G ізоморфні тоді і тільки тоді, коли матрицю
1
2
суміжності (матрицю інцидентності) одного з цих графів можна

одержати з матриці суміжності (матриці інцидентності) іншого

графа за допомогою відповідних перестановок рядків та стовпців.

Для перевірки ізоморфності графів G і G за матрицею
1
2
суміжності необхідно визначити, чи існує така перестановка

рядків і стовпців у матриці суміжності G , щоб у результаті
1
вийшла матриця G . З цією метою необхідно зробити всі можливі
2
перестановки рядків і стовпців (їхня максимальна кількість

дорівнює n!⋅n!). Якщо після однієї із цих перестановок матриці

суміжності тотожно збіжаться, то графи ізоморфні.

Для перевірки ізоморфності графів G і G за матрицею
1
2
інцидентності (та списку ребер) необхідно визначити, чи існує

така перестановка рядків і стовпців у матриці інцидентності G ,
1
щоб у результаті вийшла матриця G . З цією метою треба зробити
2
всі можливі пари перестановок рядків і стовпців (їхня

20