HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Term for a matching which is perfect on one side only

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#37837, answer score: 5

Revisions (0)

No revisions yet.