ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 23 Jun 2019 19:11:49 +0200find all matchings in a graphhttps://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/ 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?Sat, 22 Jun 2019 00:05:51 +0200https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/Comment by dazedANDconfused for <p>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$. </p>
<p>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?</p>
https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?comment=46965#post-id-46965The documentation has matching_polynomial [here](http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/matchpoly.html?highlight=matching_polynomial); 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 - 15*x^8 + 75*x^6 - 145*x^4 + 90*x^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.Sat, 22 Jun 2019 02:08:11 +0200https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?comment=46965#post-id-46965Comment by merluza for <p>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$. </p>
<p>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?</p>
https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?comment=46966#post-id-46966Thank 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.Sat, 22 Jun 2019 05:22:40 +0200https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?comment=46966#post-id-46966Comment by John Palmieri for <p>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$. </p>
<p>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?</p>
https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?comment=46972#post-id-46972I 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.Sun, 23 Jun 2019 00:07:44 +0200https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?comment=46972#post-id-46972Comment by John Palmieri for <p>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$. </p>
<p>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?</p>
https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?comment=46974#post-id-46974A 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.Sun, 23 Jun 2019 00:24:04 +0200https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?comment=46974#post-id-46974Answer by John Palmieri for <p>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$. </p>
<p>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?</p>
https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?answer=46973#post-id-46973I 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))]
Sun, 23 Jun 2019 00:17:09 +0200https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?answer=46973#post-id-46973Comment by dazedANDconfused for <p>I don't know how efficient this is, but to find all matchings with a fixed number of edges, you can do this:</p>
<pre><code>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)]
</code></pre>
<p>Now look for sets of <code>n</code> edges containing <code>2n</code> different vertices, for example with n=5:</p>
<pre><code>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))]
</code></pre>
https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?comment=46975#post-id-46975That makes sense; then just needs a loop from 0 to vertices/2.Sun, 23 Jun 2019 02:13:29 +0200https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?comment=46975#post-id-46975Answer by merluza for <p>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$. </p>
<p>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?</p>
https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?answer=46982#post-id-46982I 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)]
Sun, 23 Jun 2019 19:11:49 +0200https://ask.sagemath.org/question/46964/find-all-matchings-in-a-graph/?answer=46982#post-id-46982