double arrow

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


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

Означення 3.23. Нехай G1=(V1,E1), і G2=(V2,Е2)– два графи. Бієктивне відображення ψ: V1→V2називається ізоморфізмом G1на G2, якщо число ребер, що з’єднують вершини и і v в G1, дорівнює числу ребер, що з’єднують вершини ψ(иψ(vG2 (зрозуміло, що число петель в вершині и дорівнює числу петель в вершині ψ(и)).

Означення 3.24. Графи G1=(V1,E1G2=(V2,Е2) називаються ізоморфними, якщо існує ізоморфізм G1на G2 (позначення G1@G2).

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

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

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

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

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

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

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




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

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

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

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



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

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

Заказать ✍️ написание учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Сейчас читают про: