第四部　树和圈

第十章没有圈的时候

开学以后，祺乐的作业本背面画满了圈。正方形旁边是五边形，五边形旁边是六边形，有几个圈的边上还标着小小的分数。

正方形上的事，我们只弄清了一半。第八章那道难题说明，不管答案单怎么写，倍数都至少是 $\frac{3}{2}$ 。另一半还空着。不管出题人放什么签盒，安排人是不是总能把倍数压在 $\frac{3}{2}$ 以内？

祺乐把本子推过来：“正方形要是能做到 $\frac{3}{2}$ ，五边形呢？六边形呢？”

韵吉问：“对每一组签盒都做到？”

“对，每一组。圈变长了，是不是就更难？”

谁也答不上来。祺乐翻到新的一页，这回没画圈，只画了三个点排成一排，把中间那个圈了起来。我们想先看看没有圈的时候是什么样。

只能按撤销的顺序删

回到周六去哪儿的问题。有的助手不许你随便挑一条删，只能像按“撤销”键那样，从最近记下的那条往回删。假设“不喜欢太吵的地方”是后记下的，那就只能先删怕吵，再删电影。这样只会走到三种情况，排成一排：两条都在，只剩电影，两条都删。“只剩怕吵”根本走不到。

把三种情况叫作顶点 $X$ 、 $Y$ 、 $Z$ ， $X$ 连 $Y$ ， $Y$ 连 $Z$ 。这一回换一组假设的签盒，不用标准签盒：

顶点	情况	电影院（甲）	公园（乙）	图书馆（丙）
$X$	两条都在	$\frac{1}{2}$	$\frac{1}{4}$	$\frac{1}{4}$
$Y$	只剩电影	$\frac{1}{2}$	$\frac{1}{2}$	$0$
$Z$	两条都删	$\frac{1}{4}$	$\frac{3}{4}$	$0$

这三张表都讲得通。从 $X$ 到 $Y$ ，助手忘了你怕吵，就不再特意想到安静的图书馆；从 $Y$ 到 $Z$ ，电影约定删了，电影院少了。游乐场三种情况都是零，只是为了让例子简单。

我们希望 $X Y$ 这一步删除做到单独最好，也就是最大耦合， $Y Z$ 这一步也做到最大耦合。

两条边各自单独找最大耦合不难。要做的是把两张“两栏签”拼成一张“三栏签”，而且拼完以后，两条边各自看到的样子都不能变。

办法是从祺乐圈起来的那个点下手，先抽中间的 $Y$ ，再分别补上两边。

图 11：三个顶点排成一排：先抽中间，再按条件补两边。 — 图 11三个顶点排成一排：先抽中间，再按条件补两边。

为了少写字，下面用甲、乙、丙代替电影院、公园、图书馆。照第六章的办法， $X Y$ 的最大耦合是三种两栏签：“甲甲”占 $\frac{1}{2}$ ，“乙乙”占 $\frac{1}{4}$ ，“丙乙”占 $\frac{1}{4}$ （前一个字是 $X$ 的回答，后一个字是 $Y$ 的回答）。 $Y Z$ 的最大耦合是：“甲甲”占 $\frac{1}{4}$ ，“乙乙”占 $\frac{1}{2}$ ，“甲乙”占 $\frac{1}{4}$ （前一个字是 $Y$ ，后一个字是 $Z$ ）。两条边的全变差距离都是 $\frac{1}{4}$ 。

现在先按 $Y$ 的表抽 $Y$ ：甲、乙各占一半。

如果 $Y$ 抽到甲：在 $X Y$ 的签里， $Y$ 是甲的只有“甲甲”一种，所以 $X$ 写甲。在 $Y Z$ 的签里， $Y$ 是甲的有“甲甲”和“甲乙”两种，各占 $\frac{1}{4}$ ，一样多，所以 $Z$ 等机会写甲或乙。
如果 $Y$ 抽到乙：在 $X Y$ 的签里， $Y$ 是乙的有“乙乙”和“丙乙”，各占 $\frac{1}{4}$ ，所以 $X$ 等机会写乙或丙。在 $Y Z$ 的签里， $Y$ 是乙的只有“乙乙”，所以 $Z$ 写乙。

这样得到四种三栏签，每种机会都是 $\frac{1}{4}$ ：

签	$X$	$Y$	$Z$
一	甲	甲	甲
二	甲	甲	乙
三	乙	乙	乙
四	丙	乙	乙

你可以数一数： $X$ 这一栏，甲占两种签、乙和丙各占一种，正好是 $\frac{1}{2}$ 、 $\frac{1}{4}$ 、 $\frac{1}{4}$ ； $Z$ 这一栏，甲占一种、乙占三种，正好是 $\frac{1}{4}$ 、 $\frac{3}{4}$ 。都和原表一样。 $X Y$ 只在第四种签上不同，机会 $\frac{1}{4}$ ； $Y Z$ 只在第二种签上不同，机会也是 $\frac{1}{4}$ 。两条边都做到了最大耦合。

这四种签，就是助手的四种答案单。比如签四：两条都在时去图书馆，删了怕吵改去公园，再删电影，还是公园。只能按撤销的顺序删的时候，两步删除都做到了单独最好，一点都不多付。

图 12：把这个抽法画成树状图：先抽 Y，再按条件补上 X 和 Z，四片叶子就是四种三栏签。 — 图 12把这个抽法画成树状图：先抽 $Y$ ，再按条件补上 $X$ 和 $Z$ ，四片叶子就是四种三栏签。

刚才“在 $Y$ 是乙的情况下， $X$ 等机会写乙或丙”，用的是条件概率：已经知道 $Y$ 是什么以后，只在 $Y$ 取这个值的那些签里看， $X$ 各种回答各占多大比例。做法就是“缩小范围再数一数”。

停下来算一算

换一组表。 $X$ ：甲 $\frac{1}{2}$ 、乙 $\frac{1}{2}$ 。 $Y$ ：甲 $\frac{1}{2}$ 、乙 $\frac{1}{4}$ 、丙 $\frac{1}{4}$ 。 $Z$ ：乙 $\frac{1}{2}$ 、丙 $\frac{1}{2}$ 。两条边的最大耦合已经替你找好：

$X Y$ ：“甲甲”占 $\frac{1}{2}$ ，“乙乙”“乙丙”各占 $\frac{1}{4}$ （前一个字是 $X$ ）；
$Y Z$ ：“甲乙”“甲丙”“乙乙”“丙丙”各占 $\frac{1}{4}$ （前一个字是 $Y$ ）。

先抽 $Y$ ，再补两边，写出所有的三栏签和它们的机会。 $X Y$ 、 $Y Z$ 不同的机会各是多少？

答案见附录二。

展开本章“停下来算一算”的答案

$Y$ 抽到甲（ $\frac{1}{2}$ ）时， $X$ 只能写甲， $Z$ 等机会写乙或丙； $Y$ 抽到乙（ $\frac{1}{4}$ ）时， $X$ 、 $Z$ 都写乙； $Y$ 抽到丙（ $\frac{1}{4}$ ）时， $X$ 写乙， $Z$ 写丙。四种三栏签（按 $X$ 、 $Y$ 、 $Z$ 的顺序）是“甲甲乙”“甲甲丙”“乙乙乙”“乙丙丙”，各占 $\frac{1}{4}$ 。 $X Y$ 只在“乙丙丙”上不同，是 $\frac{1}{4}$ ； $Y Z$ 在前两种上不同，是 $\frac{1}{2}$ 。两个数正好是两条边的全变差距离。

从一棵树的根出发

三个点排成一排，就是一棵树。更一般的没有圈的图叫树：所有顶点连成一片，却没有任何圈。几棵互不相连的树放在一起，叫森林。下面不再管这棵树是从哪种删除规矩来的，去掉名字，只讲顶点。

图 13：从根出发的一棵树。每个新顶点都只通过一条边接到已经抽好的部分上。 — 图 13从根出发的一棵树。每个新顶点都只通过一条边接到已经抽好的部分上。

在树上可以重复刚才的做法。任选一个顶点当作“根”，先按它的表抽出回答。然后一层一层往外走：每碰到一条新的边，它连着一个已经抽好的顶点（叫“父顶点”）和一个还没抽的顶点（叫“子顶点”）；按这条边的最大耦合，在父顶点已有回答的条件下，抽出子顶点的回答。

从根开始一步步检查：父顶点的边际分布对，按条件抽出来的子顶点的边际分布也就对，而且这条边两端的联合分布正好是预先选好的最大耦合。每加进一个顶点，已经抽好的部分都不需要改动。

这里靠的是“没有圈”。在树上，每个新顶点只和已经抽好的部分有一条边相连。它只需要和一个已经定下来的邻居配合，不会同时受两个已经定下来的顶点限制。第八章正方形里的麻烦，就出在那条让路线首尾相接的边上。

所以，在树上，每条边都能同时做到最大耦合；森林的各棵树分开安排就行。森林的耦合常数是 $1$ 。

这种沿着树一条边一条边接起来的做法，前人早就用过。在研究“随机舍入”（按一定的机会，把带小数的方案变成整数方案）的文献里，它是一种标准技巧。我们关心它为什么管用，什么时候会用不了。

远处的两个顶点呢

树上保证的只是边。比如上面 $X$ 和 $Z$ 之间没有边，它们不同的机会是 $\frac{1}{2}$ ，正好等于它们两张表的全变差距离，但这只是这个例子的巧合，一般并不保证。我们只要求控制图上有边的那些顶点对。如果把不相邻的顶点也连上边，提的要求就变了，还可能凭空造出圈来。

回到周六，要是两条记录先删哪条随你，四种情况就首尾相接，连成了正方形。

树这么好办，碰到一个圈，能不能拿掉一条边，把它变成树？