Comparing Graphs Using Matrices

A naive approach to solving the graph isomorphism problems is to look at the Adjacency Matrix of each graph.  If they are identical, then the graphs are isomorphic, with a trivial mapping of vertices.  Unfortunately, a graph with N vertices may have up to N! different adjacency matrices, obtained from N! different renumberings of its vertices.  Thus, checking adjacency matrices has a run time of .

Here are two graphs A and A'.  If we renumber the vertices of A, we produce an isomorphic graph A'.

A : A' :

By renumbering the vertices of the graph, we affect the corresponding adjacency matrices of the graph.

         

Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.