mb wrote:
> Hi,
>
> It seems to me that the following is a bug.
>
> [EMAIL PROTECTED]:~$ sage
> ----------------------------------------------------------------------
> | SAGE Version 3.0, Release Date: 2008-04-22 |
> | Type notebook() for the GUI, and license() for information. |
> ----------------------------------------------------------------------
>
> In [1]: G=Graph()
> In [2]: G.add_edges([(0,1,'a')])
> In [3]: H=Graph()
> In [4]: H.add_edges([(0,1,'b')])
> In [5]: G.is_isomorphic(H)
> Out[5]: True
> In [6]: G.is_isomorphic(H,edge_labels=True)
> Out[6]: True
>
> That is, G and H are graphs consisting of one edge, but one is labeled
> 'a' and the other 'b'. So as labeled graphs they shouldn't be
> isomorphic.
I suppose it depends on the interpretation. I think the interpretation
used by the function is:
Is there some relabeling of vertices so that there is also a
corresponding relabeling of edges such that the graphs are exactly equal
(i.e., the vertices and edge labels exactly match up?). If so, then the
graphs are isomorphic. In other words, the *actual* edge labels don't
matter, it's just the structure of those edge labels that matters.
In the example you give, by replacing "a" by "b" in G, you get H, so
they are isomorphic. The algorithm does correctly distinguish between
the following G and H:
sage: G=Graph({0:{1: 'first'}, 1:{2: 'first'}, 2:{3:'second'}})
sage: H=Graph({0:{1: 'outer'}, 1:{2: 'inner'}, 2:{3:'outer'}})
sage: G.is_isomorphic(H)
True
sage: G.is_isomorphic(H, edge_labels=True)
False
Note that in this case, there is no relabeling of the vertices such that
a corresponding relabeling of edges gives identical graphs.
Robert (or Steve or anyone), please correct my explanation if I'm in error.
Thanks,
Jason
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
