analytics

Sunday, September 29, 2013

Graph Isomorphism matrix

If you have a graph like:
Note that some of the edges are weighted, one vertex connects to itself, and one connection can cross another.
We can associate a connectivity matrix M with this graph like so:
Here, there is a in cell (x,y) if x and y are connected and the weight if any replaces the 1. 
Also a permutation matrix of the same size can be defined as any matrix that has one 1 in every row and every column, for example:

A nice theorem about these matrices is that if two graphs are isomorphic we can write:
P*M*P = N
where M is the connectivity matrix of graph M, and N is the connectivity matrix of graph N, and P is any permutation matrix. 
Proof:
P*M*P is the matrix you get when you first permute any number of rows of the matrix, and then do the same permutation on the columns. And this is exactly the same as taking the graph associated with the connectivity matrix and permuting the labeling any way. And of course two graphs are isomorphic if there is a way to permute the labeling so that you generate the same connectivity matrix. 
This isn't an if and only if because I found two non-isomorphic graphs that are related in this way by a permutation matrix. 




No comments:

Post a Comment