Kruskal's tree theorem (original) (raw)

dbo:abstract

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. (de)
En matemáticas, el árbol teorema de Kruskal indica que el conjunto de finitos más de un conjunto bien cuasi-ordenada de las etiquetas es en sí misma bien cuasi-ordenado (bajo incrustación homeomorfo). El teorema fue conjeturado por Andrew Vázsonyi y demostró por Joseph Kruskal (1960); una breve prueba fue dada por Nash-Williams (1963). es un caso especial de este teorema, de las cuales hay muchas generalizaciones que implican árboles con una incrustación plana, árboles infinitos, y así sucesivamente. Una generalización de los árboles a los gráficos arbitrarias está dado por el . (es)
In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding. (en)
En mathématiques, le théorème des arbres de Kruskal est un résultat de théorie des graphes conjecturé en 1937 par Andrew Vázsonyi et démontré indépendamment en 1960 par Joseph Kruskal et S. Tarkowski, affirmant que l'ensemble des arbres étiquetés par un ensemble muni d'un bel ordre est lui-même muni d'un bel ordre. Ce théorème est un cas particulier du théorème de Robertson-Seymour, dont il a constitué une des motivations. En utilisant ce théorème, Harvey Friedman a pu définir des entiers « incompréhensiblement grands », qu'il a utilisé pour obtenir des résultats nouveaux d'indécidabilité. (fr)
W matematyce Teoria Drzew Kruskala jest jednym z problemów w teorii grafów i . Mówi ona, iż skończony zbiór drzew z uporządkowanymi zasadami tworzenia jest homeomorficzny. Twierdzenie to zostało zaprezentowane przez – węgierskiego matematyka, a udowodnione przez Josepha Kruskala (1960) oraz (1963). Od tego czasu stał się znaczącym przykładem w jako stwierdzenie, którego nie można udowodnić używając ATR0 (forma arytmetycznej rekurencji transfinitowej), a finalne zastosowanie tego twierdzenia umożliwia konstrukcję bardzo szybko rosnącej funkcji TREE(n) (ang. tree – drzewo). (pl)

dbo:wikiPageExternalLink

dbo:wikiPageID

3606300 (xsd:integer)

dbo:wikiPageLength

13158 (xsd:nonNegativeInteger)

dbo:wikiPageRevisionID

1124400522 (xsd:integer)

dbo:wikiPageWikiLink

dbp:authorlink

Crispin St. J. A. Nash-Williams (en)
Joseph Kruskal (en)

dbp:b

1 (xsd:integer)

dbp:date

July 2020 (en)

dbp:first

Joseph (en)
Crispin (en)

dbp:last

Kruskal (en)
Nash-Williams (en)

dbp:p

1 (xsd:integer)

dbp:reason

WP:RSPSOURCES; Fandom page lists YT video as reference (en)

dbp:txt

yes (en)

dbp:wikiPageUsesTemplate

dbp:wordnet_type

http://www.w3.org/2006/03/wn/wn20/instances/synset-musician-noun-1

dbp:year

1960 (xsd:integer)
1963 (xsd:integer)

dct:subject

rdf:type

rdfs:comment

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. (de)
En matemáticas, el árbol teorema de Kruskal indica que el conjunto de finitos más de un conjunto bien cuasi-ordenada de las etiquetas es en sí misma bien cuasi-ordenado (bajo incrustación homeomorfo). El teorema fue conjeturado por Andrew Vázsonyi y demostró por Joseph Kruskal (1960); una breve prueba fue dada por Nash-Williams (1963). es un caso especial de este teorema, de las cuales hay muchas generalizaciones que implican árboles con una incrustación plana, árboles infinitos, y así sucesivamente. Una generalización de los árboles a los gráficos arbitrarias está dado por el . (es)
In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding. (en)
En mathématiques, le théorème des arbres de Kruskal est un résultat de théorie des graphes conjecturé en 1937 par Andrew Vázsonyi et démontré indépendamment en 1960 par Joseph Kruskal et S. Tarkowski, affirmant que l'ensemble des arbres étiquetés par un ensemble muni d'un bel ordre est lui-même muni d'un bel ordre. Ce théorème est un cas particulier du théorème de Robertson-Seymour, dont il a constitué une des motivations. En utilisant ce théorème, Harvey Friedman a pu définir des entiers « incompréhensiblement grands », qu'il a utilisé pour obtenir des résultats nouveaux d'indécidabilité. (fr)
W matematyce Teoria Drzew Kruskala jest jednym z problemów w teorii grafów i . Mówi ona, iż skończony zbiór drzew z uporządkowanymi zasadami tworzenia jest homeomorficzny. Twierdzenie to zostało zaprezentowane przez – węgierskiego matematyka, a udowodnione przez Josepha Kruskala (1960) oraz (1963). Od tego czasu stał się znaczącym przykładem w jako stwierdzenie, którego nie można udowodnić używając ATR0 (forma arytmetycznej rekurencji transfinitowej), a finalne zastosowanie tego twierdzenia umożliwia konstrukcję bardzo szybko rosnącej funkcji TREE(n) (ang. tree – drzewo). (pl)

rdfs:label

Satz von Kruskal (de)
Teorema de los árboles de Kruskal (es)
Théorème de Kruskal (fr)
Kruskal's tree theorem (en)
Teoria Drzew Kruskala (pl)
Теорема Краскала (ru)
克魯斯卡爾樹定理 (zh)

owl:sameAs

prov:wasDerivedFrom

wikipedia-en:Kruskal's_tree_theorem?oldid=1124400522&ns=0

foaf:isPrimaryTopicOf

wikipedia-en:Kruskal's_tree_theorem

is dbo:knownFor of

dbr:Joseph_Kruskal

is dbo:wikiPageDisambiguates of

dbr:Tree_(disambiguation)

is dbo:wikiPageRedirects of

is dbo:wikiPageWikiLink of

is dbp:knownFor of

dbr:Joseph_Kruskal

is foaf:primaryTopic of

wikipedia-en:Kruskal's_tree_theorem