TREE(3)[1] — большое число, которое является верхней границей решения теоретико-графовой теоремы Краскала . TREE(3) в невообразимое число раз больше числа Грэма. Число TREE(3) столь велико, что стрелочные нотации Кнута и Конвея не способны его записать. Теорема Краскала править Пример последовательности деревьев для случая 3 цветов. Каждое i-е дерево имеет не более i вершин. Ни одно дерево не является топологическим минором более позднего дерева. Число TREE(3) определяется как максимально возможная длина такой последовательности. Запрос «Теорема Краскала»[d] перенаправляется сюда. На эту тему нужно создать отдельную статью. В теории графов деревом называется граф, в котором все вершины соединены рёбрами (возможно, посредством других вершин) и отсутствуют циклы (последовательности рёбер, соединяющие какую-либо вершину саму с собой). В данном случае деревья являются корневыми, то есть имеют определённую вершину - корень. Это понятное, но неформальное определение дерева. Теорема Краскала[2] утверждает последовательность деревьев TREE(n), описанную следующими законами: Каждое i-е дерево имеет не более i вершин. Вершины имеют один из n видов; для TREE(3) удобно называть их «красными», «зелёными» и «синими». Ни одно дерево не должно являться топологическим минором более позднего дерева. TREE(1) даёт единственное дерево с одной вершиной: если попытаться добавить ещё одно с двумя вершинами, при удалении любой из них получится первая. TREE(2)=3, в этой последовательности дерево с одной «красной» вершиной, с двумя «синими» и с одной «синей». Но начиная с TREE(3), происходит настоящий взрыв длины последовательности. Тем не менее, теорема Краскала утверждает, что при любом конечном n последовательность не будет бесконечной. Первое дерево имеет одну «красную» вершину, и вне зависимости от n больше ни одно дерево не имеет «красных» вершин. Иначе, при удалении всех вершин, кроме этой «красной», получилось бы первое дерево. Слабая tree-функция править Определим tree(n), слабую tree-функцию[3], как длину самой длинной последовательности из деревьев с вершинами одного цвета, описываемой следующими законами: Каждое i-е дерево имеет не более i+n вершин. Ни одно дерево не должно являться топологическим минором более позднего дерева. Известно[3], что t r e e ( 1 ) = 2 {\displaystyle tree(1)=2}, t r e e ( 2 ) = 5 {\displaystyle tree(2)=5}, t r e e ( 3 ) ≥ 844424930131960 {\displaystyle tree(3)\geq 844424930131960}, а t r e e ( 4 ) {\displaystyle tree(4)} уже больше числа Грэма. Также известно[4], что TREE(3) намного больше, чем t r e e t r e e t r e e t r e e t r e e 8 ( 7 ) ( 7 ) ( 7 ) ( 7 ) ( 7 ) {\displaystyle tree^{tree^{tree^{tree^{tree^{8}(7)}(7)}(7)}(7)}(7)} (верхний индекс в данном случае обозначает итерированную функцию). Масштаб числа TREE(3) править Распространённым заблуждением является утверждение книги рекордов Гиннесса о том, что число Грэма — самое большое число, которое когда-либо использовалось в математическом доказательстве: эта информация давно устарела, так как число TREE(3) также используется в математическом контексте, и оно несоизмеримо больше числа Грэма. Для представления числа TREE(3) бесполезны не только башни степеней, но и нотации Кнута и Конвея. В массивной нотации Бёрда[5] можно показать, что TREE(3) больше, чем { 3 , 6 , 3 [ 1 [ 1 ¬ 1 , 2 ] 2 ] 2 } {\displaystyle \{3,6,3[1[1\neg 1,2]2]2\}}[6]. Общая скорость роста функции TREE(n) оценивается как f θ ( Ω ω ω ) ( n ) {\displaystyle f_{\theta \left(\Omega ^{\omega }\omega \right)}(n)} в терминах быстрорастущей иерархии. При этом TREE(3) далеко не самое большое число, встречавшееся в математических работах: в последующие годы описывались бо́льшие числа, например такие как SSCG(3)[англ.], SCG(13)[7], а также числа, задаваемые с помощью невычислимых функций, такие, как число Райо. - @archangell_nn