Ізоморфізм графів - це

В теорії графів изоморфизмом графів і називається біекція між множинами вершин графів така, що будь-які дві вершини і графа суміжні, тоді і тільки тоді, коли вершини і суміжні в графі. Тут графи розуміються неорієнтованими і не мають ваг вершин і ребер. У разі, якщо поняття ізоморфізму застосовується до орієнтованим або зваженим графам, накладаються додаткові обмеження на збереження орієнтації дуг і значень ваг. Якщо ізоморфізм графів встановлено, вони називаються ізоморфними і позначаються як.

Іноді біекція записується у вигляді підстановки ізоморфізму. Деякі завдання обробки графів вимагають не тільки перевірки ізоморфізму, а й з'ясування його підстановки.

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

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

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

Ізоморфізм між графами і

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

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

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

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

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

інваріанти

Існує набір числових характеристик графів, званих інваріантами. які збігаються у ізоморфних графів (збіг інваріантів є необхідним. але не достатньою умовою наявності ізоморфізму) [5]. До них відносяться число вершин і число дуг / ребер графа G. упорядкований за зростанням або спаданням вектор ступенів вершин, упорядкований за зростанням або спаданням вектор власних чисел матриці суміжності графа (спектр графа), хроматичної число і ін. Факт збігу інваріантів зазвичай не несе інформації про підстановці ізоморфізму.

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

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

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

Модульне твір графів, запропоноване В. Г. Візінга (англ.), Дозволяє звести задачу перевірки ізоморфізму до задачі визначення щільності графа, що містить вершин. Якщо,, то граф містить підграф, ізоморфний графу.

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

Дивитися що таке "Ізоморфізм графів" в інших словниках:

Ізоморфізм - Цей термін має також інші значення див. Ізоморфізм (значення). Ізоморфізм (від ін. Грец. Ἴσος «рівний, однаковий, подібний» і μορφή «форма») це дуже загальне поняття, яке вживається в різних розділах математики. У загальних ... ... Вікіпедія

ГРАФІВ ізоморфізму - відношення еквівалентності на безлічі графів. Ізоморфні відображенням одного неориентированного графа на інший зв. взаємно однозначне відображення вершин і ребер одного графа відповідно на вершіниі ребра іншого графа, при до ром ... ... Математична енциклопедія

Ізоморфізм (математика) - ізоморфізм це дуже загальне поняття, яке вживається в різних розділах математики. У загальних рисах його можна описати так: Нехай дано два безлічі з певною структурою (групи, кільця, лінійні простори і т. П.). Біекція між ... ... Вікіпедія

Ізоморфізм (матем.) - ізоморфізм це дуже загальне поняття, яке вживається в різних розділах математики. У загальних рисах його можна описати так: Нехай дано два безлічі з певною структурою (групи, кільця, лінійні простори і т. П.). Біекція між ... ... Вікіпедія

ГРАФІВ гомеоморфізмом - відношення еквівалентності на безлічі графів, що характеризує їх геометрія, властивості. Г. р визначається следуюпшм чином. Подразбіеніем ребра (а, b) .графа Gназ. операція, яка полягає в додаванні нової вершини v, видаленні ребра (а, b) .і ... ... Математична енциклопедія

Теорія графів - Граф з шістьма вершинами і сім'ю ребрами Теорія графів розділ дискретної математики, що вивчає властивості графів. У загальному сенсі граф представляється як безліч вершин (вузлів), з'єднаних ребрами. У строго ... Вікіпедія

Теорія графів і мографов - Теорема 3.27. заміна будь-якого ребра (a, b) in Gкрітіческого графа G на k вершинно непересічних простих ланцюгів довжини 3 тоді і тільки тоді приводять до утворення критичного графа T 3 (G), коли k задовольняє одному з наступних умов: # k = 1 ... Вікіпедія

Глосарій теорії графів - Ця сторінка глосарій. Див. Також основну статтю: Теорія графів Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці) ... Вікіпедія

Словник термінів теорії графів - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И К Л М Н О П Р С ... Вікіпедія

Дуга (теорія графів) - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія