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

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Es sei ein bipartiter Graph mit einer Bipartition und sei . Man sagt, dass die Paarungsbedingung erfüllt, wenn für jede Teilmenge die Beziehung gilt.

Statt Paarungsbedingung sagt man auch Heiratsbedingung. Man beachte, dass die Paarungsbedingung eine Ansammlung von rein numerischen Bedingungen ist. Besonders wichtig ist der Fall .



Satz  

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 .

Beweis  

Von (1) nach (2). Da es eine Paarung für gibt, ist die Paarungszahl zumindest . Größer kann die Paarungszahl aber auch nicht sein, da ja jede Paarung Bezug auf die beiden Teile und nimmt. Von (2) nach (1) ist klar. Da man aus einer Paarung für eine injektive Abbildung von nach 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 berücksichtigt. Von (4) nach (3) ist trivial.