第十五章一张有限的清单

祺乐在草稿纸上画了一个正方形，又添上两条对角线，四个点两两都连上了。

“三角形是 $\frac{4}{3}$，正方形是 $\frac{3}{2}$。”祺乐用笔尖点着那两条斜线，“四个点全连起来，会不会比 $\frac{3}{2}$ 还大？”

$n$ 个顶点两两之间都连上边，这样的图叫完全图，记作 $K_n$。祺乐画的就是 $K_4$：正方形再加上两条对角线。

放回周末的小世界，$K_4$ 就是要求四种情况里任意两种之间都协调好，连“两条都在”和“两条都删”这样隔着两步的也算。不过这一部用不着那些去处和记录的名字，四个顶点直接编号 $1$、$2$、$3$、$4$。

$K_4$ 本身是一整个块，拆不开，第十三章从接缝处拆开的办法用不上。它的耦合常数到底是多少？

我们知道它至少是 $\frac{3}{2}$，因为它里面包含一个正方形，而把正方形上那组困难的表放进去，不会变容易。可是会不会有更难的表，让 $K_4$ 需要比 $\frac{3}{2}$ 更大的倍数？

难就难在“所有可能的表”实在太多了。耦合常数是在所有输入里找最坏的那一个：回答可以有三种，也可以有三千种，每种回答的机会也可以是一个很长的小数。

瀚林说：“先跑一下？让电脑随便造几万组表，一组一组算。”

电脑可以试很多例子，可是试过的例子再多，也证明不了所有例子都不超过某个数。要回答祺乐的问题，得先证明：对每一张固定的图，最坏的情况一定在一张有限的清单里。清单是有限的，原则上就可以把上面的情况一个一个算完，得到准确的答案。

换一种分类方式

回答的种类可以无穷多，这是最大的障碍。

韵吉把第八章那道难题的表抄到本子上，表头的甲、乙、丙、丁写回了四个去处，然后一个一个划掉：电影院、公园、图书馆、游乐场。又在每一列的下面写上：这一份，还有哪几个顶点也有。

电影院那一列，顶点 $2$、$3$、$4$ 各有 $\frac{1}{3}$，顶点 $1$ 没有，这一份就是“顶点 $2$、$3$、$4$ 共有的”。公园那一列是顶点 $1$、$3$、$4$ 共有的，图书馆是 $1$、$2$、$4$，游乐场是 $1$、$2$、$3$。写完一看，四个去处的名字都用不着了。那道难题只剩下四个“三人组”，每组 $\frac{1}{3}$。

韵吉翻到本子第一页。那里抄着八月的那句话：去掉名字，还剩什么。

韵吉的办法是，先别管一个回答叫什么名字，只问它的那一份机会被哪些顶点共同拥有。

那道难题的表特别整齐，每一种回答在有它的三个顶点上机会都一样，正好是一整份。一般的表没有这么整齐。比如在某一组表里，“甲”这个回答在顶点 $1$、$2$ 上都有一部分机会，在顶点 $3$ 上没有。那么甲的这部分机会，就是“顶点 $1$ 和 $2$ 共有的”。另一种回答“乙”的某一部分机会，也可能恰好是 $1$ 和 $2$ 共有的。在新的分类里，我们把它们都归到同一类：$\{1,2\}$。同一种回答在各个顶点上的机会高低不齐时，要先把它切开，才分得清哪一份归哪一类，这是下一章的事。

这样的类，用顶点的集合来标记。从顶点里挑出几个，用花括号括在一起，就是一个顶点的集合，比如 $\{1,2\}$，也可以只有一个顶点，比如 $\{3\}$。$n$ 个顶点能挑出的非空集合只有 $2^n-1$ 个（和第七章数情况一样：每个顶点在或不在，再去掉一个都不在的那种），所以不管原来有多少种回答，新的类最多只有 $2^n-1$ 种。三个顶点时只有 $7$ 种，四个顶点时只有 $15$ 种。

改名字之前，要先立两条规矩

把原来的回答换成“顶点集合”，等于把问题改写了一遍。改写可能出错：它可能把原来不同的东西混在一起，让距离变小；也可能在新问题里找到一个很好的安排，却没法把它变回原问题的安排。那样的话，新问题上的结论就不能用到原问题上。

所以韵吉给这一步立了两条规矩，在本子上改了好几遍才定下来：

1. 任意两个顶点之间的全变差距离，改写前后必须完全一样；
2. 新问题里的任何一种共同安排，都必须能变回原问题的一种安排，而且每条边上“两端不同”的机会不能增加。

只有两条都做到，新问题上得到的保证，才能直接用到原问题上。

韵吉试的改写办法，是把每张概率表切成一层一层。