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ß T ≤ T′ 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).
Schreiben Sie uns!