Розпізнавання ізоморфізму графа. Його практичне застосування включає перш за все хіміоінформатику, математичну хімію (ідентифікація хімічних сполук) та автоматизацію електронного проектування (перевірка
різних зображень дизайну електронної схеми).
Графовий ізоморфізм (GI) набув популярності в теоретичній спільноті в 1970-х роках, коли він виник як одна з небагатьох природних проблем у класі складності NP, яку не можна було класифікувати як складну (NP-повну) або продемонструвати як розв’язну за допомогою ефективного алгоритму (тобто алгоритм поліноміального часу).
Оскільки ізоморфізм зберігає певний структурний аспект множини або математичної групи, його часто використовують. відобразити складну множину на простішу або більш відому множину, щоб встановити властивості вихідної множини, Ізоморфізми є одним із предметів, що вивчаються в теорії груп.
Ізоморфізм графів є областю зіставлення шаблонів і широко використовується в різних програмах, таких як обробка зображень, структура білка, комп’ютерна та інформаційна система, структура хімічного зв’язку, соціальні мережі, У цій статті розглядаються як різні застосування ізоморфізму графів, так і їхнє значення для суспільства.
Графи G і H ізоморфні якщо існує структура, яка зберігає взаємно-однозначну відповідність між вершинами та ребрами, Іншими словами, два графи відрізняються лише назвами ребер і вершин, але структурно еквівалентні, як зазначено в Колумбійському університеті.
Якщо два графи ізоморфні, вони повинні мати однакові інваріанти, наприклад, однакова кількість вершин, однакова кількість ребер, однакова послідовність ступенів (аж до перевпорядкування), однакова кількість компонентів, однаковий діаметр (для відповідних компонентів) тощо.