Thread: Graph Isomorphism Problem

Hi,

About a week ago I posted this question but there were no replies and I am not sure why. Maybe because the question is too trivial for this forum I am not sure. I would really appreciate a reply to this question, or if this question does not belong on this forum can someone direct me to some forums where I could post this question?

Here is the question again. As I iterated before I am not a mathematician so bear with me!!


I would like to just clarify my understanding of isomorphism using the following 4 adjacency matrices for the following parameters:

Where:

v=10
k=6
t=3

And there are 10 blocks in each of the 4 matrices and all 4 matrices satisfy the parameters.



Matrix A:

{ 1, 2, 3, 4, 6, 7}
{ 1, 2, 3, 5, 8,10}
{ 1, 2, 3, 7, 9,10}
{ 1, 2, 4, 6, 8,10}
{ 1, 3, 4, 5, 6, 9}
{ 1, 4, 5, 7, 8, 9}
{ 2, 4, 5, 6, 9,10}
{ 2, 5, 6, 7, 8, 9}
{ 3, 4, 5, 7, 8,10}
{ 3, 6, 7, 8, 9,10}


Matrix B:

{ 1, 2, 3, 4, 6, 7}
{ 1, 2, 3, 5, 8,10}
{ 1, 2, 3, 7, 9,10}
{ 1, 2, 4, 6, 8,10}
{ 2, 3, 4, 5, 6, 9}
{ 1, 4, 5, 7, 8, 9}
{ 1, 4, 5, 6, 9,10}
{ 2, 5, 6, 7, 8, 9}
{ 3, 4, 5, 7, 8,10}
{ 3, 6, 7, 8, 9,10}


Matrix C:

{ 1, 2, 3, 4, 6, 7}
{ 1, 2, 3, 5, 7,10}
{ 1, 2, 3, 8, 9,10}
{ 1, 2, 4, 6, 8,10}
{ 1, 3, 4, 5, 6, 9}
{ 1, 4, 5, 7, 8, 9}
{ 2, 4, 5, 6, 9,10}
{ 2, 5, 6, 7, 8, 9}
{ 3, 4, 5, 7, 8,10}
{ 3, 6, 7, 8, 9,10}


Matrix D:

{ 1, 2, 3, 4, 6, 7}
{ 1, 2, 3, 5, 7,10}
{ 1, 2, 3, 8, 9,10}
{ 1, 2, 4, 6, 8,10}
{ 2, 3, 4, 5, 6, 9}
{ 1, 4, 5, 7, 8, 9}
{ 1, 4, 5, 6, 9,10}
{ 2, 5, 6, 7, 8, 9}
{ 3, 4, 5, 7, 8,10}
{ 3, 6, 7, 8, 9,10}






Based on my understanding of isomorphism NONE of these 4 matrices (A,B,C,D) are isomorphic because of the following comparing 2 matrices at a time:


For Matrix A:

Matrix A and B are not isomorphic because the 1 and 2 are relabeled only in blocks 5 & 7 (should be blocks 5,6,7 and 8)

Matrix A and C are not isomorphic because the 7 and 8 are relabeled only in blocks 2 & 3 (should be blocks 1,2,3 and 4)

Matrix A and D are not isomorphic because the 1 and 2 are relabeled only in blocks 5 & 7 (should be blocks 5,6,7 and 8) and also because 7 & 8 are relabeled only in blocks 2 & 3 (should be blocks 1,2,3 and 4).


For Matrix B:

Matrix B and C are not isomorphic because the 7 and 8 are relabeled only in blocks 2 & 3 (should be blocks 1,2,3 AND 4) and also because 1 & 2 are relabeled only in blocks 5 & 7 (should be blocks 5,6,7 and 8).

Matrix B and D are not isomorphic because the 7 and 8 are relabeled only in blocks 2 & 3 (should be blocks 1,2,3 and 4)


For Matrix C:

Matrix C and D are not isomorphic because the 1 and 2 are relabeled only in blocks 5 & 7 (should be blocks 5,6,7 and 8)


Is this right?

Are the 4 matrices (A,B,C,D) all non-isomorphic?

And if any are isomorphic, can you explain why they are?


Furthermore, would most software that compares 2 graphs to see if they are isomorphic catch these subtelties?

Thanks

At the moment, it is considered computationally difficult to determine whether or not two arbitrary graphs are isomorphic. You can read more about it on Wikipedia: Graph isomorphism problem - Wikipedia, the free encyclopedia

There are some necessary conditions that isomorphic graphs have: same number of vertices, edges, degree count, etc... If you can rule one of those out, then you can conclude that the graphs in question are not isomorphic. Otherwise, you will have to argue some other way (which can be difficult). Have you tried drawing the graphs and comparing them by sight?

Hi Roninpro,

Yes I had already read about it on Wikipedia. Actually, I have been doing a lot of research on the G.I.P. and I am at a point where I am past drawing graphs to compare 2 graphs as I think that it is a futile approach.

Looking at it from an objective standpoint, because I am not a mathematician, I think that the answer lies elsewhere then trying to draw 2 graphs. Furthermore, most graph invariants (vectors, arcs, eigenvalues, etc......) are very time consuming and are only a necessary but insufficient condition of proof. It seems to me that the subject of the G.I.P. has been beaten to death pretty much with the same approach over and over for the longest period of time and if you always do what you have done you will always get what you have gotten (A. E.) !!! So the answer obviously lies elsewhere, which is what I am searching.


Conceptually the idea of Graph Isomorphism stems from the fact that you are just relabeling the elements. For example, let's say I have Matrix A representing my first graph:

Matrix A:

{ 1, 2, 3, 4, 6, 7}
{ 1, 2, 3, 5, 8,10}
{ 1, 2, 3, 7, 9,10}
{ 1, 2, 4, 6, 8,10}
{ 1, 3, 4, 5, 6, 9}
{ 1, 4, 5, 7, 8, 9}
{ 2, 4, 5, 6, 9,10}
{ 2, 5, 6, 7, 8, 9}
{ 3, 4, 5, 7, 8,10}
{ 3, 6, 7, 8, 9,10}

Then if I was to relabel each 1 for a 2, I would get following Matrix:

{ 1, 2, 3, 4, 6, 7} // No need to change as 1 and 2 are together (Row 1)
{ 1, 2, 3, 5, 8,10} // No need to change as 1 and 2 are together (Row 2)
{ 1, 2, 3, 7, 9,10} // No need to change as 1 and 2 are together (Row 3)
{ 1, 2, 4, 6, 8,10} // No need to change as 1 and 2 are together (Row 4)
{ 2, 3, 4, 5, 6, 9} // changed the 1 for a 2 (Row 5)
{ 2, 4, 5, 7, 8, 9} // changed the 1 for a 2 (Row 6)
{ 1, 4, 5, 6, 9,10} // changed the 2 for a 1 (Row 7)
{ 1, 5, 6, 7, 8, 9} // changed the 2 for a 1 (Row 8)
{ 3, 4, 5, 7, 8,10}
{ 3, 6, 7, 8, 9,10}

In this case as you can see you really do not need to draw a graph or do any testing as you know they are isomoprhic:

- Rows 1,2,3,4 would result in the same rows if you interchanged the 1 and 2.
- Rows 5 and 6 you changed the 1 for a 2.
- Rows 7 and 8 you changed the 2 for a 1

As a matter of fact, you can continue to relabel any two numbers (10! ways to do that) and you would know that the resulting matrix would be isomorphic to Matrix A and therefore you would not have to draw any graph or do any computation whatsoever, right? So far so good?


But if you look really carefully at Matrix B below:


Matrix B:

{ 1, 2, 3, 4, 6, 7} // No need to change as 1 and 2 are together (Row 1)
{ 1, 2, 3, 5, 8,10} // No need to change as 1 and 2 are together (Row 2)
{ 1, 2, 3, 7, 9,10} // No need to change as 1 and 2 are together (Row 3)
{ 1, 2, 4, 6, 8,10} // No need to change as 1 and 2 are together (Row 4)
{ 2, 3, 4, 5, 6, 9} // changed the 1 for a 2 (Row 5)
{ 1, 4, 5, 7, 8, 9}
{ 1, 4, 5, 6, 9,10} // changed the 2 for a 1 (Row 7)
{ 2, 5, 6, 7, 8, 9}
{ 3, 4, 5, 7, 8,10}
{ 3, 6, 7, 8, 9,10}


- Rows 1,2,3,4 would result in the same rows if you interchanged the 1 and 2.
- Rows 5 you changed the 1 for a 2.
- Rows 7 you changed the 2 for a 1

But Rows 6 and 8 were not changed? Row 6 you should have changed the 1 for a 2 and Row 8 you should have changed the 2 for a 1 as they were in the first case! And yet both matrices A and B fullfill all the parameters of v=10, k=6 and t=3 that is they are both graphs and all 120 points (10 * 9 * 8 / 1 * 2 * 3) are covered.

Ditto for Matrix C where if you had Matrix A and you relabeled the 7 for an 8 you should have gotten the following:


{ 1, 2, 3, 4, 6, 8} // changed the 7 for a 8 (Row 1)
{ 1, 2, 3, 5, 7,10} // changed the 8 for a 7 (Row 2)
{ 1, 2, 3, 8, 9,10} // changed the 7 for a 8 (Row 3)
{ 1, 2, 4, 6, 7,10} // changed the 8 for a 7 (Row 4)
{ 1, 3, 4, 5, 6, 9}
{ 1, 4, 5, 7, 8, 9} // No need to change as 7 and 8 are together (Row 10)
{ 2, 4, 5, 6, 9,10}
{ 2, 5, 6, 7, 8, 9} // No need to change as 7 and 8 are together (Row 10)
{ 3, 4, 5, 7, 8,10} // No need to change as 7 and 8 are together (Row 10)
{ 3, 6, 7, 8, 9,10} // No need to change as 7 and 8 are together (Row 10)

But once again look if you look at Matrix C:


Matrix C:

{ 1, 2, 3, 4, 6, 7}
{ 1, 2, 3, 5, 7,10} // changed the 8 for a 7 (Row 2)
{ 1, 2, 3, 8, 9,10} // changed the 7 for a 8 (Row 3)
{ 1, 2, 4, 6, 8,10}
{ 1, 3, 4, 5, 6, 9}
{ 1, 4, 5, 7, 8, 9} // No need to change as 7 and 8 are together (Row 10)
{ 2, 4, 5, 6, 9,10}
{ 2, 5, 6, 7, 8, 9}// No need to change as 7 and 8 are together (Row 10)
{ 3, 4, 5, 7, 8,10} // No need to change as 7 and 8 are together (Row 10)
{ 3, 6, 7, 8, 9,10} // No need to change as 7 and 8 are together (Row 10)

Once again Row 1 and Row 4 were not changed as they should have been. And once again both matrices A and C fullfill all the parameters of v=10, k=6 and t=3 that is they are both graphs and all 120 points (10 * 9 * 8 / 1 * 2 * 3) are covered.


Finally, Matrix D is a combination of the changes in Matrix B and C (I will only show the result) where only


Matrix D:

{ 1, 2, 3, 4, 6, 7}
{ 1, 2, 3, 5, 7,10} // changed the 8 for a 7 (Row 2)
{ 1, 2, 3, 8, 9,10} // changed the 7 for a 8 (Row 3)
{ 1, 2, 4, 6, 8,10}
{ 2, 3, 4, 5, 6, 9} // changed the 1 for a 2 (Row 5)
{ 1, 4, 5, 7, 8, 9}
{ 1, 4, 5, 6, 9,10} // changed the 2 for a 1 (Row 7)
{ 2, 5, 6, 7, 8, 9}
{ 3, 4, 5, 7, 8,10}
{ 3, 6, 7, 8, 9,10}

And once again Matrix D like Matrix B and C, also satisfies all the parameters of v=10, k=6 and t=3 that is it covers all 120 points (10 * 9 * 8 / 1 * 2 * 3).


Therefore, it seems to me that from a graph isomorphic standpoint that all 4 matrices (A,B,C,D) are non-isomorphic, right???

Furthermore, is there some type of an encompassing classification of graph isomorphism that these 4 matrices would fall under or are they just classified as 4 non-isomorphic graphs?

I would dearly love a clear and concise answer.

Thanks
Juventus

Here is a link
Prof Mawata has actually written a program to check isomorphisms for 'small' graphs.
He may help in some ways if he is still working on this.

Originally Posted by Juventus

Hi Roninpro,

Yes I had already read about it on Wikipedia. Actually, I have been doing a lot of research on the G.I.P. and I am at a point where I am past drawing graphs to compare 2 graphs as I think that it is a futile approach.

Looking at it from an objective standpoint, because I am not a mathematician, I think that the answer lies elsewhere then trying to draw 2 graphs. Furthermore, most graph invariants (vectors, arcs, eigenvalues, etc......) are very time consuming and are only a necessary but insufficient condition of proof. It seems to me that the subject of the G.I.P. has been beaten to death pretty much with the same approach over and over for the longest period of time and if you always do what you have done you will always get what you have gotten (A. E.) !!! So the answer obviously lies elsewhere, which is what I am searching.

I didn't mean to suggest that drawing the two graphs is the best way to solve the problem. But since you are a human, and the graphs are small enough, it may be possible to do by sight. (In any case, it isn't always best to try to follow an algorithm as a human, even if it is computationally efficient. It can be become unwieldy without automation.) And of course, people realise the difficulties you mentioned, and this is why the isomorphism problem is an active problem for research.

I actually don't understand your argument. Are these adjacency matrices? You can't just arbitrarily shuffle numbers - it would disturb the relationships between the edges and vertices. Consider the following:

and

I have changed all of the 1s for 2s and vice versa. But you can see from the actual graphs that they are not isomorphic. (Some edges have been inserted in the process.)



Can you clarify what you mean? The argument between A and B would be enough - you don't have to do them all.

Hi,

Sorry maybe I should have clarified that these are covering designs (t-designs, Steiner Triple systems, etc....) but I thought that it was implicit by the v,k and t parameters.

With covering designs you want to be able to cover all the points that satisfy the parameters. In this case the parameters are v = 10, k = 10 and t = 3. Essentially what this says is that you want to cover all the permutations of 3 numbers (t = 3) from a pool of 10 elements (v = 10) using a block size of 6 (k = 6) and there are 120 ( 10 x 9 x 8 / ( 1 x 2 x 3)) such points:

Pt 1 - 1,2,3
Pt 2 - 1,2,4
Pt 3 - 1,2,5
.
.
.
Pt 120 - 8,9,10


So as I said for Matrix A below by interchanging any 2 elements such as the 1 with the 2, you are preserving all the characteristics (vertices, arcs, etc....) and also still covering all the points 120 of the parameters. But in Matrix B below not all the elements are relabeled as Row 6 and Row 8 are not and yet the parameters are still satisfied that is all 120 pts are covered.

Matrix A:

{ 1, 2, 3, 4, 6, 7}
{ 1, 2, 3, 5, 8,10}
{ 1, 2, 3, 7, 9,10}
{ 1, 2, 4, 6, 8,10}
{ 1, 3, 4, 5, 6, 9}
{ 1, 4, 5, 7, 8, 9}
{ 2, 4, 5, 6, 9,10}
{ 2, 5, 6, 7, 8, 9}
{ 3, 4, 5, 7, 8,10}
{ 3, 6, 7, 8, 9,10}


Matrix B:

{ 1, 2, 3, 4, 6, 7} // No need to change as 1 and 2 are together (Row 1)
{ 1, 2, 3, 5, 8,10} // No need to change as 1 and 2 are together (Row 2)
{ 1, 2, 3, 7, 9,10} // No need to change as 1 and 2 are together (Row 3)
{ 1, 2, 4, 6, 8,10} // No need to change as 1 and 2 are together (Row 4)
{ 2, 3, 4, 5, 6, 9} // changed the 1 for a 2 (Row 5)
{ 1, 4, 5, 7, 8, 9}
{ 1, 4, 5, 6, 9,10} // changed the 2 for a 1 (Row 7)
{ 2, 5, 6, 7, 8, 9}
{ 3, 4, 5, 7, 8,10}
{ 3, 6, 7, 8, 9,10}


I hope this makes it clearer.

Roy