ON THE DEVELOPMENT AND IMPLEMENTATION OF THE GRAPH ISOMORPHITY RECOGNITION ALGORITHM

Abstract

The article is devoted to the problem of creating an algorithm and a program for establishing the isomorphism of two given graphs by the iterative method; study of computational efficiency of the created algorithm for graph isomorphism recognition. This paper delves into the problem of graph isomorphism and presents its practical implementation using the C# programming language. It explores the theoretical aspects of the problem, proposes an algorithm for its resolution, and demonstrates its embodiment in software. A graph is a structure composed of objects (vertices) and connections between them (edges). The isomorphism of two graphs implies the existence of a special connection (bijection) between them that preserves the structure of the connections. In other words, graphs can be "transformed" into each other by rearranging and renaming vertices without disrupting the overall picture. Determining graph isomorphism is crucial in various fields, including computer chip design, evolutionary analysis, crowd control, and chemistry. The paper proposes an algorithm for determining graph isomorphism based on comparing adjacency matrices. An adjacency matrix is a table where each element indicates whether a connection exists between two specific vertices. Was developed software on C# to implement the algorithm. It allows adding and removing vertices and edges, obtaining adjacency matrices, determining graph isomorphism, and classifying graphs. The software was successfully tested on various graph types. It is worth noting the use of object-oriented programming (OOP) for clear and structured code organization. A user-friendly command-line interface was also implemented for working with graphs. Overall, the program can be beneficial for solving various tasks related to graph analysis. However, there is room for improvement. An essential research direction is investigating the algorithm's runtime and comparing it to other graph isomorphism determination methods. It would also be beneficial to include examples of using the software to solve real-world problems. Ideally, the program's code should be made open-source.