Satz von Kruskal

Der Satz von Kruskal ist ein Lehrsatz der Graphentheorie, eines der Teilgebiete der Mathematik. Er wurde von dem Mathematiker Joseph Bernard Kruskal im Jahre 1960 publiziert. Der Satz behandelt eine wichtige Eigenschaft der Klasse der endlichen Bäume.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:[1][2][3][4][5]

Die Klasse der endlichen Bäume ist durch die Quasiordnungsrelation der Bildung topologischer Minoren wohlquasigeordnet.
Mit anderen Worten: Jede abzählbare Menge endlicher Bäume bildet zusammen mit der topologischen Minorenrelation eine wohlfundierte quasigeordnete Menge, in der jede Antikette endlich ist.

Verwandte Sätze

Der Satz von Kruskal wurde in den 1960er Jahren von Crispin St. J. A. Nash-Williams auf unendliche Bäume verallgemeinert.[6][3] Einen vereinfachten Beweis beider Sätze legte Daniela Kühn im Jahre 2001 vor.[3] Der kruskalsche Satz ist eingebunden in den Problemkreis um das bedeutende Minorentheorem.

Literatur

Originalarbeiten

  • J. B. Kruskal: Well-quasi-ordering, the Tree Theorem, and Vazsonyi’s conjecture. In: Transactions of the American Mathematical Society. Band 95, 1960, S. 210–225 (ams.org).  MR0111704
  • Daniela Kühn: On well-quasi-ordering infinite trees—Nash-Williams’s theorem revisited. In: Mathematical Proceedings of the Cambridge Philosophical Society. Band 130, 2001, S. 401–408 (MR1816801). 
  • C. St. J. A. Nash–Williams: On well-quasi-ordering infinite trees. In: Mathematical Proceedings of the Cambridge Philosophical Society. Band 61, 1965, S. 697–720 (MR0175814). 
  • C. St. J. A. Nash–Williams: On better-quasi-ordering transfinite sequences. In: Mathematical Proceedings of the Cambridge Philosophical Society. Band 64, 1968, S. 273–290 (MR0221949). 

Monografien

  • Reinhard Diestel: Graphentheorie. 2. Auflage. Springer Verlag, Berlin / Heidelberg / New York (und weitere) 2000, ISBN 3-540-67656-2. 
  • Reinhard Diestel: Graph Theory (= Graduate Texts in Mathematics. Band 173). 3. Auflage. Springer Verlag, Berlin / Heidelberg / New York 2005, ISBN 3-540-26182-6 (MR2159259). 
  • Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York 2005, ISBN 0-387-24219-8 (MR2127991). 
  • Rudolf Halin: Graphentheorie I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 (MR0586234). 
  • Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4 (MR0282850). 

Einzelnachweise und Fußnoten

  1. ↑ Reinhard Diestel: Graphentheorie. 2000, S. 251 ff., 253–255
  2. ↑ Reinhard Diestel: Graph Theory. 2005, S. 316 ff., 317
  3. ↑ a b c Egbert Harzheim: Ordered Sets. 2005, S. 231 ff., 245–246
  4. ↑ Klaus Wagner: Graphentheorie. 1970, S. 172 ff., 178
  5. ↑ Rudolf Halin: Graphentheorie I. 1980, S. 116 ff.
  6. ↑ Diestel, op. cit., S. 354