Thursday, March 13, 2014

Using the maximized cm from last post to check for isomorphism

I was just checking a few cases to see whether the algorithm from the last blog post works in practice. Here are two graphs:
Here are the two connectivity matrices. The first is rows a-j have a 1 if they are connected to a vertex a-j. And similarly for the second.  :
When I run my program on both of these above matrices to write the maximized matrix they both come out to:

So clearly the two graphs are isomorphic. I just still don't know whether this always works, but it is very fast and there can't be false positives so it might be good as a first check. 

No comments:

Post a Comment