РОЗРОБКА ТА РЕАЛІЗАЦІЯ АЛГОРИТМУ УПІЗНАННЯ ІЗОМОРФНОСТІ ГРАФІВ
DOI:
https://doi.org/10.31891/2307-5732-2024-335-3-37Ключові слова:
графи, ізоморфність графів, матричний метод, матриця суміжності, об’єктно-орієнтоване програмування, C#, аналіз графів, оптимізація, алгоритмиАнотація
Стаття присвячена проблемі створення алгоритму та програми встановлення ізоморфності двох даних графів методом перебору; дослідженню обчислювальної ефективності створеного алгоритму упізнання ізоморфності графів. Досліджено проблему ізоморфності графів та запропоновано її практичну реалізацію на мові програмування C#. Розглянуто теоретичні аспекти задачі, запропоновано алгоритм для її вирішення і продемонстровано його втілення у програмному забезпеченні, в тому числі, поняття графу, як структури, що складається з об'єктів (вершин) та зв'язків між ними (ребер). Ізоморфність двох графів означає, що між ними існує особливий зв'язок (бієкція), який зберігає структуру зв'язків. Іншими словами, графи можна "перетворити" один в один, переставляючи та перейменовуючи вершини, не руйнуючи загальної картини. Визначення ізоморфності графів має важливе значення в багатьох сферах, таких як розробка комп'ютерних чипів, аналіз еволюції, контроль натовпу та хімії.
Робота пропонує алгоритм для визначення ізоморфності графів, що ґрунтується на порівнянні матриць суміжності. Матриця суміжності – таблиця, де кожен елемент показує, чи існує зв'язок між двома певними вершинами. Для реалізації алгоритму розроблено програмне забезпечення на C#. Воно дозволяє додавати та видаляти вершини й ребра, отримувати матриці суміжності, визначати ізоморфність графів та їх класифікувати. Програмне забезпечення успішно протестовано на різних типах графів. Відзначено використання об'єктно-орієнтованого програмування (ООП) для чіткої та структурованої організації коду. Також реалізовано зручний інтерфейс командного рядка для роботи з графами. Загалом, програма може бути корисною для вирішення різних задач, пов'язаних з аналізом графів. Важливим напрямком досліджень є час роботи алгоритму та його порівняння з іншими методами визначення ізоморфності графів. Корисним є дослідити приклади використання програмного забезпечення для вирішення реальних задач, зробити код програми відкритим для публічного використання.
