TREE(3)为什么是有限的？——克鲁斯卡尔树定理

本文接上一期有关良拟序的话题，聊聊TREE(3)为什么是有限的。

关于这个问题，我想从解答上期节目开头的那个”写数列“游戏开始：

请你玩玩看如下的这个写数列游戏，游戏目标是写出尽可能长的数字序列。但要符合以下规则：

数列的第n项，最多有n位。
数列左边的项，不能“嵌入”所有其右边的项。“嵌入”的定义如下：

有数字字符串a和b，b的长度大于等于字符a，且存在以下情况：可以从b中删除若干字符，留下与a相等长度的字符串，留下的字符前后位置关系保持不变，并记作b’。如果a比b’按位比较，每一位数字上，a的数字都小于等于b’上的数字，称a可以“嵌入”b。比如：

a=“2” 可以嵌入 b=”3″，其中取b’=’3′

a=“321” 可以嵌入 b=”13312″，其中取b’=’332′

a=“132” 不可以嵌入 b=”2131″，因为b中找不到符合要求的3个字符的子串。

以上是游戏的定义。当用n个数字玩以上游戏，可以写出的数列的最长长度，记作s(n)。

当用一个数字“1”玩这个游戏时：

第一项为：1，再也无法写出第二项。因此s(1)=1。

当用两个数字“1”和”2″玩这个游戏时：

第一项可以写“2”，第二项可以写“1”。如此再也无法写出第三项。但如果第二项写“11“，则还可以写第三项”1“。整个数列是：

2, 11, 1。

所以s(2)=3。

请简单试试写写s(3)的前几项，重点思考两个问题：

是否对任意大的n，s(n)总是有限的？另外，如果去掉游戏中第一个规则，数列长度是否总是有限的？

熟悉TREE(3)的读者，一定能发现这道题的描述与TREE(3)非常像，你大概也能猜到了，在这个写数列游戏中，无论用多少个符号写，最终的数列长度总是有限的。我先来证明这一点，证明的方法就是用上一期讲的“良拟序”关系。

“良拟序”有两个特性：

没有”无穷递降链“（逐渐减小的序列）和无穷”不可比较链“（任意两项都不可比较的序列）。而我们的游戏规则里的嵌入，就好比是一种“小于等于”关系，那么游戏规则是说，不能写出一个比之前元素大的字符串，但可以写更小的或者不可比的。

在游戏中，如果能写出无穷长的序列，那数列中必然存在一个无穷递降链或者无穷不可比子序列，这两个情况都是与良拟序集性质矛盾的。

所以只要证明，那个“嵌入”是一个良拟序关系，那么就证明了，无论如何都无法写出无穷长的序列。

首先，这个“写字符串”游戏中的“嵌入”显然是一个拟序，也就是满足“自反”、“反对称”和“传递性”，请各位自行验证。那么问题就是，怎么证明它是一个“良拟序”（w.q.o.），也就是证明其中不存在无穷递降链和无穷不可比链。

对这个写字符串游戏来说，不存在无穷递降链是比较明显的。因为要递降的话，总的字符串长度迟早要开始递减，这样总是有尽头的。

证明其中不存在无穷不可比链的情况就比较奥妙了，需要些技巧。其实它有一个相当精巧的证明，以下证明来自Graham Higman 1952年的证明（稍改写、翻译和简化）：

以下讨论都在无穷字符串集合上，先定义以下概念：

好序列：一个无穷字符串序列，存在左边某项可以“嵌入”（以下有时也写作 $(\leq)$ ）右边某项。

坏序列：不是“好序列”的序列。

最小坏序列（带递归的定义）：设 $(t_1)$ 是所有坏序列中，某个首项长度最短的字符串, 作为某最小坏序列的首项。则当某个最小坏序列的前n项是 $(t_1)$ , $(t_2)$ , $(t_3)$ ,… $(t_n)$ 时，考察所有以 $(t_1)$ , $(t_2)$ , $(t_3)$ ,… $(t_n)$ 开头的坏序列，取某个长度最短的项作为 $(t_{n+1})$ 。如此所得的坏序列t称为“最小坏序列”。

现在用反证法证明“写字符串”游戏中的“嵌入”是一个“良拟序”。设这个“嵌入”不是“良拟序”，则其中必然存在某个最小坏序列：

$(t_1)$ , $(t_2)$ , $(t_3)$ ,… $(t_n)$ …

记 $(t_i)$ 最左边的字符是 $(a_i)$ ，余下部分的字符串是 $(s_i)$ ：

$(t_i=a_is_i)$

则 $(a_1)$ , $(a_2)$ ,…, $(a_n)$ ,…构成了一个无穷字符序列a， $(s_1)$ , $(s_2)$ ,…, $(s_n)$ ,…也构成了一个无穷字符串序列s，

因为字符之间的 $(\leq)$ 关系是一个良拟序，所以a序列中必存在一个无穷递增子序列（上一篇文章中提到过：良拟序集中的每个无穷序列中，必有”无穷递增子序列”），即存在序列a’：

$(a^{'}=(a_{f(i)})_{i\geq 1})$

使得其中每一对相邻项，左项小于等于右项：

$(a_{f(i)}\leq a_{f(i+1)})$

则我们证明 $(s^{'}=(s_{f(i)})_{i\geq 1})$ 是一个好序列。用反证法，设s’是一个坏序列，有两种情况：

$(f(1)=1)$ ，但 $(s_1)$ 的长度小于 $(t_1)$ ，这与t是最小坏序列矛盾。

$(f(1)>1)$ ，则 $(t^{\prime}=\left\langle t_{1}, \ldots, t_{f(1)-1}, s_{f(1)}, s_{f(2)}, \ldots, s_{f(j)}, \ldots\right\rangle)$ 也是坏序列(这点比较容易，请自行思考验证)。但如此情况下， $(s_{f(1)})$ 长度小于 $(t_{f(1)})$ ，这与t是最小坏序列矛盾。

因此 $(s^{'}=(s_{f(i)})_{i\geq 1})$ 是一个好序列, 则存在某对整数i,j，使得：

$(f(i)\leq f(j))$ 且 $(s_{f(i)}\leq s_{f(j)})$ ，又因为a’是递增序列，所以： $(a_{f(i)}\leq a_{f(j)})$ ，则：

$(a_{f(i)}s_{f(i)}\leq a_{f(j)}s_{f(j)})$

所以，t是一个好序列，这与t是一个坏序列矛盾。

那么既然不可能写出无穷递降序列和无穷不可比序列，那么这个写字符串游戏的嵌入关系就是一个良拟序关系。那么根据游戏规则，游戏必然在有限步骤内结束，就是这样简单。

你有没有发现这么一点，以上推理过程中，并没有用到“第n步只能写出n个数字”这个条件，也就是说，去掉这个条件，序列仍然必定在有限步骤内结束！这是让我一开始非常吃惊和难以想象的一点。

它是为何如此反直觉呢？原因在于，去掉了关于每一项长度的限制后，整个序列的长度其实是可以达到“任意大”，要多大有多大。比如，你希望序列至少有1亿位，那第一项写个1亿位的数字就肯定可以。甚至于第一项写过1亿位之后，很可能整个序列的长度还是可以达到任意大。

甚至整个序列在写下前若干项后，长度还是可以达到任意大（比如，用2个数字玩，第一个数字写了“2”，突然要求序列长度达到1亿，则可以在第二项写1亿个“1”）。而“任意大”与不能“无穷大”这两点观念本身是有冲突的，所以整个事实是非常反直觉的。

那现在讲讲为什么TREE(3)是有限的。你大概也猜出来了，那就是TREE(3)游戏中定义的，关于树之间的“嵌入”也是一种良拟序，这句话也就是“克鲁斯卡树定理”（Kruskal’s Tree Theorem）的内容。所以TREE(3)是有限的，就是这么简单。

TREE(3)游戏中那个“嵌入”，具有自反、反对称和传递性是非常明显的，所以它是拟序。那它为什么是良拟序呢？有很多种证明方法，基本思路就是把树的每个结点打一个标签，那么树之间的“嵌入”其实就是建立标签的“嵌入”，那只要证明这个标签之间的嵌入是一种良拟序关系就可以了。具体过程留给各位思考。

那么，同样这里有个非常令人吃惊的结论就是，TREE游戏中，“第n棵树中最多只能有n个结点”，去掉这个规则，TREE游戏仍然不能无限的玩下去。那为什么要加入这个规则呢？

这里面有点历史故事。“克鲁斯卡尔树定理”是克鲁斯卡尔在1960年证明的。其实克鲁斯卡尔树定理后来也衍生出好几个版本，不同版本里关于那个嵌入的定义稍微有点区别，但不管那个版本，要点就是确保那个嵌入的定义是一个“良拟序”。

(Joseph Kruskal，January 29, 1928 – September 19, 2010)

而我们现在熟悉的那个TREE游戏中的定义，其实是现年73岁的，俄亥俄州立大学教授，哈维·弗里德曼（Harvey Friedman）在1980年代提出的，他把的这个版本的“嵌入”称为克鲁斯卡尔树定理的“小型化”。叫“小型化”是因为，原版的树定理其描述是一个二阶逻辑的命题，而改造后的版本变成了一阶逻辑的，所以变得更为“通俗易懂”，当然还有一些数学上的意义。

(Harvey Friedman, born 23 September 1948)

而到2006年前后，弗里德曼又提出了大家熟悉的这个TREE游戏。在游戏中，他加入了结点数量的限制。其原因就是为了让这个TREE游戏从“任意大”变成一个确切的有限的数字。不加入结点数条件的话，这个TREE游戏的长度是任意大，很难让人理解。加入结点数条件后，每个TREE(n)都变成一个确切的有限数字，这使的TREE序列一下子名声大噪，获得了非常好的传播效果，这就是TREE游戏的来龙去脉。

知道了TREE游戏的来龙去脉，理解另外两个比TREE还大的序列就太容易了，它们就是SSCG序列和SCG序列，它们也都是弗里德曼发明。它们其实就是把TREE游戏中树之间的嵌入，推广到图上。就是两个图，也可以定义嵌入关系，你要做的就是保证这种嵌入是一个良拟序，那么你就可以产生一个大数序列，是不是非常简单？

simple subcubic graph (SSCG)：有限简单图，其中每个顶点的度数最多为3。SSCG上也可以类似TREE游戏定义一个“嵌入”关系，从而定义SSCG序列。已知：

SSCG(0) = 2, SSCG(1) = 5

SSCG(3)远大于 TREE(3) 和 TREE(3) $(^{TREE(3)})$

subcubic graph(SCG)则是从SSCG中去掉“简单图”的限制。

最后，分析一下我对上期出的那个写字符串思考题的思考。其实这道题是一个开放题，没有现成答案。那道题里的那个“嵌入”定义其实是来自于英国数学家Graham Higman在1952的的一篇论文，他证明了这样一个嵌入是一种“良拟序”。既然是良拟序，那好办了，大老李就直接拿过来，构造了那个写字符串的游戏，并且我们能确信，这个游戏可以在有限步骤能完成。你也能发现这个游戏有点像TREE(3)游戏限制在一条直线上玩。

以下我用s(n)表示用n个字符玩这个游戏时，最大的序列长度游戏征答发布后我到现在只收到3个读者来信解答，其中署名金承锦的听众解答最为认真，她手动在Excel表里排列出了s(4)的可能的最长序列，这已经是非常细心的工作了。她也发现s(4)的最终数值是非常大，远超出可以手动解决的程度。那么以下我们来分析下，会发现s(4)的数值也超过了通过简单编程暴力求解的程度。

用s(n)表示用n个字符玩这个游戏时，可以写出的最长序列长度，那么s(1)=1和s(2)=3是很明显的。求s(3)用手动排会有点麻烦，大老李写了个程序，去求解了一下s(3)。算法就是贪心算法，对每一个数字尽可能写得长，并且从左到右，每个数字尽可能写得大。

用这个程序求解，得到s(3)=17，就是用3个数字玩这个游戏，可以写出的最长17个数字的数列：

[‘3′, ’22’, ‘211’, ‘1121’, ‘11112’, ‘111111’, ‘11111’, ‘1112’, ‘1111’, ‘121’, ‘112’, ‘111’, ’21’, ’12’, ’11’, ‘2’, ‘1’]

但是用这个程序求解s(4)是等不到答案了，因为这个贪心算法明显效率太低了。只得到以下开头的几项：

[‘4′, ’33’, ‘322’, ‘3211’, ‘31121’, ‘311112’, ‘3111111’, ‘22311111’, ‘222231112’, ‘2222231111’, ‘22222223121’, ‘222222223112’, ‘2222222223111’]

当然，我们可以分析一下s(n)的可能范围。关于s(n)的范围，最重要一点是算出s(n)中的最长的字符串长度，记作。

关于|max(s(n))|，我有个猜想：

$(|max(s(n))| \approx |max(s(n-1))|^2)$

对s(4)，金承锦排出的|max(s(4))|是48，可能确切结果也就是49或50了。

另外，我还有一个对s(n)的下界保守估计：

$(s(n) > (n-1)^{2^{2^{n-2}}})$

可以证明 $(s(4)>3^{20})$

也非常欢迎有人给出s(n)更加精确的大小估计。

总结：

TREE(3)的有限性是“克鲁斯卡尔树定理”的一个简单推论。

“克鲁斯卡尔树定理”是说TREE游戏中的那个“嵌入”关系，是一种良拟序。

良拟序有两个性质：没有无穷递降链，没有不穷不可比链。

根据这两个性质，就自然地导出了TREE游戏必然在有限步骤内结束。

由此，我们也可以构造一些产生大数序列的游戏，方法就是找到某个无穷集合上的一种良拟序关系，利用良拟序的性质，我们可以非常简单得构造很大，但是有限的数字。

Share this:

Related