Difference between matching and perfect matching
Consider a set M = {m1, m2, ..., mn} of n men, and a set W = {w1, w2, ..., wn} of n women. Let MXW denote the set of all possible ordered pairs of the form (m, w), where m belongs to M and w belongs to W.
A matching S is a set of ordered pairs, each from MXW, with the property that each member of M and each member of W appears in at most one pair in S.
A perfect matching S1 is a matching with the property that each member of M and each member of W appears in exactly one pair in S1.
I am having tough time to understand above statment on definitions of matching and perfect matching.
Can any one give me an example on matching and perfect matching on following example. M = {m1,m2, m3} and w = {w1, w2, w3}
Thanks for help
A better example would be to use M={m1,m2,m3,m4} and W={w1,w2,w3} . There is no perfect match possible because at least one member of M cannot be matched to a member of W, but there is a matching possible. An example of a matching is [{m1,w1},{m2,w2},{m3,w3}] (m4 is unmatched)
In the example you gave a possible matching can be a perfect matching because every member of M can be matched uniquely to a member of W.
Here's a matching: ∅. No member of M, nor any member of W, appears in more than one pair in ∅, trivially, so the definition is satisfied.
∅ is not a perfect mathing, though, since no members of W or M appear in its pairs (since there are no pairs in it).
A matching:
{(m1,w1), (m2,w2)}
A perfect matching:
{(m1,w1), (m2,w2), (m3,w3)}
上一篇: 高效地找到匹配的对象对
下一篇: 匹配与完美匹配的区别