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.Fri, 04 Sep 2020 18:15:04 +0200Maximal matching of a posethttps://ask.sagemath.org/question/53301/maximal-matching-of-a-poset/ Hi,
I would like to know how to find a maximal matching (defined below) of a given finite poset.
A matching M in a poset X is a subset M of X x X such that:
1) if (x, y) is in M, then x is an immediate predecessor of y (x<y and there is no element z such that x<z<y)
2) each element x of X belongs to at most one element in M.
A matching of a poset is the same as a matching of its Hasse Diagram. I thought about using the matching() function for graphs, however, it seems that the Hasse diagram of a poset is a Digraph for Sage and so the matching function does not work.
By maximal matching I mean one with the maximal number of elements.
Any help would be appreciated.
Fri, 04 Sep 2020 13:55:52 +0200https://ask.sagemath.org/question/53301/maximal-matching-of-a-poset/Answer by FrédéricC for <p>Hi,</p>
<p>I would like to know how to find a maximal matching (defined below) of a given finite poset. </p>
<pre><code> A matching M in a poset X is a subset M of X x X such that:
1) if (x, y) is in M, then x is an immediate predecessor of y (x<y and there is no element z such that x<z<y)
2) each element x of X belongs to at most one element in M.
</code></pre>
<p>A matching of a poset is the same as a matching of its Hasse Diagram. I thought about using the matching() function for graphs, however, it seems that the Hasse diagram of a poset is a Digraph for Sage and so the matching function does not work. </p>
<p>By maximal matching I mean one with the maximal number of elements. </p>
<p>Any help would be appreciated.</p>
https://ask.sagemath.org/question/53301/maximal-matching-of-a-poset/?answer=53305#post-id-53305Maybe use the undirected Hasse diagram ?
sage: P=posets.PentagonPoset()
sage: G=P.hasse_diagram().to_undirected()
sage: G.matching()
[(2, 3, None), (1, 4, None)]
Fri, 04 Sep 2020 18:15:04 +0200https://ask.sagemath.org/question/53301/maximal-matching-of-a-poset/?answer=53305#post-id-53305