4
$\begingroup$

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.

  • 3
    Draw the graphs...2012-11-28

2 Answers 2

4

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.

0

I think there is a better way of finding a solution to your question. As the question is given in MATRIX form. I think it's better to do total solution in Matrices.

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