Lexikon der Mathematik: Hall, Satz von
charakterisiert diejenigen bipartiten Graphen, die eine vollständige Korrespondenz besitzen. Dabei heißt eine Korrespondenz M in einem bipartiten Graphen G mit den Partitionsmengen X und Y vollständig, wenn
Es sei G ein bipartiter Graph mit den Partitions-mengen X und Y so, daß |X| ≤ |Y| gilt.
Der Graph G besitzt genau dann eine vollständige Korrespondenz, wenn für alle S ⊆ X die Bedingung
Da dieser Satz implizit in einem Resultat von König (1931) enthalten ist, wird er von manchen Autoren auch „Satz von König-Hall“ genannt.
Wegen der folgenden amüsanten Interpretation ist er außerdem unter dem Namen Heiratssatz bekannt: Ist X eine Menge von Damen, Y eine Menge von Herren und xy ∈ K(G), wenn x ∈ X und y ∈ Y einer Heirat nicht abgeneigt sind, so gibt der Satz eine exakte Bedingung dafür an, wann alle Damen einen geeigneten Heiratspartner finden, ohne Bigamie zu betreiben. Übrigens geht der Spezialfall |X| = |Y| dieses Satzes sogar schon auf Frobenius (1917) zurück.
Eine leichte Folgerung aus dem Heiratssatz ist der sogenannte Haremssatz.
Es sei G ein bipartiter Graph mit den Partitionsmengen X = {x1, x2, …, xn} und Y, und jeder Ecke xi sei eine natürliche Zahl pi zugeordnet.
Es gibt genau dann eine Kantenmenge K ⊆ K(G) mit der Eigenschaft, daß jede Ecke xi mit genau pi Kanten und jede Ecke y ∈ Y mit höchstens einer Kante von K inzidiert, wenn für alle
Die Interpretation dieses Satzes sei diesmal dem Leser überlassen.
Auch das nächste sehr attraktive Ergebnis von König aus dem Jahre 1916 läßt sich leicht mit Hilfe des Satzes von Hall beweisen.
Die Kantenmenge eines p-regulären bipartiten Graphen läßt sich in p kantendisjunkte perfekte Matchings zerlegen.
Kreise ungerader Länge zeigen, daß dieses Ergebnis für nicht bipartite Graphen seine Gültigkeit verliert.
Alle hier angegebenen Sätze gelten auch für bipartite Multigraphen
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.