脚本宝典收集整理的这篇文章主要介绍了【说句闲话】什么是 TREE 函数？，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

零、前言

中国国内对于 (operatorname{TREE}) 函数这个数的资料确实有点少，我所看过的大部分文章、视频说的都是关于 (operatorname{TREE}) 函数的大小。

比如 (operatorname{TREE}(3)) 和葛立恒数的大小比较（虽然确实，葛立恒数在 (operatorname{TREE}(3)) 面前就是个渣渣）。

但极少地提到 (operatorname{TREE}) 函数到底是个什么东西。当然我这里也就只是说明一下 (operatorname{TREE}) 函数到底是个啥，剩下的那些证明...我看不懂。

说实话，(operatorname{TREE}) 实际意义暂时不大... 就是个数而已...

参考资料：

• Numberphile - The Enormous TREE(3)
• 大老李 - 画树画出一棵超大数--TREE(3)漫谈
• 大老李 - TREE(3)为什么是有限的？——克鲁斯卡尔树定理

在此表示感谢。

一、(operatorname{TREE}) 函数

1. 定义

(operatorname{TREE}) 是一个函数，有一个自变量 (x)。提出者 Harvey Friedman。

(operatorname{TREE}) 函数来源于一个连续画树的游戏。

在这个游戏中，你可以使用 (x) 种不同颜色的笔连续画树的节点，而边的颜色我们不考虑。

当然是有规则的：

• 规则 1：画的第 (n) 棵树上的节点个数不能超过 (n)。
• 规则 2：画的第 (n) 棵树，前 (n - 1) 棵树不能“包含”在第 (n) 棵树里。

而 (operatorname{TREE}) 函数的函数值为通过上述规则所能画出最多树的个数。

注意规则 2 的“包含”，数学中有一个名词，叫“inf-embeddable”（下确界-可嵌入）。

意思就是：

我们设两棵树 (T_1) 和 (T_2)。判断 (T_2) “包含于” (T_1)：

• (T_2) 是 (T_1) 的子图。
• (T_2) 中取若干节点，这若干节点如果可以跟 (T_1) 的节点建立一一对应关系，而且两颗树中，任意对应两个节点的 最近公共祖先 是同一颜色。

完全满足上面两条的我们判断 (T_2) “包含于” (T_1)。

2. (operatorname{TREE}(1)) 和 (operatorname{TREE}(2))

我们先从人畜无害的 (operatorname{TREE}(1)) 和 (operatorname{TREE}(2)) 开始画树。

在 (operatorname{TREE}(1)) 中，很明显我们只能画出一个根节点。所以 (operatorname{TREE}(1) = 1)。

在 (operatorname{TREE}(2)) 中，我们可以先画出一个根节点，假设颜色为绿色，然后我们画第二棵，为两个红色的节点连成的树，然后画第三个，一个红色的根节点。我们不能再画下去了，并且其他方法也不会大于三棵树，所以 (operatorname{TREE}(2) = 3)。

3. 从 (operatorname{TREE}(3)) 到 (operatorname{TREE}(x))

可以自己尝试。画不下去的时候要保证这是树的个数最大的方案，如果不是，可以换一种画法，直到找到最大的那种。

但是我不建议你尝试。

脚本宝典总结

以上是脚本宝典为你收集整理的【说句闲话】什么是 TREE 函数？全部内容，希望文章能够帮你解决【说句闲话】什么是 TREE 函数？所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。