Bipartiter Graph/Teilmenge/Paarungsbedingung/Definition

Paarungsbedingung

Es sei ${}G$ ein bipartiter Graph mit einer Bipartition ${}V=A\uplus B$ und sei ${}C\subseteq A$. Man sagt, dass ${}C$ die Paarungsbedingung erfüllt, wenn für jede Teilmenge ${}S\subseteq C$ die Beziehung ${}{\#\left(S\right)}\leq {\#\left(N(S)\right)}$ gilt.