У теорії графів, розділі математики, канонізація графів — це задача знаходження канонічної форми заданого графа G. Канонічна форма — це позначений граф Canon(G), який є ізоморфним до G, такий що кожен граф, ізоморфний до G, має таку саму канонічну форму, як і G. Таким чином, маючи розв'язок задачі канонізації графів, можна також розв'язати задачу ізоморфізму графів: щоб перевірити, чи є два графи G і H ізоморфними, обчислюють їхні канонічні форми Canon(G) і Canon(H) та перевіряють, чи ці дві канонічні форми ідентичні.

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

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

Задача ізоморфізму графів — це обчислювальна задача визначення того, чи є два скінченні графи ізоморфними. Очевидно, що задача канонізації графів є принаймні настільки ж обчислювально складною, як і задача ізоморфізму графів. Фактично, ізоморфізм графів навіть AC0-зводиться до канонізації графів. Проте, залишається відкритим питання, чи є ці дві задачі поліноміально-часово еквівалентними.

У 2019 році Ласло Бабаї оголосив про квазіполіноміальний алгоритм для канонізації графів, тобто такий, що має час виконання для деякого фіксованого . Хоча існування (детерміністичних) поліноміальних алгоритмів для ізоморфізму графів все ще є відкритою проблемою в теорії обчислювальної складності, у 1977 році Ласло Бабаї повідомив, що з імовірністю принаймні 1 − exp(−O(n)), простий алгоритм класифікації вершин створює канонічне позначення графа, обраного рівномірно випадково з множини всіх n-вершинних графів, лише після двох кроків уточнення. Невеликі модифікації та доданий крок пошуку в глибину створюють канонічні позначення таких рівномірно обраних випадкових графів за лінійний очікуваний час. Цей результат проливає світло на питання, чому багато повідомлених алгоритмів ізоморфізму графів добре працюють на практиці... Це був важливий прорив у імовірнісній теорії складності, який став широко відомим у рукописній формі і на який продовжували посилатися як на "неопублікований рукопис" ще довго після того, як його було представлено на симпозіумі.

Загальновідомою канонічною формою є лексикографічно найменший граф у межах класу ізоморфізму, яким є граф класу з лексикографічно найменшою матрицею суміжності, розглянутою як лінійний рядок. Однак обчислення лексикографічно найменшого графа є NP-складним.

Для дерев стислий поліноміальний алгоритм канонізації, що потребує O(n) пам'яті, представлений .. Почніть з позначення кожної вершини рядком 01. Ітеративно для кожної невисячої вершини x, видаліть провідний 0 та кінцеву 1 з позначення x; потім відсортуйте позначення x разом з позначеннями всіх суміжних листків у лексикографічному порядку. Об'єднайте ці відсортовані позначення, додайте назад провідний 0 та кінцеву 1, зробіть це новим позначенням для x та видаліть суміжні листки. Якщо залишилися дві вершини, об'єднайте їхні позначення в лексикографічному порядку.

Застосування Канонізація графів є основою багатьох алгоритмів ізоморфізму графів. Одним з провідних інструментів є Nauty..

Поширеним застосуванням канонізації графів є графічний інтелектуальний аналіз даних, зокрема у застосуваннях хімічних баз даних..

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

Див. також

Посилання