Satz von Kruskal

mathematischer Satz

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

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

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

Bearbeiten

Originalarbeiten

Bearbeiten

Monografien

Bearbeiten

Einzelnachweise und Fußnoten

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