Say there is a task to determine whether two graphs are isomorphic, given a picture of the graphs. However the graphs are really complex, with a lot of vertices and edges, and things like number of vertices or edges and degrees are the same and it is really difficult to count triangles, or any other cycle, or to find what to swap. What to do then?

Sometimes I spend about 4 hours to find an isomorphism, so I was thinking : is there some more efficient way? Can maybe the adjacency matrix help?

  • $\begingroup$ Did the related questions not help? I appreciate they are usually asking about particular examples and you are asking about more general techniques, but still. $\endgroup$ – gilleain Sep 21 '16 at 12:05
  • $\begingroup$ Just to clarify: You are not interested in computer algorithm to test whether two given graphs are isomorphic, but in problems when you should check this "by hand", i.e. without use of computers. Is that correct interpretation of your question? (At least that is my impression from the first paragraph of your question, I am not sure about the second one.) $\endgroup$ – Martin Sleziak Sep 21 '16 at 12:24
  • $\begingroup$ Yes, that is correct interpretation of my question. $\endgroup$ – dreamer Sep 21 '16 at 12:32
  • $\begingroup$ I assumed that maybe I see something if I write adjacency matrix for graphs $\endgroup$ – dreamer Sep 21 '16 at 12:35
  • 1
    $\begingroup$ @dreamer I doubt that there are a lot of 'good' heuristic ways of checking for graph isomorphism by hand, except to manually perform an algorithm that would normally be given to a computer. Why do you need to manually check for isomorphisms? $\endgroup$ – Chris Harshaw Sep 21 '16 at 20:49

The Wikipedia article on graph isomorphism problem has pretty extensive discussion, describing the state of the art, practical algorithms, solved special cases etc.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.