Bipartiter Graph/Zerlegung/Numerische Paarungsbedingung/Fakt

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Satz über Paarungen in bipartiten Graphen

Es sei ein bipartiter Graph mit einer bipartiten Zerlegung . Dann sind die folgenden Eigenschaften äquivalent.

  1. enthält eine Paarung für .
  2. Die Paarungszahl von ist gleich .
  3. Es gilt die Paarungsbedingung für , d.h. zu jeder Teilmenge ist .
  4. Es gibt eine injektive Abbildung

    mit für alle .