analytics

Friday, November 13, 2015

A standard form for adjacency matrices to solve the graph isomorphism problem

Supposing you have some graph with no more than one edge between vertices:
Here A, B, and C are all connected to themselves but they don't have to be, the above graph has adjacency matrix:
Indicating with a 1 where a row, column pair of vertices are connected...

Now a problem is to find a standard form for this and all  adjacency matrices corresponding to isomorphic graphs, though maybe the vertices are labeled differently...

First define a row's C to be a binary number corresponding to the row with the most significant digit to the right.. for example the first row above reads as 1100 so that would be the binary number for decimal 3 or 2^0 + 2^1

The algorithm I'm proposing is to simultaneously swap two rows and corresponding columns producing a new matrix if it increases a row's C with importance towards the top row. For example, swap two columns and corresponding rows if it either increases the first row's C or if that's not possible,  the second rows C while also not making the first row's C less, or if that's not possible swap so the third row's C is increased while at the same time not making row 1's and row 2's C less, etc... Each iteration of the algorithm I call an "improvement" of the adjacency matrix, the algorithm is done when no more improvements are possible...



Above is 3 steps of the algorithm describing which rows and columns are to be swapped highlighted in red and which row is improved on the new matrix after the swapping... The final matrix on the right can not be improved by the above definition by swapping any pair of rows and  corresponding columns... I think the exact specifics of how to choose which rows and corresponding columns is not important to the final result which by definition can not be improved...

So the final matrix is I believe in a standard form for all adjacency matrices corresponding to isomorphic graphs. In other words all adjacency matrices corresponding to isomorphic graphs and only to isomorphic graphs will improve to a particular unique standard matrix at the end of the algorithm...


No comments:

Post a Comment