Teoria drzew Kruskala
Z Wikipedii, wolnej encyclopedia
Teoria drzew Kruskala – w matematyce jeden z problemów w teorii grafów i teorii porządku. Mówi ona, iż skończony zbiór drzew z uporządkowanymi zasadami tworzenia jest homeomorficzny. Twierdzenie to zostało zaprezentowane przez Andrew Vázsonyiego – węgierskiego matematyka, a udowodnione przez Josepha Kruskala (1960)[1] oraz Nasha-Williamsa (1963)[2]. Od tego czasu stał się znaczącym przykładem w teorii odwrotności 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).