Ungerichteter Graph/Bipartit/Paarungen/Einführung/Textabschnitt

Definition

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.

Statt Paarungsbedingung sagt man auch Heiratsbedingung. Man beachte, dass die Paarungsbedingung eine Ansammlung von rein numerischen Bedingungen ist. Besonders wichtig ist der Fall ${}C=A$.

Satz

Es sei ${}G=(V,E)$ ein bipartiter Graph mit einer bipartiten Zerlegung ${}V=A\uplus B$. Dann sind die folgenden Eigenschaften äquivalent.

1. ${}G$ enthält eine Paarung für ${}A$.
2. Die Paarungszahl von ${}G$ ist gleich ${}{\#\left(A\right)}$.
3. Es gilt die Paarungsbedingung für ${}A$, d.h. zu jeder Teilmenge ${}S\subseteq A$ ist ${}{\#\left(S\right)}\leq {\#\left(N(S)\right)}$.
4. Es gibt eine injektive Abbildung

   $\varphi \colon A\longrightarrow B$

   mit ${}(a,\varphi (a))\in E$ für alle ${}a\in A$.

Beweis

Von (1) nach (2). Da es eine Paarung für ${}A$ gibt, ist die Paarungszahl zumindest ${}{\#\left(A\right)}$. Größer kann die Paarungszahl aber auch nicht sein, da ja jede Paarung Bezug auf die beiden Teile ${}A$ und ${}B$ nimmt. Von (2) nach (1) ist klar. Da man aus einer Paarung für ${}A$ eine injektive Abbildung von ${}A$ nach ${}B$ mit der beschriebenen Kantenbedingung und aus einer solchen Abbildung umgekehrt direkt eine Paarung machen kann, sind (1) und (4) äquivalent. Von (3) nach (4) folgt direkt aus Fakt, wenn man ${}N(S)=\bigcup _{s\in S}N(s)$ berücksichtigt. Von (4) nach (3) ist trivial.

$\Box$