imported>M2k~dewiki: BKL ersetzt mit bkl-replace

2026-01-29T10:04:19Z

Neue Seite

Der '''Heiratssatz''', oder auch '''Satz von Hall''', benannt nach [[Philip Hall]], ist ein mathematischer Satz aus der [[Kombinatorik]] bzw. aus der [[Endliche Menge|Theorie der endlichen Mengen]] aus dem Jahre 1935.<ref>P. Hall: ''On representation of subsets.'' ''Quart. J. Math. (Oxford)'' 10, 1935, S. 26–30.</ref> Er gilt als Ausgangspunkt der [[Matching (Graphentheorie)|Matching]]-Theorie in der [[Graphentheorie]].<ref name="Ziegler">Aigner-Ziegler: S. 134–136.</ref>

== Problemstellung ==
[[Datei:Halls theorem positive example.svg|mini|hochkant=1.5|<math>1\in A_1</math>, <math>2\in A_2</math>, <math>5\in A_3</math> und <math>7\in A_4</math> ist eine mögliche Auswahl.]]
[[Datei:Halls theorem negartive example.svg|mini|hochkant=1.5|Die Mengen <math>A_1,A_2,A_3</math> verletzen die Hall-Bedingungen, da deren Vereinigung nur 2 Elemente enthält.]]

Gegeben seien eine [[natürliche Zahl]] <math>n</math>, eine [[endliche Menge]] <math>X</math> und endlich viele [[Teilmenge]]n <math>A_1,\ldots,A_n</math> von <math>X</math>, die nicht notwendigerweise alle verschieden sein müssen. Dann ist die Frage:

''Gibt es ein „Vertretersystem“ ({{enS|system of distinct representatives}}), also Elemente <math>x_i\in A_i</math>   <math>(i=1, \ldots, n) </math> derart, dass die <math>x_1,\ldots, x_n</math> alle verschieden sind?''

Oder anders formuliert:

Gegeben seien eine endliche [[Indexmenge (Mathematik)|Indexmenge]] <math>I</math> und dazu eine [[Familie (Mathematik)|Familie]] <math>\mathcal A = (A_i)_{i \in I}</math> endlicher Mengen. Dann ist die Frage:

''Existiert für <math>\mathcal A</math> eine „[[Injektivität|injektive]] [[Auswahlfunktion]]“''
:<math>a \colon I \to \bigcup_{i \in I} A_i</math>,
so dass <math>a(i)\in A_i</math> für alle <math> i\in I </math> gilt?

=== Interpretation ===
Folgende Interpretation führte zum weitverbreiteten Begriff ''Heiratssatz'':<ref>Der Terminus „Heiratssatz“ ({{enS|marriage theorem}}) und die damit verbundene Interpretation werden in der Fachliteratur auf [[Hermann Weyl]] zurückgeführt; vgl. Jacobs-Jungnickel: S. 23, 393. Weyl nennt die in Rede stehende Fragestellung explizit das ''marriage problem''; vgl. {{Literatur |Autor=Weyl |Titel=Amer. J. Math. |Band=71 |Datum= |Seiten=202 ff.}}</ref>

Gegeben seien eine endliche Menge <math>I</math> heiratswilliger Frauen und dazu eine endliche Menge <math>X</math> von mit diesen Frauen befreundeten Männern. Für jede Frau <math>i \in I</math> sei <math>A_i\subseteq X</math> die Menge der mit <math>i</math> befreundeten Männer.

Dann ist die Frage:

''Lassen sich die Frauen mit den Männern so verheiraten, dass jede Frau einen der mit ihr befreundeten Männer heiratet, ohne dass die Monogamieregel verletzt wird?''<ref name="Ziegler" /> Eine Veranschaulichung des Heiratssatzes findet sich in dem Beitrag von [[Konrad Jacobs]] in den ''Selecta Mathematica I''.<ref>{{Literatur |Autor=Jacobs |Titel=Selecta Mathematica I |Datum= |Seiten=103 ff.}}</ref>

=== Notwendige Bedingung ===
Eine solche Heirat verlangt, dass jede Frau <math>i</math> einen Mann <math>x_i\in A_i</math> zur Heirat auswählt, ohne dass dabei zwei Frauen denselben Mann heiraten. Dies muss nicht nur für die Gesamtheit der Frauen gelten, sondern auch für jede beliebige Teilmenge. Es ist also offensichtlich notwendig, dass je <math>k</math> Frauen immer mit mindestens <math>k</math> Männern befreundet sind.<ref name="Heise">Halder-Heise: S. 145–149.</ref>

Dies bedeutet: Für jede Teilmenge <math>I_0 \subseteq I</math> muss es in der [[Vereinigungsmenge]] <math>\bigcup_{i\in I_0}A_i</math> immer mindestens <math>|I_0|</math> Elemente geben.<ref>Dabei bezeichnet <math>|I_0|</math> die Anzahl der Elemente von <math>I_0</math>.</ref>

Zur Existenz einer Auswahl der verlangten Art erhalten wir exakt die folgende notwendige Bedingung, die man auch die ''Hall-Bedingung'' oder ''hallsche Bedingung'' ({{enS|Hall’s condition}}) nennt:
: Für jede Teilmenge <math>I_0\subseteq I</math> ist <math>|\bigcup_{i\in I_0}A_i| \ge |I_0|</math>.

== Heiratssatz ==
Der Heiratssatz sagt nun aus, dass die Hall-Bedingung für die Existenz einer Auswahl nicht nur notwendig, sondern auch hinreichend ist:

Es seien <math>I</math> und <math>\mathcal A</math> wie oben beschrieben. Dann sind folgende Aussagen äquivalent:

* Es existiert für <math>\mathcal A</math> eine injektive Auswahlfunktion
:<math>a \colon I \to \bigcup_{i \in I} A_i, \quad i \mapsto x_i \in A_i</math>.
* Die Hall-Bedingung ist erfüllt.

== Beweise und verwandte Sätze ==
Ein direkter Beweis kann mittels Induktion über die Anzahl <math>|I|</math> der Mengen <math>A_i</math> geführt werden. Ein solcher Beweis findet sich in den ''Proofs from THE BOOK'' von [[Martin Aigner]] und [[Günter Ziegler]].<ref name="Ziegler" /> Der Satz lässt sich ebenfalls direkt auf den [[Satz von Dilworth#Herleitung des Heiratssatzes aus dem Satz von Dilworth|Satz von Dilworth]] zurückführen. Wie sich zeigt, lassen sich der Heiratssatz, der [[Satz von Dilworth]] und der [[Satz von König (Graphentheorie)|Satz von König]] leicht gegenseitig auseinander herleiten.<ref>Jungnickel, Konrad Jacobs: S. 27 ff.</ref>

== Graphentheoretische Darstellung ==
[[Datei:Halls theorem matching graph theory.svg|mini|hochkant=1|Die blauen Kanten bilden ein Matching, in dem alle Knoten aus A vorkommen.]]
Der Heiratssatz von Hall lässt sich wie folgt graphentheoretisch darstellen. Es sei <math>G=(V,E)</math> ein [[bipartiter Graph]] mit Bipartition <math>\{A,B\}</math>. Ein [[Matching (Graphentheorie)|Matching]] ist eine Menge von verschiedenen Kanten, die keine Knoten des Graphen gemeinsam haben. Für eine Teilmenge <math>S\subset A</math> sei <math>N(S)</math> die Menge aller zu <math>S</math> benachbarten Punkte, die wegen der Bipartitheit notwendigerweise eine Teilmenge von <math>B</math> sind. Die Frage nach einem Matching, in dem alle Knoten <math>a\in A</math> vorkommen, ist die Frage nach einer Auswahl von paarweise verschiedenen Knoten <math>b_a\in N(\{a\})</math> für alle <math>a\in A</math>. Der Heiratssatz lautet in diesem Kontext:<ref>Winfried Hochstättler: ''Algorithmische Mathematik'', Springer-Verlag (2010), ISBN 3-642-05421-8, Satz 4.36.</ref>

Für einen bipartiten Graphen mit Bipartition <math>\{A,B\}</math> sind folgende Aussagen äquivalent:
* Es gibt ein Matching, in dem jeder Knoten aus <math>A</math> vorkommt.
* Für alle Teilmengen <math>S\subseteq A</math> gilt <math>|N(S)|\ge |S|</math>.
* Es existiert eine injektive Funktion <math> f\subseteq E</math> mit Definitionsbereich <math>A</math> (welche eine mögliche injektive Auswahlfunktion wie in Kapitel [[#Problemstellung|Problemstellung]] beschrieben ist).

Ob ein derartiges Matching existiert, lässt sich mithilfe des Modells des [[Flüsse und Schnitte in Netzwerken|Netzflusses]] beantworten.<br />

== Verallgemeinerungen ==
In der Literatur zum Heiratssatz findet sich eine große Anzahl von Verallgemeinerungen und Erweiterungen unter verschiedenen Maßgaben:

=== Verallgemeinerung nach Philip A. Ostrand ===
Diese Verallgemeinerung (''Satz von Ostrand'') verschärft den Heiratssatz in der Weise, dass hier eine [[untere Schranke]] zur [[Abschätzung]] der Anzahl der Vertretersysteme angegeben wird, mit der sich der Heiratssatz unmittelbar ergibt:<ref>{{Literatur |Autor=Ostrand |Titel=J. Math. Anal. Appl. |Band=32 |Datum= |Seiten=1–4}}</ref><ref name="Heise" /><ref>Die Notwendigkeit des Erfülltseins der ''hallschen Bedingung'' wird hierbei als evident angesehen.</ref>

Gegeben seien eine natürliche Zahl <math>n</math> und dazu eine endliche Familie <math>\mathcal A = (A_1, \ldots, A_n)</math> endlicher Mengen. Diese sei in folgendem Sinne ''aufsteigend angeordnet'':
: <math>|A_1| \leq |A_2| \leq \ldots \leq |A_n|</math>

Die Anzahl der Vertretersysteme von <math>\mathcal A</math> werde mit <math>v_{\mathcal A}</math> bezeichnet.<ref>Dies ist also die Anzahl der injektiven Auswahlfunktionen <math>a \colon \{ 1 , \ldots , n \} \to A_1 \cup \ldots \cup A_n</math> für <math>\mathcal A = (A_1, \ldots, A_n)</math>. Hier gilt im Allgemeinen, wenn nichts weiter vorausgesetzt wird, <math>v_{\mathcal A} = 0</math>.</ref>

Dann gilt:

: Erfüllt <math>\mathcal A</math> die ''Hall-Bedingung'', so ist
: <math>v_{\mathcal A} \geq \prod_{i=1}^n {\operatorname{max}\left(1,\ \left|A_i\right| - i +1\right)} </math>.

Die Verbindung zum Heiratssatz ergibt sich aus der Beobachtung, dass für <math>i=1, \ldots , n</math> durchweg <math>{\operatorname{max}(1,|A_i| - i +1)} > 0</math> gilt. Der Satz von Ostrand sagt also insbesondere aus, dass bei Gültigkeit der Hall-Bedingung die Anzahl der Vertretersysteme mindestens <math>1</math> sein muss, dass also in diesem Falle ein Vertretersystem existiert.

Wie der niederländische Mathematiker [[Jacobus Hendricus van Lint]] zeigen konnte, ist die oben genannte Schranke, wenn allein die Anzahlen <math>|A_i|</math> bekannt sind, die bestmögliche.<ref>Halder-Heise: S. 149.</ref>

=== Verallgemeinerung nach Rado ===
{{Hauptartikel|Satz von Rado}}
Diese Verallgemeinerung, welche auf [[Richard Rado]] zurückgeht, bringt den Heiratssatz in Verbindung mit der [[Matroid]]theorie. Ausgangspunkt ist hier die folgende Frage:

''Unter welchen Bedingungen existiert zu einem gegebenen [[Matroid]] <math>\mathcal M = (X;\mathcal U) </math> und zu einer gegebenen endlichen Familie <math>\mathcal A = (A_i)_{i \in I}</math> von <math>X</math>-Teilmengen ein „Vertretersystem“ <math>(a_i)_{i \in I}</math> derart, dass die Teilmenge <math>A= \{a_i : i \in I \}</math> „unabhängig“ ist?''<ref><math>X</math> ist die gegebene endliche [[Grundmenge]], in der alle <math>A_i</math> enthalten sind und <math> \mathcal U </math> ist das zugehörige [[Unabhängigkeitssystem|System der unabhängigen Teilmengen]].</ref><ref>Stellt man den Zusammenhang mit der oben beschriebenen injektiven Auswahlfunktion <math>a \colon I \to \bigcup_{i \in I} A_i</math> her, so ist <math>(a_i)_{i \in I}= (a(i))_{i \in I}</math>, wobei die Teilmenge <math>A</math> genau die <math>a</math>-[[Bildmenge]] von <math>I</math> ist, zu der sie auf diesem Wege in [[umkehrbar eindeutig]]er Beziehung steht.</ref>

Eine solche Teilmenge <math>A</math> nennt man auch eine „unabhängige Transversale“.

Kurz und knapp formuliert ist die in Rede stehende Frage also so zu stellen:

''Unter welchen Bedingungen hat ein gegebenes Matroid <math>\mathcal M</math> zu einer gegebenen endlichen Teilmengenfamilie <math>\mathcal A</math> eine unabhängige Transversale?''

Die Antwort auf diese Frage gibt der ''Satz von Rado'', welcher folgendes besagt:<ref>{{Literatur |Autor=Rado |Titel=Quart. J. Math. (Oxford) |Band=13 |Datum= |Seiten=83 ff.}}</ref><ref>Aigner: S. 246 ff.</ref><ref>Mirsky: S. 93 ff.</ref><ref>Welsh: S. 97 ff.</ref>

<math>\mathcal M </math> hat zu <math>\mathcal A</math> eine unabhängige Transversale dann und nur dann, wenn für jede Teilfamilie <math>{\mathcal {A}}_{H} = (A_i)_{i \in H}</math>   <math>(H\subseteq I)</math> die [[Ungleichung]] <math>\rho (\bigcup_{i\in H}A_i) \ge |H|</math> erfüllt ist.<ref><math>\rho \colon \mathcal P(X) \to \N_0 </math> ist die zu <math>\mathcal M </math> gehörige [[Matroid#Axiome der Rangfunktion|Rangfunktion]].</ref>

Die letzte Bedingung nennt man kurz ''Rados Bedingung'' ({{enS|Rado’s condition}}) oder auch ''Hall-Rado-Bedingung'' ({{enS|Hall-Rado condition}}) oder ähnlich. Sie bedeutet, dass für jedes <math>H \subseteq I</math> die zugehörige Vereinigungsmenge eine unabhängige Teilmenge mit mindestens <math>|H|</math> [[Element (Mathematik)|Elementen]] umfasst. Von ihr aus gelangt man zur ''Hall-Bedingung'', indem man als Rangfunktion die [[Anzahl]]funktion <math>|\cdot| \colon \mathcal P(X) \to \N_0 </math> nimmt, welche jeder Teilmenge <math>T \subseteq X</math> die Anzahl ihrer Elemente <math>|T|</math> zuordnet. In dem zur Anzahlfunktion gehörigen Matroid sind alle Teilmengen von <math>X</math> unabhängig. So erweist sich der Heiratssatz als Spezialfall des ''Satzes von Rado''.

=== Erweiterung auf den unendlichen Fall ===
Zum Heiratssatz und zum Satz von Rado (und ebenso zum [[Satz von Dilworth]]) gibt es erweiterte Versionen, welche (u. a.) den Fall einbeziehen, dass die Grundmenge [[Unendliche Menge|unendlich]] ist. Die Beweise dieser ''transfiniten Versionen'' setzen allerdings üblicherweise als entscheidendes Hilfsmittel das [[Lemma von Zorn]] bzw. den [[Satz von Tychonoff]] ein, gehen also vom [[Auswahlaxiom]] aus.<ref>Welsh: S. 389 ff.</ref><ref>Siehe hierzu auch [[Rados Auswahlprinzip]].</ref>

Die Erweiterung auf den unendlichen Fall wurde von [[Ron Aharoni]], [[Crispin Nash-Williams]] und [[Saharon Shelah]] bewiesen.<ref>R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah,. Marriage in infinite societies, in: Progress in Graph Theory (Waterloo, Ontario, 1982), Academic Press, Toronto, 1984, S. 71–79</ref><ref>R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah, A general criterion for the existence of transversals, Proceedings of the London Mathematical Society, Band 3, 1983, S. 43–68.</ref><ref>R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah, Another Form of a Criterion for the Existence of Transversals, Journal of the London Mathematical Society, Band 2, 1984, S. 193–203</ref>

== Weblinks ==

{{Wikiversity|Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 20|Ein Beweis des Heiratssatzes im Rahmen eines Kurses zur diskreten Mathematik}}

== Literatur ==
* {{Literatur
|Autor=Martin Aigner, Günter M. Ziegler
|Titel=Proofs from THE BOOK
|Verlag=Springer Verlag
|Ort=Berlin (u. a.)
|Datum=1991
|ISBN=3-540-63698-6}}
* {{Literatur
|Autor=Martin Aigner
|Titel=Kombinatorik II: Matroide und Transversaltheorie
|Reihe=Hochschultext
|Verlag=Springer Verlag
|Ort=Berlin (u. a.)
|Datum=1976
|ISBN=3-540-07949-1
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Aigner%2C%20Martin&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=80&mx-pid=460127 MR0460127]}}
* {{Literatur
|Autor=Heinz-Richard Halder, [[Werner Heise (Mathematiker)|Werner Heise]]
|Titel=Einführung in die Kombinatorik
|Reihe=Mathematische Grundlagen für Mathematiker, Physiker und Ingenieure
|Verlag=Hanser Verlag
|Ort=München, Wien
|Datum=1976
|ISBN=3-446-12140-4
|Online=[https://mathscinet.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&r=1&review_format=html&s4=Halder&s5=Kombinatorik&s6=&s7=&s8=All&sort=Newest&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq MR0498160]}}
* {{Literatur
|Hrsg=Konrad Jacobs
|Titel=Selecta Mathematica I
|Reihe=Heidelberger Taschenbücher
|BandReihe=49
|Verlag=Springer-Verlag
|Ort=Berlin / Heidelberg / New York
|Datum=1969
|Seiten=103–141}}
* {{Literatur
|Autor=Konrad Jacobs, Dieter Jungnickel
|Titel=Einführung in die Kombinatorik
|Reihe=de Gruyter Lehrbuch
|Auflage=2., völlig neu bearbeitete und erweiterte
|Verlag=de Gruyter
|Ort=Berlin (u. a.)
|Datum=2004
|ISBN=3-11-016727-1}}
* {{Literatur
|Autor=[[Dieter Jungnickel]]
|Titel=Transversaltheorie
|Reihe=Mathematik und ihre Anwendungen in Physik und Technik
|BandReihe=39
|Verlag=Akademische Verlagsgesellschaft Geest & Portig K.-G.
|Ort=Leipzig
|Datum=1982
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Jungnickel%2C%20Dieter&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=163&mx-pid=706076 MR0706076]}}
* {{Literatur
|Autor=[[László Lovász|L. Lovász]], M. D. Plummer
|Titel=Matching Theory
|Reihe=North-Holland Mathematics Studies
|BandReihe=121
|Auflage=
|Verlag=North-Holland
|Ort=Amsterdam (u. a.)
|Datum=1986
|ISBN=0-444-87916-1
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Lovasz&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=165&mx-pid=859549 MR0859549]}}
* {{Literatur
|Autor=[[Heinz Lüneburg]]
|Titel=Kombinatorik
|Reihe=Elemente der Mathematik vom höheren Standpunkt aus
|BandReihe=6
|Verlag=Birkhäuser Verlag
|Ort=Basel / Stuttgart
|Datum=1971
|ISBN=3-7643-0548-7
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=L%C3%BCneburg%2C%20Heinz&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=47&mx-pid=335267 MR0335267]}}
* {{Literatur
|Autor=[[Leonid Mirsky]]
|Titel=Transversal Theory
|Reihe=North-Holland Mathematics Studies
|BandReihe=121
|Verlag=Academic Press
|Ort=New York / London
|Datum=1971
|ISBN=0-12-498550-5
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Mirsky&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=20&mx-pid=282853 MR0282853]}}
* {{Literatur
|Autor=[[Leonid Mirsky|L. Mirsky]], Hazel Perfect
|Titel=Systems of representatives
|Sammelwerk=[[Journal of Mathematical Analysis and Applications|J. Math. Anal. Appl]]
|Band=15
|Datum=1966
|Seiten=520–568
|Online=[http://www.sciencedirect.com/science/article/pii/0022247X66901065 sciencedirect.com]; [http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=JOUR&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Mirsky&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=31&mx-pid=204300 MR0204300]}}
* {{Literatur
|Autor=Philip. A. Ostrand
|Titel=Systems of distinct representatives, II
|Sammelwerk= [[Journal of Mathematical Analysis and Applications|J. Math. Anal. Appl.]]
|Band=32
|Datum=1970
|Seiten=1–4
|Online=[http://ac.els-cdn.com/0022247X70903148/1-s2.0-0022247X70903148-main.pdf?_tid=25eedf08-5230-11e4-a3d5-00000aab0f27&acdnat=1413132927_6b497644d28dcf0fa263058ea4d2bc38 ac.els-cdn.com]
|Format=PDF
|KBytes=}} [http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Ostrand&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=17&mx-pid=280385 MR0280385].
* {{Literatur
|Autor=[[Richard Rado|R. Rado]]
|Titel=A theorem on independence relations
|Sammelwerk=[[Quarterly Journal of Mathematics|Quart. J. Math. (Oxford)]]
|Band=13
|Datum=1942
|Seiten=83–89
|Kommentar=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Rado%2C%20R.&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=70&mx-pid=8250 MR0008250]
|Online=[http://qjmath.oxfordjournals.org/content/os-13/1/83.full.pdf+html qjmath.oxfordjournals.org]
|Format=PDF
|KBytes=}}
* {{Literatur
|Autor=Philip F. Reichmeider
|Titel=The Equivalence of Some Combinatorial Matching Theorems
|Verlag=Polygonal Publishing House
|Ort=Washington NJ
|Datum=1984
|ISBN=0-936428-09-0
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Reichmeider&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=1&mx-pid=781348 MR0781348]}}
* {{Literatur
|Autor=[[Dominic Welsh|D. J. A. Welsh]]
|Titel=Matroid Theory
|Reihe=L.M.S. Monographs
|BandReihe=8
|Verlag=Academic Press
|Ort=London (u. a.)
|Datum=1976
|ISBN=0-12-744050-X
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Welsh%2C%20D.%20J.%20A.&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=45&mx-pid=427112 MR0427112]}}
* {{Literatur
|Autor=[[Hermann Weyl]]
|Titel=Almost periodic invariant vector sets in a metric vector space
|Sammelwerk=[[Johns Hopkins University Press|Amer. J. Math]]
|Band=71
|Datum=1949
|Seiten=178–205
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Weyl%2C%20Hermann&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=57&mx-pid=28530 MR0028530]
|JSTOR=2372104}}

== Einzelnachweise und Anmerkungen ==
<references />

[[Kategorie:Diskrete Mathematik]]
[[Kategorie:Satz (Graphentheorie)]]
[[Kategorie:Kombinatorik]]
[[Kategorie:Satz (Mathematik)|Hall, Satz von]]

Heiratssatz - Versionsgeschichte

imported>M2k~dewiki: BKL ersetzt mit bkl-replace