Тыщ-тыдыщ-тыщ-тыщ! Вот и статейка долгожданная подъехала! Судя по названию, думаю, вы догадались, что сейчас речь пойдёт о невообразимо огромном числе. Вспомните мою старую статью про число Грэма. Вспомнили? Ну и хорошо. Теперь поймите, что наше любимое число G - это всего лишь детский лепет по сравнению с тем, что я сейчас буду вам рассказывать!
Надеюсь, вас эта статья очень заинтересует и вы дочитаете её до конца, но сначала я бы советовал ознакомиться с упомянутой выше статьёй про число Грэма, т.к. я буду опираться на данные, исходящие из неё.
Ну, погнали!
Для понимания моей статьи мы в начале должны с вами такое понятие, как математический граф. А именно древовидный граф. Чтобы долго на это времени не тратить, просто посмотрите на картинку ниже.
Итак, нам нужно взять бесконечную последовательность из конечных деревьев. Краскал доказал, что в такой последовательности обязательно существует поддерево i, меньшее чем j, которое вкладывается в это j как его часть. Если попроще, то всегда есть участок какого-то графа, который является частью большего графа, его копией.
Вроде бы с "житейской" точки зрения это и так очевидно, всё вроде бы понятно, что на бесконечности всегда найдётся что-то, являющееся копией чего-то. Но Краскал смог это доказать.
Теорема Краскала позволяет построить минимальное остовное дерево, в связанном с ним взвешенном неориентированном графе.
Итак, чтобы у вас вот этот вот алгоритм уложился в голове, я постараюсь объяснить вам выделенные жирным шрифтом термины (и потом вы ещё раз прочитайте эту теорему, чтобы её получше понять).
Неориентированный граф - это граф, у которого все ребра неориентированы, то есть ребрам которого не задано направление.
Если сказать проще, то это такая математическая хрень, у которой есть вершины (тобишь точки) и рёбра (отрезки между вершинами), направления которых не заданы
Остовное дерево - такое дерево в графе, состоящее из минимального подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам.
Минимальное остовное дерево (его так же называют минимальным покрывающим деревом) в связанном взвешенном графе - это такое остовное дерево этого графа, имеющее минимальный возможный вес. В данном случае под понятием "вес дерева" подразумевается сумма весов входящих в него рёбер.
Итак, теперь мы разобрались с формулировкой теоремы. Но ведь просто услышать - этого мало, верно? А как она применяется? Вот на даной ниже гифке я вам показал пример работы этого алгоритма. Ведь лучше 1 раз увидеть, чем 100 раз услышать)
Итак, ну теперь-то уж с теоремой, думаю, вам всё понятно. Но мы же с вами хотели почитать про огромное число, а не про какой-то там ноунеймовский алгоритм, поэтому переходим сразу к делу!
Был такой мужик, звать которого Харви Фридман (на картинке вы можете его видеть), который ну вот не мог просто вот взять и не "сузить" эту задачку.
Сначала наш мужик подумал так: возьмём какое-то дерево t с коэффициентом i, имеющее не более i+k вершин, после чего он задумался: "Сколько нужно деревьев, чтобы нашлось поддерево, которое будет частью другого дерева?"
Т.е. мы должны назвать ему k, а он нам посчитает кол-во деревьев N, при котором вышеописанное условие вложения выполняется.
Вроде бы всё кажется довольно простым, верно? Ну я должен вас предупредить, что эта зависимость N от k просто невероятно велика.
Итак, давайте возьмём k=1 => N=3
А что, если мы возьмём k=2? Ну тогда число N будет равняться 11
Думаю, вы спросите: "Админ, ну и зачем ты расписал это всё так подробно, хотя тут огромными числами вообще не пахнет?"
Так вот вся суть в том, что если мы уже возьмём число k, равное трём, то мы получим на столько огромное число, что оно само с себя в обморок упадёт! Его называют числом TREE(3)
Давайте я приведу пример на известном нам ранее числе Грэма. Если я его запишу в форме G64(3), то вроде бы ничего особого тут нету, верно? Ну давайте подобным образом запишем число TREE(3) (т.е. выразим его через число Грэма). Ну что, готовы? Если да, то держите: G(G(187196)). Кошмарно, да? Есть разные возможности записать это число, но это является наглядным примером, что невообразимое число Грэма по сравнению с этим - всего лишь какая-то муха)
Спасибо большое за прочтение этой статьи! Я очень старался найти для вас качественную информацию и объединить её воедино! В ближайшее время ждите ещё одной статейки!)