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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В теорії графів, ізоморфізмом графів 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
Graph isomorphism a.svg Graph isomorphism b.svg ƒ(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) \le n(H), тоді граф H містить підграф, ізоморфний графові G.

Ізоморфізм графів спеціального виду[ред.ред. код]

Обчислювальна складність[ред.ред. код]

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

Застосування[ред.ред. код]

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

Примітки[ред.ред. код]

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