Ізоморфізм графів

В теорії графів та її застосуваннях часто суттєвим є лише той факт, що існують об'єкти (вершини графа) і зв'язки між ними (ребра). У таких випадках один граф можна утворити з відомого іншого шляхом зміни позначень вершин та конфігурації діаграми графа. Ці міркування приводять до поняття ізоморфізму графів.

Означення 3.23. Нехай G₁=(V₁,E₁), і G₂=(V₂,Е₂)– два графи. Бієктивне відображення ψ: V₁→V₂називається ізоморфізмом G₁на G₂, якщо число ребер, що з’єднують вершини и і v в G₁, дорівнює числу ребер, що з’єднують вершини ψ(и)і ψ(v)в G₂ (зрозуміло, що число петель в вершині и дорівнює числу петель в вершині ψ(и)).

Означення 3.24. Графи G₁=(V₁,E₁)і G₂=(V₂,Е₂) називаються ізоморфними, якщо існує ізоморфізм G₁на G₂ (позначення G₁@G₂).

Сформульоване означення ізоморфізма придатне і для орграфів, необхідно лише ребра вважати орієнтованими (тобто дугами), а пари вершин, з’єднані дугами, вважати упорядкованими.

Ізоморфізм G₁ на G₂ є взаємно однозначним відображенням множини вершин V₁ на множину вершин V₂, що зберігає відношення суміжності вершин. Іншими словами, ізоморфізм ψ характеризується властивістю: довільні вершины и і v суміжні в графі G₁тоді і лише тоді, коли вершины ψ(u) і ψ(v)суміжні в графі G₂.

На рис. 3.5 наведені діаграми двох ізоморфних графів.

Ізоморфізм – це бінарне взаємно-однозначне відношення на множині графів, тобто він є відношенням еквівалентності. Ізоморфні графи відрізняються лише ідентифікато-рами вершин. Ця відмінність не є суттєвою, тому звичайно ізоморфні графи ототожнюють, зображаючи їхні діаграми без позначення вершин, або з нумерацією вершин натуральними числами. Отже, діаграма задає граф з точністю до ізоморфізму.

Для доказу ізоморфності двох графів треба показати відповідну бієкцию. У загальному випадку доведення ізоморфізму графів може виявитись складною задачею. Якщо формально виходити з означення ізоморфізму, то потрібно здійснювати перебір бієкцій множини вершин одного графа на множину вершин іншого і для кожної з них перевіряти, чи є вона ізоморфізмом. Практично такий перебір бієкцій здійснюється на підставі наступної теореми.

Теорема 3.1. Графи G₁ та G₂ ізоморфні тоді і тільки тоді, коли матрицю суміжностей одного з цих графів можна одержати з матриці суміжностей іншого графа за допомогою відповідних перестановок рядків та стовпців.

Доведення. Оскільки ізоморфні графи G₁ і G₂ порядку n відрізняються між собою лише нумерацією (позначеннями) вершин, то існує бієктивне відображення j множини номерів (позначень) вершин першого графа на множину номерів (позначень) вершин другого. Отже, кожен елемент a_ij матриці суміжностей A графа G₁ збігається з елементом b_j(i)j(j) , що знаходиться в рядку з номером j(i) і стовпці з номером j(j) матриці суміжностей B графа G₂. Якщо відображення j відоме, то шляхом послідовної перестановки рядків з номерами i та j(i), а потім і стовпців з тимі ж номерами для всіх i=1,...,n матрицю суміжностей A можна перетворити у матрицю суміжностей B і навпаки.

Якщо потрібно перевірити за допомогою матриць суміжностей ізоморфність двох графів порядку n, необхідно здійснити різні (по сполуках номерів i та j) перестановки рядків і стовпців однієї з цих матриць. Якщо після чергової перестановки одержимо матрицю, що збігається з іншою, то дійдемо до висновку, що ці графи ізоморфні.

Кількість всіх можливих перестановок рядків і стовпців квадратної матриці порядку n дорівнює n!. Якщо після виконання всіх n! перестановок збігу матриць суміжностей обох графів не одержимо, то дійдемо до висновку, що ці графи неізоморфні. Теорему доведено.

Для n вершин число можливих бієкцій дорівнює n!. Щоб з’ясувати розглянутим способом, чи є графи ізоморфними, може стати потрібним виконати всі n! перестановок рядків і стовпців матриці суміжностей одного з них. Вже для порівняно невеликих значень n здійснити такий перебір бієкцій практично неможливо (наприклад, при n=20 маємо n!>2×10¹⁸). У прикладній теорії алгоритмів розробляються різноманітні алгоритми перевірки ізоморфізму графів, які для більшості графів (або окремих типів графів) дозволяють суттєво скоротити обсяг необхідних перевірок.

Одержаний (шляхом відповідних перестановок рядків і стовпців) збіг матриць суміжностей є достатньою умовою ізоморфності неорієнтованих графів без паралельних і контрпаралельних ребер, тому що при цьому збігаються також їхні матриці інциденцій. У загальному ж випадку для будь-яких графів (орграфів) достатньою умовою ізоморфності є збіг матриць інциденцій, що гарантує збіг матриць суміжностей цих графів. За аналогією з теоремою 3.1 наведемо наступну теорему, на підставі якої можна здійснювати перевірку ізоморфності будь-яких графів.

Теорема 3.2. Графи (орграфи) G₁ і G₂ ізоморфні тоді і тільки тоді, коли матрицю інциденцій одного з цих графів можна одержати з матриці інциденцій іншого за допомогою перестановок рядків та стовпців.

Для матриць інциденцій графів G₁ і G₂ з n вершинами і m ребрами (дугами) справедливі аналогічні міркування щодо перестановок рядкі і стовпців, як і для матриць суміжностей. Відмінність у тому, що коли G₁ і G₂ ізоморфні, тоді для їхніх множин вершин існує бієкція j, а для множин ребер - інша бієкція y. Тому перестановки рядків і стовпців здійснюються в будь-якої послідовності, як взаємно незалежні кроки. Загальна кількість таких кроків для перевірки ізоморфізму графів G₁ і G₂ не перевищує n!·m!.