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

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

f\colon V(G)\to V(H)\,\!

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

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

Якщо присутній ізоморфізм між двома графами, тоді графи називають ізоморфними і ми пишемо $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

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

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

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

Виняток з теореми Вітні: подані графи

K_{3}

(ліворуч) і

K_{1,3}

(праворуч) не ізоморфні, хоча їх лінійні графи ізоморфні

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

Інваріант

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

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

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

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

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

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

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

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

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

Примітки

H. Whitney (1932). Congruent graphs and the connectivity of graphs. Am. J. Math. 54: 160–168. doi:10.2307/2371086.
Dirk L. Vertigan, Geoffrey P. Whittle (1997). A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71 (2): 215–230. doi:10.1006/jctb.1997.1789.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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). A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71 (2): 215–230. doi:10.1006/jctb.1997.1789.