Heiratssatz

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Heiratssatz, oder auch Satz von Hall, benannt nach Philip Hall, ist ein mathematischer Satz aus der Kombinatorik bzw. aus der Theorie der endlichen Mengen aus dem Jahre 1935.[1] Er gilt als Ausgangspunkt der Matching-Theorie in der Graphentheorie.[2]

Problemstellung[Bearbeiten]

1\in A_1, 2\in A_2, 5\in A_3 und 7\in A_4 ist eine mögliche Auswahl.
Die Mengen A_1,A_2,A_3 verletzen die Hall-Bedingungen, da deren Vereinigung nur 2 Elemente enthält.

Gegeben seien eine endliche Menge X und eine endliche Anzahl A_1,\ldots,A_n von Teilmengen aus X, die nicht notwendigerweise alle verschieden sein müssen. Kann man Elemente x_i\in A_i derart auswählen, dass die x_1,\ldots, x_n alle verschieden sind?

Folgende folkloristische Interpretation führte zum weit-verbreiteten Begriff Heiratssatz. Gegeben seien eine Menge \{1,\ldots, n\} heiratswilliger Frauen und eine Menge X von dazu in Frage kommenden Männern. Für jede Frau i sei A_i\subset X die Menge der von i bevorzugten Männer. Kann man nun eine Massenhochzeit so einrichten, dass alle Frauen einen bevorzugten Mann heiraten? Für jede Frau i ist dazu ein Mann x_i\in A_i zu wählen und bei vorherrschender Monogamie können keine zwei Frauen denselben Mann heiraten, das heißt die ausgewählten Männer x_1,\ldots,x_n müssen paarweise verschieden sein.

Wenn es eine Auswahl x_i\in A_i von der verlangten Art gibt, so muss es für jede Teilmenge I\subset \{1,\ldots, n\} zu jedem Index i\in I ein geeignetes x_i\in A_i geben, so dass die x_i, i\in I paarweise verschieden sind, insbesondere muss es also in \bigcup_{i\in I}A_i wenigstens |I| viele Elemente geben, wobei |I| die Anzahl der Elemente in I bezeichnet. Zur Existenz einer Auswahl der verlangten Art erhalten wir also folgende notwendige Bedingungen, die man auch die Hall-Bedingungen nennt:

Für jede Teilmenge I\subset \{1,\ldots, n\} ist |\bigcup_{i\in I}A_i| \ge |I|.

Heiratssatz[Bearbeiten]

Der Heiratssatz sagt aus, dass die Hall-Bedingungen für die Existenz einer Auswahl auch hinreichend sind:

Es seien X eine endliche Menge und A_1,\ldots, A_n Teilmengen von X. Dann sind folgende Aussagen äquivalent:

  • Es gibt x_i\in A_i derart, dass die x_1,\ldots, x_n paarweise verschieden sind.
  • Die Hall-Bedingungen sind erfüllt.

Ein Beweis kann mittels Induktion über die Anzahl n der Mengen A_i geführt werden. Ein kurzer Beweis findet sich in [3].

Graphentheorie[Bearbeiten]

Die blauen Kanten bilden ein Matching, in dem alle Knoten aus A vorkommen.

Der Heiratssatz von Hall lässt sich wie folgt graphentheoretisch deuten. Es sei G ein bipartiter Graph mit Bipartition \{A,B\}. Ein Matching ist eine Menge von verschiedenen Kanten, die keine Knoten des Graphen gemeinsam haben. Für eine Teilmenge S\subset A sei N(S) die Menge aller zu S benachbarten Punkte, die wegen der Bipartitheit notwendigerweise eine Teilmenge von B sind. Die Frage nach einem Matching, in dem alle Knoten a\in A vorkommen, ist die Frage nach einer Auswahl von paarweise verschiedenen Knoten b_a\in N(\{a\}) für alle a\in A. Der Heiratssatz lautet in diesem Kontext[4]:

Für einen bipartiten Graphen mit Bipartition \{A,B\} sind folgende Aussagen äquivalent:

  • Es gibt ein Matching, in dem jeder Knoten aus A vorkommt.
  • Für alle Teilmengen S\subset A gilt |N(S)|\ge |S|.

Siehe auch[Bearbeiten]

Der Heiratssatz ist eng verwandt mit

das heißt diese drei Sätze lassen sich leicht gegenseitig auseinander herleiten.[5]

Eine schöne Veranschaulichung des Heiratssatzes findet sich bei Konrad Jacobs.[6]

Erweiterung auf den unendlichen Fall[Bearbeiten]

Zum Heiratssatz (und ebenso zum Satz von Dilworth) gibt es eine erweiterte Version, welche den Fall einbezieht, dass die Grundmenge unendlich ist. Der Beweis dieser transfiniten Version setzt allerdings üblicherweise als entscheidendes Hilfsmittel das Lemma von Zorn ein, geht also vom Auswahlaxiom aus [7].

Einzelnachweise[Bearbeiten]

  1. P. Hall: On representation of subsets, Quart. J. Math. (Oxford) 10 (1935), Seiten 26-30
  2. M. Aigner, G. M. Ziegler: Proofs from THE BOOK, Springer-Verlag (1991), ISBN 3-540-63698-6, Kapitel 21, Seite 134
  3. M. Aigner, G. M. Ziegler: Proofs from THE BOOK, Springer-Verlag (1991), ISBN 3-540-63698-6, Kapitel 21, Seite 135
  4. Winfried Hochstättler: Algorithmische Mathematik, Springer-Verlag (2010), ISBN 3-642-05421-8, Satz 4.36
  5. Dieter Jungnickel, Konrad Jacobs:Einführung in die Kombinatorik, Walter de Gruyter (2003), ISBN 3-11-016727-1, Kapitel II, 2.2
  6. Konrad Jacobs: "Selecta Mathematica I", Heidelberger Taschenbücher, Springer-Verlag (1969), S. 104 ff.
  7. Siehe hierzu Rado's Auswahlprinzip.