World's most popular travel blog for travel bloggers.

[Solved]: Term for a matching which is perfect on one side only

, , No Comments
Problem Detail: 

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?

Asked By : Erel Segal-Halevi

Answered By : Pål GD

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37837

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback