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...
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