Satz von Kruskal

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

[Bearbeiten | Quelltext bearbeiten]

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

[Bearbeiten | Quelltext bearbeiten]

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.

Originalarbeiten

[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext bearbeiten]
  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