Cerca d’automorfismes i d’isomorfismes de grafs: algorismes i implementació

Abstract

Graph Isomorphism problem (GIP) consists in constructing an efficient algorithm for testing whether two graphs are isomorphics and to find, if it exists, one isomorphism,i.e, to find a one-to-one, onto mapping from the set of vertexs of one graph to the set of vertexs of the other graph, so that the edges remain the same. GIP is one of the most interesting problems in Discrete Mathematics, it is essential for Graph Theory as well as for computational complexity theory. The problem has interest in the theoretical side, because it is not known if it is a P or NP-complete problem. On the one hand it is known that many classes of graphs admit polynomial time algorithms for isomorphism testing, such as rooted trees, planar graphs, circular graphs, graphs with bounded vertex degree, etc. On the other hand, the search for isomorphism complete problems has produced a large list of problems, such as bipartite graph isomorphism, regular graph isomorphism, complement graph isomorphism, automorphism orbits search, automorphism generators search, etc. So, GIP is a good candidate for an intermediate computational status between P and NP problems. From the practical point of view, GIP has many applica tions for science and technology: pattern recognition, data mining, computer vision, chemistry and VLSI layout validation. During the last decades many algorithms have been born to solve the problem, most of them based on Canonical labeling and direct backtracking, but Brendan McKay’s Nauty algorithm has stood up among the others because its fine performing. In 2011, José Luis López Presa et al. tested Nauty with some special graphs, Miyazaki’s graphs, and confirmed that it was very slow to find isomorphisms. So, they developed a new algorithm, Conauto, which attacks the problem in an original way, using special techniques to prune the automorphisms searching tree, to become one of the fastest algorithms today. The aim of this work is, on the one hand, to study and analyze the theoretical background the algorithm Conauto relies on and, on the other hand, to try to perform any improvement in some aspects: it has been implemented a graphical interface to visualize the partitions on the graphs and it has been performed two different algorithms to calculate the whole automorphism group of the graph starting from a set of generators; a first one based on brute force (strength) and a second one based on the Schreier-Sims algorithm. An algoritm that calculates all isomorphisms between two graphs, starting from one previous isomorphism and the whole automorphism group of one of the graphs, have also been implemented.