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.