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

В теорії графів, ізоморфізмом графів G і H є бієкція між множинами вершин G і H

${\displaystyle f\colon V(G)\to V(H)\,\!}$

така, що будь-які дві вершини u і v графа G суміжні в G тоді і тільки тоді, коли ƒ(u) і ƒ(v) суміжні в H. Такий тип бієкції зазвичай зветься «реброзберігальна бієкція», згідно із загальним поняттям ізоморфізму як бієкції зі збереженням структури.

У визначенні поданому вище, під графами ми розумієм неорієнтовані непозначені (незважені) графи. Однак, поняття ізоморфізму може бути застосоване до всіх інших різновидів графів. доданням вимог зі збереження відповідних додаткових елементів структури: спрямування ребер, ваги кожного з ребер і т. д., з наступним винятком. Коли йдеться про позначений граф з унікальними позначками, зазвичай цілими числами в межах 1,…,n, де n це кількість вершин в графі, два позначених графи називають ізоморфними, якщо відповідні непозначені графи ізоморфні.

Якщо присутній ізоморфізм між двома графами, тоді графи називають ізоморфними і ми пишемо ${\displaystyle G\simeq H}$. У випадку, коли бієкція це відображення графа самого на себе, тобто, коли G і H це один і той самий граф, бієкція називається автоморфізмом G.

Ізоморфізм графів це відношення еквівалентності на графах і ділить всі графи на класи еквівалентності. Множина графів ізоморфних один одному називається класом ізоморфності графів.

Приклад

Два графи показні нижче ізоморфні, незважаючи на свою зовнішню відмінність.

Граф G	Граф H	Ізоморфізм між G і H
		ƒ(a) = 1 ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7

Ізоморфізм графів загального виду

Графи ${\displaystyle G}$ і ${\displaystyle H}$ є ізоморфними, якщо шляхом перестановки рядків і стовпців матриці суміжності графа ${\displaystyle G}$ можливо отримати матрицю суміжності графа ${\displaystyle H}$. Однак перебирання всіх можливих перестановок характеризується обчислювальною складністю ${\displaystyle O(N!)}$ (за умови, що порівняння матриць суміжності відбувається за час незалежний від ${\displaystyle N}$, що зазвичай несправедливо і додатково збільшує наведену оцінку), що істотно обмежує використання подібного підходу на практиці. Існують методи обмеженого перебору можливих пар здогадно-ізоморфних графів вершин (аналог методу гілок і меж), однак вони незначно покращують наведену вище асимптотику.

Теорема Вітні

Виняток з теореми Вітні: подані графи ${\displaystyle K_{3}}$ (ліворуч) і ${\displaystyle K_{1,3}}$ (праворуч) не ізоморфні, хоча їх лінійні графи ізоморфні

Теорема про ізоморфізм графів Вітні, сформульована Х. Вітні в 1932, каже, що два зв'язних графи ізоморфні, тоді і тільки тоді, коли їх лінійні графи ізоморфні, за винятком графів ${\displaystyle K_{3}}$ (повного графа з 3 вершин) і повного двочасткового графа ${\displaystyle K_{1,3}}$, які не є ізоморфними, однак обидва мають граф ${\displaystyle K_{3}}$ як лінійний граф. Теорема Вітні може бути узагальнена для гіперграфів.

Інваріант

Докладніше: Інваріант графа

Існує набір числових характеристик графів, званих інваріантами, які збігаються в ізоморфних графів (збіг інваріантів є необхідною, але не достатньою умовою наявності ізоморфізму). До них належать кількість вершин ${\displaystyle n(G)}$ і кількість ребер ${\displaystyle m(G)}$ графа G, впорядкований за зростанням або зменшенням вектор степенів вершин ${\displaystyle s(G)=(\rho (v_{1}),\rho (v_{2}),\dots ,\rho (v_{n}))}$, впорядкований за зростанням або зменшенням вектор власних чисел матриці суміжності графа (спектр графа), хроматичне число ${\displaystyle \chi (G)}$ та ін. Факт збігу інваріантів зазвичай не несе інформації про підстановку ізоморфізму.

Інваріант називається повним, якщо збігу інваріантів графів необхідно і достатньо для встановлення ізоморфізму. Наприклад, кожне значення ${\displaystyle \mu _{min}(G)}$ і ${\displaystyle \mu _{max}(G)}$ (міні- і максі-коди матриці суміжності) є повним інваріантом для графа з фіксованою кількістю вершин ${\displaystyle n}$.

Різні інваріанти мають різну працеємність обчислень. Наразі повний інваріант графа, обчислюваний за поліноміальний час, невідомий, хоча не доведено, що він не існує. Спроби його відшукання неодноразово здійснювались в 60—80 XX сторіччя, однак не увінчались успіхом.

Модульний добуток Візинга

Модульний добуток графів ${\displaystyle Y=G\lozenge H}$, запропонований В. Г. Візінгом, дозволяє звести задачу перевірки ізоморфізму до задачі визначення щільності графа ${\displaystyle \varphi (Y)}$, який містить ${\displaystyle n(G)\cdot n(H)}$ вершин. якщо ${\displaystyle \varphi (Y)=n(G)}$, ${\displaystyle n(G)\leq n(H)}$, тоді граф ${\displaystyle H}$ містить підграф, ізоморфний графові ${\displaystyle G}$.

Обчислювальна складність

Докладніше: ^[en]

Хоча задача розпізнавання ізоморфізму належить до класу NP, невідомо є вона NP-повною чи належить класу P (за умови, що P ≠ NP). При цьому задача пошуку ізоморфного підграфа в графі є NP-повною. Сучасні дослідження спрямовані на розробку швидких алгоритмів розв'язання як загальної задачі ізоморфізму довільних графів, так і графів особливих видів, а також теоретичного дослідження її складності обчислення.

Застосування

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

Примітки

1. H. Whitney (1932). Congruent graphs and the connectivity of graphs. Am. J. Math. 54: 160—168. doi:10.2307/2371086.
2. Dirk L. Vertigan, Geoffrey P. Whittle (1997). (PDF). J. Comb. Theory, Ser. B. 71 (2): 215—230. doi:10.1006/jctb.1997.1789. Архів оригіналу (PDF) за 28 лютого 2013. Процитовано 2 березня 2011.