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

В теорії графів изоморфизмом графів G = ⟨V G. E G⟩, E_ \ right \ rangle> і H = ⟨V H. E H⟩, E_ \ right \ rangle> називається біекція між множинами вершин графів f. V G → V H \ rightarrow V_> така, що будь-які дві вершини u і v графа G суміжні тоді і тільки тоді, коли вершини f (u) і f (v) суміжні в графі H. Тут графи розуміються неорієнтованими і не мають ваг вершин і ребер. У разі, якщо поняття ізоморфізму застосовується до орієнтованим або зваженим графам, накладаються додаткові обмеження на збереження орієнтації дуг і значень ваг. Якщо ізоморфізм графів встановлено, вони називаються ізоморфними і позначаються як G ≃ H.

Іноді біекція f записується у вигляді підстановки ізоморфізму (a 1 a 2 ... a n f (a 1) f (a 2) ... f (a n)) a_a_ \ dots a _ \\ f (a_) f (a _) \ dots f (a _) \ end >>. Деякі завдання обробки графів вимагають не тільки перевірки ізоморфізму, а й з'ясування його підстановки.

Ставлення ізоморфізму графів є відношенням еквівалентності. певне для графів, і дозволяє зробити розбиття вихідного класу всіх графів на класи еквівалентності. Безліч графів, ізоморфних один одному, називається класом ізоморфізму графів (англ.). їх число в залежності від n являє собою послідовність A000088 в OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346.).

Існують також суміжні задачі теорії графів, такі як пошук изоморфного подграфа і пошук максимального загального изоморфного подграфа (англ.). належать до класу NP-повних. У суміжних розділах математики існують схожі проблеми, наприклад ізоморфізму проективних площин і ізоморфізму кінцевих груп. які полиномиально зводяться до проблеми ізоморфізму графів (можливість зворотного полиномиальной сводимости в загальному випадку не доведена) [1].

Два графа, наведені в прикладі, є ізоморфними.

Підстановка ізоморфізму f

(A b c d g h i j 1 6 8 3 5 2 4 7) abcdghij \\ 16835247 \ end >>

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

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

теорема Уїтні

Виняток з теореми Уїтні: представлені графи K 3> (зліва) і K 1. 3> (праворуч) НЕ ізоморфні, проте їх реберні графи ізоморфні

Теорема Уїтні про ізоморфізмі графів [3] [4]. сформульована Хасслер Уїтні в 1932 році. свідчить, що два зв'язкових графа ізоморфні, тоді і тільки тоді, коли їх реберні графи ізоморфні, за винятком графів K 3> (повного графа з 3 вершин) і повного двудольного графа K 1. 3>. які не є ізоморфними, проте обидва мають граф K 3> як ребрового графа. Теорема Уїтні може бути узагальнена для гіперграфів [5].

інваріанти

Існує набір числових характеристик графів, званих інваріантами. які збігаються у ізоморфних графів (збіг інваріантів є необхідним. але не достатньою умовою наявності ізоморфізму) [6]. До них відносяться число вершин n (G) і число дуг / ребер m (G) графа G. упорядкований за зростанням або спаданням вектор ступенів вершин s (G) = (ρ (v 1). Ρ (v 2). .... Ρ (vn))), \ rho (v _), \ dots, \ rho (v _))>. упорядкований за зростанням або спаданням вектор власних чисел матриці суміжності графа (спектр графа), хроматичної число χ (G) і ін. Факт збігу інваріантів зазвичай не несе інформації про підстановці ізоморфізму.

Інваріант називається повним. якщо збігу інваріантів графів необхідно і достатньо для встановлення ізоморфізму. Наприклад, кожне з значень μ m i n (G) (G)> і μ m a x (G) (G)> (міні- і максі-код матриці суміжності) є повним інваріантом для графа з фіксованим числом вершин n.

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

Модульне твір Візінга

Модульне твір графів Y = G ◊ H. запропоноване В. Г. Візінга. дозволяє звести задачу перевірки ізоморфізму до задачі визначення щільності графа φ (Y). що містить n (G) ⋅ n (H) вершин. Якщо φ (Y) = n (G). n (G) ≤ n (H). то граф H містить підграф, ізоморфний графу G.

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