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, 07 Dec 2015 17:49:08 +0100Check SDR in a bipartite graph by Hall's theorem.https://ask.sagemath.org/question/31379/check-sdr-in-a-bipartite-graph-by-halls-theorem/How can I check existence of a complete SDR in a bipartite graph ?
This will be done by checking if there is a perfect matching in the graph(Hall's marriage theorem), but How can I implement this in SAGE?
Mon, 07 Dec 2015 17:39:04 +0100https://ask.sagemath.org/question/31379/check-sdr-in-a-bipartite-graph-by-halls-theorem/Answer by tmonteil for <p>How can I check existence of a complete SDR in a bipartite graph ? </p>
<p>This will be done by checking if there is a perfect matching in the graph(Hall's marriage theorem), but How can I implement this in SAGE?</p>
https://ask.sagemath.org/question/31379/check-sdr-in-a-bipartite-graph-by-halls-theorem/?answer=31380#post-id-31380You can ask for a maximal matching and see if its size correspond to half the size of the bipartite graph:
You can get a maximal matching as follows:
sage: n = 10
sage: G = graphs.RandomBipartite(n,n,0.5)
sage: G.matching()
[((0, 1), (1, 0), None),
((0, 6), (1, 7), None),
((0, 4), (1, 4), None),
((0, 7), (1, 8), None),
((0, 9), (1, 9), None),
((0, 0), (1, 2), None),
((0, 5), (1, 6), None),
((0, 3), (1, 1), None),
((0, 8), (1, 5), None),
((0, 2), (1, 3), None)]
You can check that a maximal matching is complete as follows:
sage: len(G.matching()) == n
True
or as follows:
sage: G.matching(value_only=True) == n
True
Mon, 07 Dec 2015 17:49:08 +0100https://ask.sagemath.org/question/31379/check-sdr-in-a-bipartite-graph-by-halls-theorem/?answer=31380#post-id-31380