Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Draw the graphs... – draks ... Nov 28 '12 at 14:40
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.