Thursday, August 8, 2013

Test for graph isomorphism

I noticed if you translate 2 graphs into an connectivity matrix like so:

These two graphs are obviously isomorphic as I've just relabeled the graph. But I've found that perhaps this can be captured by this relationship I've found of their connectivity matrices:

What I'm showing is that if you multiply the adjacency matrices and then multiply then changing the order of the multiplication (because matrix multiplication isn't commutative), you produce two matrices that are the transpose of one another. 


I actually found counterexamples that suggest that any time you multiply both ways two valid connectivity matrices that meaning that they have the symmetry that the ith row and jth column and the jth column and ith row are the same, you end up with transposes, so it doesn't point out that they are isometric after all. 

No comments:

Post a Comment