The goal is to determine whether two undirected weighted graphs are isomorphic using spectral information. Efficient algorithms for the solution of the graph isomorphism or graph matching problem are required in a wide variety of different areas such as pattern recognition, object detection, face recognition, and fingerprint analysis. There exists no polynomial-time algorithm to check whether two arbitrary graphs are isomorphic. The graph isomorphism problem is one of only a few problems for which the complexity class is still unknown.
Two graphs and
with adjacency matrices
and
are said to be isomorphic if one of the following equivalent conditions is satisfied:
- There exists a permutation
such that
, where
denotes the symmetric group of degree
.
- There exists a permutation matrix
such that
, where
is the set of all
permutation matrices.