Given a graph G, is it possible to ask Sage to generate all possible matchings of G? I know that G.matching() gives a maximum matching of G and I also know that Sage has an iterator which finds all perfect matchings of G.
If no command exists which asks Sage to give me all possible matchings of G, does anyone have an idea of how to write a program to ask Sage to do this?
I found another way! Given a graph G, ask Sage to create its line graph and then from there find all of the independent sets in the line graph. The independent sets in the line graph are precisely the matchings in the original graph. Here is the code for finding the matchings in K4,5:
from sage.graphs.independent_sets import IndependentSets
B45=graphs.CompleteBipartiteGraph(4,5)
L_B45=B45.line_graph()
M=[x for x in IndependentSets(L_B45)]I don't know how efficient this is, but to find all matchings with a fixed number of edges, you can do this:
sage: from itertools import combinations
sage: g = graphs.PetersenGraph()
sage: E = [e[:2] for e in g.edges()]
sage: E # edges without the labels
[(0, 1), (0, 4), (0, 5), (1, 2), (1, 6), (2, 3), (2, 7), (3, 4), (3, 8), (4, 9), (5, 7), (5, 8), (6, 8), (6, 9), (7, 9)]Now look for sets of n edges containing 2n different vertices, for example with n=5:
sage: [a for a in combinations(E, 5) if len(set().union(*a)) == 10]
[((0, 1), (2, 3), (4, 9), (5, 7), (6, 8)),
((0, 1), (2, 7), (3, 4), (5, 8), (6, 9)),
((0, 4), (1, 2), (3, 8), (5, 7), (6, 9)),
((0, 4), (1, 6), (2, 3), (5, 8), (7, 9)),
((0, 5), (1, 2), (3, 4), (6, 8), (7, 9)),
((0, 5), (1, 6), (2, 7), (3, 8), (4, 9))]That makes sense; then just needs a loop from 0 to vertices/2.
Asked: 5 years ago
Seen: 1,961 times
Last updated: Jun 23 '19
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
The documentation has matching_polynomial here; it's coefficients, ignoring the sign, tell you the number of matchings as the the number of edges increases. The matching polynomial for the Petersen graph is x^10 - 15x^8 + 75x^6 - 145x^4 + 90x^2 - 6 which would be interpreted as 1 matching with 0 edges, 15 matchings with 1 edge, 75 matchings with 2 edges, 145 matchings with 3 edges, 90 matchings with 4 edges, and 6 matchings with 5 edges. It doesn't list the matchings but the documentation mentions an algorithm used to get the polynomial.
Thank you for your comment. Yes, I was aware that Sage can compute the matching polynomial of a graph, which is why I am surprised that it cannot list the matching themselves if it can count them.
What I am trying to figure out now is the following: Given a the edge set E of a graph, how can I get Sage to give me all possible subsets of E which contain pairs with completely distinct entries, i.e., a matching.
I suppose you could work recursively: ask for all maximal matchings in
G, and then ask for all maximal matchings inGwith a single edge removed, etc.A problem with my suggestion is that I don't know how to get Sage to tell me all maximal matchings. It produces a single one easily enough, but I don't know about all of them.