第十三章从接缝处拆开

我们已经会处理树，也会处理一个圈。如果一张图里有好几个圈，只在某些顶点上连在一起，会怎样？每多接上一个圈，是不是就要再多付一次代价？

祺乐当时问：“能不能在两块图的接缝处，把各自最好的安排拼起来？”

这一章的图大多带着三角形、五边形，不是删记录得来的。两条记录随便删，得到正方形；三条记录得到立方体；几个三角形挂在一起的图，不会这样冒出来。所以这一章去掉名字，只用顶点的编号和字母。

删记录用不到这些图，我们还是把它们弄清楚了，为的是回答本章开头的问题，看清图的形状怎样影响难度。拼的办法也不新。第十章在树上一条边一条边地接，第十一章在圈上拿掉一条边以后，沿剩下的路也是这样接的，现在只是把它用到接缝上。后面方框里“要求少一些，问题不会更难”的道理，第十五章讲四个顶点两两相连的图时还要用。

两个三角形共用一个顶点

先看最简单的情形：两个三角形只共用一个顶点 $O$。

我们分别给两个三角形找好各自最好的共同安排。两边的安排都要求 $O$ 的边际分布是 $O$ 自己那张表，可是两边各抽一次，抽出来的 $O$ 不一定相同，所以不能把两张签简单地放在一起。

解决办法和树上一样：先抽好第一个三角形，再把已经抽到的 $O$ 的回答带进第二个三角形，在 $O$ 取这个回答的条件下，按第二个三角形自己的安排抽出它另外两个顶点。

因为两个三角形给 $O$ 的边际分布是同一张表，这样拼起来以后，第二个三角形内部看到的联合分布一点没变，第一个也没变，两边各自的保证全都保留。

所以整张图的倍数，就是两个三角形中较大的那个，不会因为多接了一个三角形而变大。

块和割点

把这个想法推广，需要两个词。

如果拿掉某个顶点（连同和它相连的边），原来连在一起的图会断开，这个顶点就叫割点。上图里的 $O$ 和 $Q$ 都是割点。如果拿掉某条边会让图断开，这条边叫桥。

把一张图从所有割点处拆开，会得到一些片段。每一片要么是一条桥，要么是一个“结实”的部分：在这一部分里随便拿掉一个顶点，剩下的仍然连在一起。这样的片段叫块。上图有三个块：两个三角形，和那条桥。

块和割点之间的连接关系，本身构成一棵树。所以可以像树上那样，从任意一个块开始，一块一块地往外接，每接一块，只在一个割点上和已经抽好的部分相连。

于是祺乐证明了： $$c(G)=\text{各个块的耦合常数中最大的那个}$$

一方面，整张图的任何安排，只看其中一个块，仍然是这个块的合法安排，所以整张图不会比最难的那个块容易；另一方面，按割点一块块地拼，又说明它不会更难。

仙人掌

如果一张图里每条边最多只属于一个圈，它的块就只能是桥或者圈。这样的图叫仙人掌图。祺乐画了一个三角形接一个五边形，又在接缝上挂了几个三角形，看上去真像一节一节的仙人掌。

由上面的公式，仙人掌图的耦合常数由它最长的圈决定：最长的圈有 $\ell$ 个顶点，常数就是 $2-\frac{2}{\ell }$；如果根本没有圈，它就是森林，常数是 $1$。比如祺乐画的那张图，三角形和五边形在一个顶点上相接，常数是 $\frac{8}{5}$。在接缝上再挂多少个三角形，它都还是 $\frac{8}{5}$。

由此还能看出，只有森林能对每一组表都让所有边同时做到最大耦合。只要图里有一个圈，把第十二章那组困难的表放到这个圈上，倍数就已经大于 $1$。

拆不开的地方

这种拆法也有边界。如果两个圈共用了一整条边，它们就共用了两个顶点，整个构成一个块。只固定其中一个共用顶点的回答，并不能保证另一个共用顶点也对得上。这时就不能简单地拼接了。

图越复杂，这样拆不开的块就越多。比如四个顶点两两相连的完全图，本身就是一个块，里面有好几个互相交叠的圈。这样的图要换一种办法，留到第五部。

可这一章的办法用不到删记录上。正方形本身就是一整块，立方体也是，哪里都拆不开。

瀚林盯着祺乐那张挂满三角形的仙人掌图，问：“这些签，在电脑上怎么抽？”