Direkt zum Inhalt

Lexikon der Mathematik: Kruskal, Satz von

sagt aus, daß es für jede unendliche Folge T1, T2, … von Bäumen Indizes i < j so gibt, daß Tj eine Unterteilung des Ti als Teilgraphen enthält.

Definiert man eine Relation „≤“ auf der Menge aller Bäume dadurch, daß TT′ genau dann gilt, wenn T′ eine Unterteilung von T als Teilgraphen enthält, dann sagt der Satz von Kruskal aus, daß durch ≤ eine Wohl-Quasi-Ordnung auf der Menge aller Bäume gegeben wird.

J.A. Kruskal bewies dieses Ergebnis 1960, und K. Wagner stellte die Vermutung auf, daß eine analoge Aussage für die Menge aller Graphen und die Minorenrelation gilt (Wagner, Vermutung von).

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos