Ask Your Question
1

find all matchings in a graph

asked 2019-06-21 17:05:51 -0500

merluza gravatar image

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?

edit retag flag offensive close merge delete

Comments

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.

dazedANDconfused gravatar imagedazedANDconfused ( 2019-06-21 19:08:11 -0500 )edit

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.

merluza gravatar imagemerluza ( 2019-06-21 22:22:40 -0500 )edit

I suppose you could work recursively: ask for all maximal matchings in G, and then ask for all maximal matchings in G with a single edge removed, etc.

John Palmieri gravatar imageJohn Palmieri ( 2019-06-22 17:07:44 -0500 )edit

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.

John Palmieri gravatar imageJohn Palmieri ( 2019-06-22 17:24:04 -0500 )edit

2 answers

Sort by ยป oldest newest most voted
1

answered 2019-06-23 12:11:49 -0500

merluza gravatar image

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 $K_{4,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)]
edit flag offensive delete link more
1

answered 2019-06-22 17:17:09 -0500

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))]
edit flag offensive delete link more

Comments

That makes sense; then just needs a loop from 0 to vertices/2.

dazedANDconfused gravatar imagedazedANDconfused ( 2019-06-22 19:13:29 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2019-06-21 17:05:51 -0500

Seen: 76 times

Last updated: Jun 23