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.Mon, 29 Jul 2019 01:36:01 +0200How to compute a perfect matching in a general graph?https://ask.sagemath.org/question/47280/how-to-compute-a-perfect-matching-in-a-general-graph/Are there functions to compute a maximal or perfect matching, or all the maximal/perfect matchings in a general (bipartite or non-bipartite) graphSun, 28 Jul 2019 08:09:48 +0200https://ask.sagemath.org/question/47280/how-to-compute-a-perfect-matching-in-a-general-graph/Answer by tmonteil for <p>Are there functions to compute a maximal or perfect matching, or all the maximal/perfect matchings in a general (bipartite or non-bipartite) graph</p>
https://ask.sagemath.org/question/47280/how-to-compute-a-perfect-matching-in-a-general-graph/?answer=47285#post-id-47285If you just want a perfect matching, you can use:
sage: p = G.matching()
If you want to iterate over all parfect matching, you can use (but it might be very slow as it is a brute force approach):
sage: for p in G.perfect_matchings():
....: blah
Sun, 28 Jul 2019 21:17:22 +0200https://ask.sagemath.org/question/47280/how-to-compute-a-perfect-matching-in-a-general-graph/?answer=47285#post-id-47285Answer by dazedANDconfused for <p>Are there functions to compute a maximal or perfect matching, or all the maximal/perfect matchings in a general (bipartite or non-bipartite) graph</p>
https://ask.sagemath.org/question/47280/how-to-compute-a-perfect-matching-in-a-general-graph/?answer=47289#post-id-47289You should download the PDF documentation which is available [here](http://doc.sagemath.org/pdf/en/reference/graphs/graphs.pdf). On page 222 there are 3 listed:
1. matching() Return a maximum weighted matching of the graph represented by the list of its edges.
2. has_perfect_matching() Return whether this graph has a perfect matching
3. perfect_matchings() Return an iterator over all perfect matchings of the graph.
Clicking on each method will bring you to more instructions and examples.
Mon, 29 Jul 2019 01:36:01 +0200https://ask.sagemath.org/question/47280/how-to-compute-a-perfect-matching-in-a-general-graph/?answer=47289#post-id-47289