Algorithm for determining if 2 graphs are isomorph

问题:

Disclaimer: I'm a total newbie at graph theory and I'm not sure if this belongs on SO, Math SE, etc.

Given 2 adjacency matrices A and B, how can I determine if A and B are isomorphic.

For example, A and B which are not isomorphic and C and D which are isomorphic.

A = [ 0 1 0 0 1 1     B = [ 0 1 1 0 0 0
      1 0 1 0 0 1           1 0 1 1 0 0
      0 1 0 1 0 0           1 1 0 1 1 0
      0 0 1 0 1 0           0 1 1 0 0 1
      1 0 0 1 0 1           0 0 1 0 0 1
      1 1 0 0 1 0 ]         0 0 0 1 1 0 ]

C = [ 0 1 0 1 0 1     D = [ 0 1 0 1 1 0
      1 0 1 0 0 1           1 0 1 0 1 0
      0 1 0 1 1 0           0 1 0 1 0 1
      1 0 1 0 1 0           1 0 1 0 0 1
      0 0 1 1 0 1           1 1 0 0 0 1
      1 1 0 0 1 0 ]         0 0 1 1 1 0 ]   

(sorry for this ugly notation, I'm not quite sure how to draw matrices on SO)

Here's how I've started my algorithm (pardon my lack of mathematical rigor) please help me complete/correct!

1. If size (number of edges, in this case amount of 1s) of A != size of B => graphs are not isomorphic
2. For each vertex of A, count its degree and look for a matching vertex in B which has the same degree and was not matched earlier. If there is no match => graphs are not isomorphic.
3. Now that we cannot quickly prove that A and B are not isomorphic, what's the next step? Would it be correct try every permutation of lines in A until A matches B? Really not sure about this one...

回答1:

That's a quite difficult problem to solve. There is a Wikipedia page about it:

• Graph isomorphism problem

According to that page there are a number of special cases that have been solved with efficient polynomial time solutions, but the complexity of the optimal solution is still unknown.

回答2:

My project - Griso - at sf.net: http://sourceforge.net/projects/griso/ with this description:
Griso is a graph isomorphism testing utility written in C++ and based on my own algo.
See Griso's sample input/output on this page: http://funkybee.narod.ru/graphs.htm

回答3:

Well, it is very easy to quickly tell that they ARE NOT isomorphic by doing the following. areIsomorphic(G1, G2): if(G1.num_verticies != G2.num_verticies) return False if(G1.num_total_edges != G2.num_total_edges) return False for each vertex v in G1: if( G2.find(v).edges != v.edges): return False; //Try and find a property in graph G1 that does not exist in G2. // Use a heuristic. ie- try and find nonmutually adjacenct sets.