#17132: Perfect Matchings for Graphs
-------------------------------------+-------------------------------------
Reporter: ayyer | Owner:
Type: task | Status: new
Priority: minor | Milestone: sage-6.4
Component: graph theory | Resolution:
Keywords: perfect | Merged in:
matchings, graphs | Reviewers:
Authors: Arvind Ayyer | Work issues:
Report Upstream: N/A | Commit:
Branch: | 88e58625775dfa5cea13db7336dc5f5371ab3768
public/ayyer/perfect_matchings | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by ncohen):
Hello !
> Oh, I see now! You want me to create another function which will delete
the vertices without creating a copy. Here's what I did, and it seems to
work. It seems a bit long though...
Ahahah. Well, actually this code creates a copy too, you even call the
graph constructor !
I was thinking of this code:
{{{
def matchings(G):
if G.order() == 0:
yield []
return
v = G.vertex_iterator().next()
Nv = G.neighbors(v)
G.delete_vertex(v)
for u in Nv:
Nu = G.neighbors(u)
G.delete_vertex(u)
for partial_matching in matchings(G):
partial_matching.append((u,v))
yield partial_matching
G.add_vertex(u)
G.add_edges((u,nu) for nu in Nu)
G.add_vertex(v)
G.add_edges((v,nv) for nv in Nv)
sage: abs(graphs.PetersenGraph().matching_polynomial()(0))
6
sage: len(list(matchings(graphs.PetersenGraph())))
6
sage: abs(graphs.ChvatalGraph().matching_polynomial()(0))
52
sage: len(list(matchings(graphs.ChvatalGraph())))
52
}}}
Note that it can be made more efficient by branching when it is not
connected, which would lead to a check that all connected components are
of even size, etc, etc... But then it depends on the size of the graphs
that are of interest to you, as those optimization can cost a lot on small
instances.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17132#comment:28>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
