Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

В теорії графів изоморфизмом графів G = \ left \ langle V_G, E_G \ right \ rangle і H = \ left \ langle V_H, E_H \ right \ rangle називається біекція між множинами вершин графів f \ colon \ V_G \ rightarrow V_H така, що будь-які дві вершини u і v графа G суміжні, якщо і тільки якщо вершини f (u) і f (v) суміжні в графі H . Тут графи розуміються неорієнтованим і не мають ваг вершин і ребер. У випадку, якщо поняття ізоморфізму застосовується до орієнтованим або зваженим графам, накладаються додаткові обмеження на збереження орієнтації дуг і значень ваг. Якщо ізоморфізм графів встановлено, вони називаються ізоморфними і позначаються як G \ simeq H .

Іноді біекція f записується у вигляді підстановки ізоморфізму \ Begin {pmatrix} a_1 & a_2 & \ dots & a_n \ \ f (a_1) & f (a_2) & \ dots & f (a_n) \ end {pmatrix} . Деякі завдання обробки графів вимагають не тільки перевірки ізоморфізму, а й з'ясування його підстановки.

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

У випадку, якщо біекція f відображає граф сам на себе (графи G і H збігаються), вона називається автоморфізмом графа G .


1. Приклад

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

Граф G Граф H Ізоморфізм між графами G і H Підстановка ізоморфізму f
Graph isomorphism 1.gif Graph isomorphism 2.gif f (a) = 1

f (b) = 6
f (c) = 8
f (d) = 3
f (g) = 5
f (h) = 2
f (i) = 4
f (j) = 7

\ Begin {pmatrix} a & b & c & d & g & h & i & j \ \ 1 & 6 & 8 & 3 & 5 & 2 & 4 & 7 \ end {pmatrix}

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

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


2.1. Теорема Уїтні

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

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


2.2. Інваріанти

Існує набір числових характеристик графів, званих інваріантами, які збігаються у ізоморфних графів (збіг інваріантів є необхідним, але не достатньою умовою наявності ізоморфізму) [5]. До них відносяться число вершин n (G) і число дуг / ребер m (G) графа G, упорядкований за зростанням або спаданням вектор ступенів вершин s (G) = (\ rho (v_1), \ rho (v_2), \ dots, \ rho (v_n)) , Упорядкований за зростанням або спаданням вектор власних чисел матриці суміжності графа (спектр графа), хроматичної число χ (G) та ін Факт збігу інваріантів зазвичай не несе інформації про підстановці ізоморфізму.

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

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


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

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


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

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

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



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

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


Примітки

  1. 1 2 Курейчик В. М., Глушань В. М., Щербаков Л. І. Комбінаторні апаратні моделі та алгоритми в САПР - М .: Радіо і зв'язок, 1990. - 216 с.
  2. H. Whitney (1932). "Congruent graphs and the connectivity of graphs". Am. J. Math. 54: 160-168. DOI : 10.2307/2371086 - dx.doi.org/10.2307/2371086.
  3. Харарі Ф. Теорія графів - eqworld.ipmnet.ru/ru/library/books/Harari1973ru.djvu - М .: Світ, 1973. (Вид. 3, М.: КомКніга, 2006. - 296 с.)
  4. Dirk L. Vertigan, Geoffrey P. Whittle (1997). " A 2-Isomorphism Theorem for Hypergraphs - homepages.mcs.vuw.ac.nz / ~ whittle/pubs/2-isomorphism_theorem_for_hypergraphs.pdf ". J. Comb. Theory, Ser. B 71 (2): 215-230. DOI : 10.1006/jctb.1997.1789 - dx.doi.org/10.1006/jctb.1997.1789.
  5. Зиков А. А. Основи теорії графів - М .: Наука, 1986. - 384 с. - ISBN 978-5-9502-0057-1.
  6. Трофимов М. І., Смоленський Є. А. Застосування індексів електронегативності органічних молекул в задачах хімічної інформатики / / Вісті Академії наук. Серія хімічна. - 2005. - С. 2166-2176.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Ізоморфізм
Ізоморфізм (значення)
Ізоморфізм (хімія)
Теорія графів
Список графів д'Е
Візуалізація графів
Зв'язність графів
Кліка (теорія графів)
Список графів де Блуа
© Усі права захищені
написати до нас
Рейтинг@Mail.ru