patternMinor
Term for a matching which is perfect on one side only
Viewed 0 times
sideperfecttermoneforwhichonlymatching
Problem
What is a standard term for a matching in a bipartite graph, in which one part has less vertices than the other part, and the part with less vertices is fully matched (but the other part is, obviously, not fully matched)?
It is not exactly perfect, but it is "one-sided perfect", or "as perfect as it could be". What is a short term to use for this kind of matching?
It is not exactly perfect, but it is "one-sided perfect", or "as perfect as it could be". What is a short term to use for this kind of matching?
Solution
Such a matching is said to saturate one of the sides. More specifically, if $M$ is a matching of a graph $G$ and $v$ is incident to one of the edges of $M$, we say that $M$ saturates $v$. If $A$ is a set of vertices, then we say that $M$ saturates $A$ if every vertex in $A$ is saturated by $M$.
Specifically for your case, the matching saturates the smaller of the two sides of the bipartition.
Specifically for your case, the matching saturates the smaller of the two sides of the bipartition.
Context
StackExchange Computer Science Q#37837, answer score: 5
Revisions (0)
No revisions yet.