Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Hellooo !!!

If you have noticed that the orderings in the vertices are not the same, then most probably the two graphs will not be equal. To be equal, if I am not mistaken, the two adjacency matrices of the graphs first need to be equal (element per element). Of course, they will not be if the rows have been reordered. Even when this is true, Sage may say that two graphs are not equal if one has labeled edges why the other doesn't (this is not your case), or if the names of the vertices are somehow different. Beware, because this can also happen in tricky cases, I suspect it may answer that the graphs are different if you have in one graph vertices which are Integer() object, and in the other vertices which are int objects.

Well. Anyway, whenever you have two graphs which you suspect may be "equivalent", you are probably looking for the is.isomorphic method. This will tell you whether there is a bijection between the vertices such that each edge is sent to an edge, and each nonedge to a nonedge.

It can also tell you how to permute the vertices such that this is true. For instance :

sage: g = graphs.PetersenGraph()
sage: h = graphs.KneserGraph(5,2)
sage: g.is_isomorphic(h, certify = True)
(True, {0: {4, 5}, 1: {1, 3}, 2: {2, 5}, 3: {1, 4}, 4: {2, 3}, 5: {1, 2}, 6: {2, 4}, 7: {3, 4}, 8: {3, 5}, 9: {1, 5}})

Tell me if that help :-)