I'll answer my own question:-)
There is an easily written function which does this:
def fundamental_cycle(G, T, e):
"""
Finds the unique cycle associated to the
spanning tree T of G and the edge e of G not in T.
INPUT:
G - a connected graph
T - a spanning tree
e - an edge of G not in T
OUTPUT:
the unique circuit in the graph T+e
EXAMPLES:
sage: G = graphs.HeawoodGraph()
sage: mst = G.min_spanning_tree()
sage: TG = G.subgraph(edges=mst)
sage: e = G.edges()[-1]
sage: e in TG
False
sage: fundamental_cycle(G, TG, e)
[(12, 3, None), (3, 2, None), (2, 1, None),
(1, 0, None), (0, 13, None), (13, 12, None)]
"""
mst = G.min_spanning_tree()
u = e[0]
v = e[1]
P = T.shortest_path(u,v)
Pu = P+[u]
cycle = [(Pu[i],Pu[i+1],None) for i in range(len(P))]
return cycle
On Sun, Feb 28, 2010 at 5:42 AM, David Joyner <wdjoy...@gmail.com> wrote:
> Hi:
>
> I'm trying to compute fundamental circuits of a
> graph in Sage and am getting stuck. Is this implemented?
>
> Here is an example:
>
> sage: G = graphs.HeawoodGraph()
> sage: TG = G.subgraph(edges=G.min_spanning_tree())
> sage: e = G.edges()[-1]
> sage: TG.edges()
> [(0, 1, None), (0, 5, None), (0, 13, None), (1, 2, None), (1, 10,
> None), (2, 3, None), (2, 7, None), (3, 4, None), (3, 12, None), (4, 9,
> None), (5, 6, None), (6, 11, None), (7, 8, None)]
> sage: TG.add_edge(e)
> sage: TG.edges()
> [(0, 1, None), (0, 5, None), (0, 13, None), (1, 2, None), (1, 10,
> None), (2, 3, None), (2, 7, None), (3, 4, None), (3, 12, None), (4, 9,
> None), (5, 6, None), (6, 11, None), (7, 8, None), (12, 13, None)]
> sage: G.girth()
> 6
> sage: TG.girth()
> 6
>
> This has the circuit 0 - 1 - 2 - 3 - 12 - 13 - 0 of length 6.
> I'd like to know if there is an easy way to get Sage to
> return the corresponding list of edges.
>
> - David Joyner
>
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
