CODEWITHSUNDEEP
algorithmlanguage-agnosticgraphgraph-theory
Olivier Lalonde
Olivier Lalonde

Reputation: 19958

Algorithm for determining if 2 graphs are isomorphic

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...

Upvotes: 13

Views: 21293

Answers (4)

Sushant
Sushant

Reputation: 1

In general, it is not a simple task to prove that two graphs are isomorphic. For that reason we must consider some properties of isomorphic graphs. That means those properties must be satisfied if the graphs are isomorphic. If the given graph does not satisfy these properties then we can say they are not isomorphic graphs.

Property: Two graphs are isomorphic if and only if for some ordering of their vertices their adjacency matrices are equal.

Based on the above property we can decide whether the given graphs are isomorphic or not. In order to check the property, we need to do some matrix transformation operations.

Upvotes: 0

Alex Spencer
Alex Spencer

Reputation: 862

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.

Upvotes: 1

trg787
trg787

Reputation: 219

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

Upvotes: 6

Mark Byers
Mark Byers

Reputation: 839254

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

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.

Upvotes: 10

Related Questions