Для начла разберёмся, что такое граф. Граф – это некое соединение 2-х или более вершин рёбрами. Есть цикличные графы, где какие-нибудь рёбра соединяются, а есть нецикличные графы, где ребра никак не пересекаются. Такие графы называются деревьями.
Если описывать теорему это своими словами, то это примерно так: у нас есть бесконечная последовательность деревьев. Допустим, i – поддерево, меньшее, чем дерево j. Тогда, когда-нибудь, в этой последовательности будет, что i – часть j. Тут вроде бы все верно, но Краскал смог это доказать.
Далее у нас идёт Фридман, который уменьшил эту задачу, сделав так, что дерево t с коэффициентом i имеет не более i+k вершин. И он такой: "Сколько нужно деревьев, чтобы нашлось поддерево, которое будет частью другого дерева". Допустим, это количество N. Теперь, если вы дадите число k, то Фридман должен вам дать ответ, сколько деревьев нужно.
Тут самое интересное. Если k=1, то N=3, если k=2, то N=11, а вот если k=3, то N становится таким ебанутым числом, что оно само от себя хуеет. Вот это недосягаемое дерево называют TREE(3).
Запишем это число особым образом. Вот у нас есть число Грэма, если его записать кое-каким хитровыебанным способом, то получится G64(3), теперь оно кажется не таким страшным, да? Теперь, если мы запишем TREE(3) таким же способом, то получится G(G(187196)).
*Шутки про G(G(187196))+1 объявляю открытыми.
Спасибо за то, что вы с нами.
С любовью, Рителлинг favorite
