# Given two adjacency matrices, how can I find if they're isomorphic?

Matrix 1: \begin{matrix} 0&1&1&0\\ 1&0&1&0\\ 1&1&0&1\\ 0&0&1&0 \end{matrix}

Matrix 2: \begin{matrix} 0&1&1&1\\ 1&0&0&0\\ 1&0&0&1\\ 1&0&1&0 \end{matrix}

I've looked on google to find out how to do this, but I can't find an answer that makes sense to me. As far as I can tell, there is no efficient algorithm to do this, so you need to check all the permutations... but I don't even know how to start. Any help would be great, Thanks.

-
Draw the graphs... –  draks ... Nov 28 '12 at 14:40

As isomorphims have to preserve degree, there are only 2 possible ones, the first given by $$\phi_1 \colon 1\mapsto 3, 2 \mapsto 4, 3 \mapsto 1, 4 \mapsto 2$$ and $$\phi_2 \colon 1\mapsto 4, 2 \mapsto 3, 3 \mapsto 1, 4 \mapsto 2$$ $\phi_1$ maps the first matrix to (that means the following matrix has $a_{\phi_1^{-1}(i), \phi_1^{-1}(j)}$ as $(i,j)$-th entry. $$\begin{pmatrix} 0&1&1&1\\ 1&0&0&0\\ 1&0&0&1\\ 1&0&1&0 \end{pmatrix}$$ and so $\phi_1$ is an isomorphism.

-
OK - This helps a lot. I can see now how you applied the algorithm to do this. –  agent154 Nov 28 '12 at 14:49

I think my solution is a better way of finding solution to your questions As question is given in MATRIX form.I think its better to do total solution in Matrices.

Firstly Concept : Matrix M be the matrix we get by multiplying adjacency matrix and its TRANSPOSE (A').

  Matrix M will be = [a ij] : where a ij is the number of edges from Vi to Vj if i is not equal to j and a ii is the number of edges incident to i(V is the vertices set of the given matrix).


So if we find Matrices M1 and M2 for the two given matrices..and checking whether identical terms are there are not. If identical numbers are there in Matrices, then both graphs are ISOMORPHIC. and from these matrices (if they are ISOMORPHIC)we find which element of first graph points to which element of secong graph.

P.S : If this kinda is not there is any book..this method is called MY METHOD (MY ="my name"). P.P.S : this is my first answer in this website..:P

-