Bipartiter Graph/Zerlegung/Numerische Paarungsbedingung/Fakt

Satz über Paarungen in bipartiten Graphen

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

${}G$ enthält eine Paarung für ${}A$ .

Die Paarungszahl von ${}G$ ist gleich ${}{\#\left(A\right)}$ .

Es gilt die Paarungsbedingung für ${}A$ , d.h. zu jeder Teilmenge ${}S\subseteq A$ ist ${}{\#\left(S\right)}\leq {\#\left(N(S)\right)}$ .

Es gibt eine injektive Abbildung
$\varphi \colon A\longrightarrow B$

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

Zum Beweis, Alternativen Beweis erstellen

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.