组合学笔记 (Part 2): 高级计数方法

这是 组合学笔记 系列的第二期。

4. 鸽巢原理及其变种

4.1 基本鸽巢原理

定理 4.1（简单形式） 如果将 $n+1$ 个物体放入 $n$ 个盒子中，那么至少有一个盒子包含不少于 $2$ 个物体。

定理 4.2（一般形式） 如果将 $m$ 个物体放入 $n$ 个盒子中，那么至少有一个盒子包含不少于 $\lceil m/n \rceil$ 个物体。

4.2 Erdős–Szekeres 定理

定理（Erdős–Szekeres） 任意 $n^2+1$ 个不同实数构成的序列中，必存在长度为 $n+1$ 的单调子列（单调递增或单调递减）。

4.3 Dirichlet 逼近定理

定理（Dirichlet） 对于任意实数 $\alpha$ 和正整数 $n$，存在整数 $p, q$，其中 $1 \leq q \leq n$，使得： $\left|q\alpha - p\right| < \frac{1}{n}$

等价地：$\left|\alpha - \frac{p}{q}\right| < \frac{1}{nq} \leq \frac{1}{q^2}$

4.4 Ramsey 理论简介

定义（Ramsey 数） $R(s, t)$ 是最小的正整数 $n$，使得对完全图 $K_n$ 的边进行任意红蓝二染色后，必存在红色的 $K_s$ 或蓝色的 $K_t$。

定理：$R(3, 3) = 6$

5. 生成函数

5.1 普通生成函数（OGF）

定义：设 $\{a_n\}_{n=0}^{\infty}$ 是一个数列，其普通生成函数定义为： $G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$

乘法运算（卷积）： $G(x) \cdot H(x) = \sum_{n=0}^{\infty} c_n x^n, \quad c_n = \sum_{k=0}^{n} a_k b_{n-k}$

常见序列：

• 几何级数：$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$
• 二项式：$(1+x)^m = \sum_{n=0}^{m} \binom{m}{n} x^n$
• 负二项式：$\frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n$

卡特兰数的生成函数： $C(x) = \sum_{n=0}^{\infty} C_n x^n = \frac{1-\sqrt{1-4x}}{2x}$

5.2 指数生成函数（EGF）

定义：设 $\{a_n\}_{n=0}^{\infty}$ 是一个数列，其指数生成函数定义为： $E(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} = a_0 + a_1 \frac{x}{1!} + a_2 \frac{x^2}{2!} + \cdots$

乘积公式（二项卷积）： $E(x) \cdot F(x) = \sum_{n=0}^{\infty} c_n \frac{x^n}{n!}, \quad c_n = \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}$

5.3 贝尔数的指数生成函数

贝尔数 $B_n$ 表示 $n$ 元集合的划分数。

定理：贝尔数的指数生成函数为： $B(x) = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x - 1}$

5.4 狄利克雷生成函数（DGF）

定义：设 $\{a_n\}_{n=1}^{\infty}$ 是一个数列，其狄利克雷生成函数定义为： $F(s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s}$

黎曼ζ函数： $\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}$

狄利克雷卷积： $(f * g)(n) = \sum_{d|n} f(d) \cdot g\left(\frac{n}{d}\right)$

5.5 分拆数的生成函数

定理（Euler）： $P(x) = \sum_{n=0}^{\infty} p(n) x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}$

五边形数定理： $\prod_{k=1}^{\infty} (1-x^k) = \sum_{m=-\infty}^{\infty} (-1)^m x^{m(3m-1)/2}$

6. 特殊计数序列

6.1 卡特兰数（Catalan Numbers）

定义： $C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$

前几项：$C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42$

递推关系： $C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$

组合解释：

• Dyck路径（从 $(0,0)$ 到 $(2n,0)$，不降到 $x$ 轴下方）
• $n$ 对括号的正确匹配
• $n+1$ 个叶子的满二叉树
• $(n+2)$ 边形的三角剖分

6.2 Dyck 路径

定义：从 $(0,0)$ 到 $(2n,0)$ 的格路，每步 $(1,1)$ 或 $(1,-1)$，不降到 $x$ 轴下方。

数目：$n$ 阶 Dyck 路径的数目等于第 $n$ 个卡特兰数 $C_n$。

Narayana数 $N(n,k)$ 计数恰有 $k$ 个峰的 $n$ 阶 Dyck 路径： $N(n,k) = \frac{1}{n}\binom{n}{k}\binom{n}{k-1}$

6.3 斯特林数（Stirling Numbers）

第一类斯特林数 $c(n,k)$（或 $\left[{n \atop k}\right]$）：表示 $n$ 个元素恰好分成 $k$ 个轮换的排列数。

递推关系： $c(n,k) = c(n-1,k-1) + (n-1)c(n-1,k)$

第二类斯特林数 $S(n,k)$（或 $\left\{{n \atop k}\right\}$）：将 $n$ 个元素的集合划分为 $k$ 个非空子集的方式数。

递推关系： $S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k)$

显式公式： $S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}j^n$

与幂的关系： $x^n = \sum_{k=0}^{n} S(n,k) (x)_k$ 其中 $(x)_k = x(x-1)\cdots(x-k+1)$ 为下降阶乘。

6.4 施罗德数（Schröder Numbers）

大施罗德数 $R_n$：从 $(0,0)$ 到 $(2n,0)$ 的格路，每步 $(1,1)$、$(1,-1)$ 或 $(2,0)$，始终不低于 $x$ 轴。

前几项：$R_0 = 1, R_1 = 2, R_2 = 6, R_3 = 22, R_4 = 90$

生成函数： $R(x) = \frac{1-x-\sqrt{1-6x+x^2}}{2x}$

与卡特兰数的关系： $R_n = \sum_{k=0}^{n} \binom{n}{k} C_k$

6.5 分拆数（Partition Numbers）

定义：$p(n)$ 计数 $n$ 的整数分拆个数（不计顺序）。

递推公式（由五边形数定理）： $p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + \cdots$

其中符号按 $+,+,-,-,+,+,-,-,\ldots$ 周期变化。

7. 波利亚计数原理

7.1 群论基础

定义 7.1.1（群） 设 $G$ 是一个非空集合，$\cdot$ 是 $G$ 上的二元运算。如果满足以下条件，则称 $(G, \cdot)$ 为一个群：

1. 封闭性：对于任意 $a, b \in G$，有 $a \cdot b \in G$；
2. 结合律：对于任意 $a, b, c \in G$，有 $(a \cdot b) \cdot c = a \cdot (b \cdot c)$；
3. 单位元：存在 $e \in G$，使得对任意 $a \in G$，有 $e \cdot a = a \cdot e = a$；
4. 逆元：对于任意 $a \in G$，存在 $a^{-1} \in G$，使得 $a \cdot a^{-1} = a^{-1} \cdot a = e$。

例 7.1.1（对称群 $S_n$） 设 $X = \{1, 2, \ldots, n\}$，$S_n$ 是 $X$ 上所有置换构成的集合。$(S_n, \circ)$ 构成群，称为 $n$ 次对称群，$|S_n| = n!$。

例 7.1.2（循环群 $C_n$） $C_n = \{e, \rho, \rho^2, \ldots, \rho^{n-1}\}$，其中 $\rho$ 表示绕中心逆时针旋转 $\frac{2\pi}{n}$，$|C_n| = n$。

例 7.1.3（二面体群 $D_n$） 正 $n$ 边形的对称群，包含 $n$ 个旋转和 $n$ 个反射，$|D_n| = 2n$。

例 7.1.4（立方体旋转群） 立方体的旋转对称群有24个元素：

• 恒等旋转：1个
• 绕对面中心轴旋转 $90°, 180°, 270°$：$3 \times 3 = 9$个
• 绕对边中点轴旋转 $180°$：6个
• 绕对角顶点轴旋转 $120°, 240°$：$4 \times 2 = 8$个

7.2 置换的循环分解

定义 7.2.1（轮换） 设 $\sigma \in S_n$，如果存在互不相同的元素 $i_1, i_2, \ldots, i_k$ 使得 $\sigma(i_1) = i_2, \sigma(i_2) = i_3, \ldots, \sigma(i_k) = i_1$ 则称 $\sigma$ 为**$k$-轮换**，记作 $(i_1\, i_2\, \cdots\, i_k)$。

定理 7.2.2（循环分解定理） 任意置换 $\sigma \in S_n$ 都可以唯一地表示为不相交轮换的乘积。

定义 7.2.3（轮换指标） 设 $G$ 是 $S_n$ 的子群，$G$ 的轮换指标定义为： $Z_G(x_1, x_2, \ldots, x_n) = \frac{1}{|G|} \sum_{g \in G} x_1^{c_1(g)} x_2^{c_2(g)} \cdots x_n^{c_n(g)}$ 其中 $c_k(g)$ 表示置换 $g$ 中 $k$-轮换的个数。

例 7.2.4（循环群 $C_4$ 的轮换指标） 设 $\rho = (1\, 2\, 3\, 4)$，则 $C_4 = \{e, \rho, \rho^2, \rho^3\}$。

因此： $Z_{C_4}(x_1, x_2, x_3, x_4) = \frac{1}{4}(x_1^4 + x_2^2 + 2x_4)$

例 7.2.5（二面体群 $D_4$ 的轮换指标） $D_4$ 包含 $C_4$ 的4个元素，加上4个反射：

• 关于对角顶点的反射：$(1\, 2)(3\, 4)$ 和 $(1\, 4)(2\, 3)$，对应 $x_2^2$
• 关于对边中点的反射：$(2\, 4)$ 和 $(1\, 3)$，对应 $x_1^2 x_2$

因此： $Z_{D_4}(x_1, x_2, x_3, x_4) = \frac{1}{8}(x_1^4 + 2x_1^2 x_2 + 3x_2^2 + 2x_4)$

7.3 群作用

定义 7.3.1（群作用） 设 $G$ 是群，$X$ 是非空集合。映射 $G \times X \to X$，记作 $g \cdot x$，满足：

1. $e \cdot x = x$ 对所有 $x \in X$ 成立；
2. $(gh) \cdot x = g \cdot (h \cdot x)$ 对所有 $g, h \in G$，$x \in X$ 成立。

定义 7.3.2（轨道） $x \in X$ 的轨道：$G \cdot x = \{g \cdot x : g \in G\}$

定义 7.3.3（稳定子） $x \in X$ 的稳定子：$G_x = \{g \in G : g \cdot x = x\}$

定义 7.3.4（不动点集） 设 $g \in G$，$g$ 的不动点集：$X^g = \{x \in X : g \cdot x = x\}$

定理 7.3.5（轨道-稳定子定理） $|G \cdot x| = \frac{|G|}{|G_x|}$

7.4 伯恩赛德引理

定理 7.4.1（Burnside’s Lemma） 设有限群 $G$ 作用于有限集 $X$，则轨道的个数为： $|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$

证明：考虑集合 $S = \{(g, x) \in G \times X : g \cdot x = x\}$。

方法1：$|S| = \sum_{g \in G} |X^g|$

方法2：$|S| = \sum_{x \in X} |G_x| = \sum_{O \in X/G} |O| \cdot \frac{|G|}{|O|} = |X/G| \cdot |G|$

因此 $|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$。

应用 7.4.2（二色项链问题） 用2种颜色给正 $n$ 边形的顶点染色，考虑旋转等价：

对 $g = \rho^k$，$f \in X^g$ 当且仅当 $f$ 在 $\rho^k$ 的每个轮换上取常值。$\rho^k$ 的轮换数为 $\gcd(n,k)$，因此 $|X^{\rho^k}| = 2^{\gcd(n,k)}$。

由伯恩赛德引理： $|X/C_n| = \frac{1}{n} \sum_{k=0}^{n-1} 2^{\gcd(n,k)} = \frac{1}{n} \sum_{d|n} \varphi\left(\frac{n}{d}\right) 2^d$

当 $n = 6$ 时：$|X/C_6| = \frac{1}{6}(64 + 2 + 4 + 8 + 4 + 2) = 14$

应用 7.4.3（立方体面染色） 用2种颜色给立方体的面染色，考虑旋转等价：

轨道数 = $\frac{1}{24}(64 + 48 + 48 + 32 + 48) = 10$

7.5 波利亚计数定理

定理 7.5.1（Pólya Enumeration Theorem） 用 $m$ 种颜色对 $n$ 个对象进行染色的不同方案数（在群 $G$ 作用下）等于轮换指标中代入 $x_k = m$： $|X/G| = Z_G(m, m, \ldots, m) = \frac{1}{|G|}\sum_{g \in G} m^{c(g)}$

立方体面染色的轮换指标： $Z_G = \frac{1}{24}(x_1^6 + 6x_1^2x_4 + 3x_1^2x_2^2 + 8x_3^2 + 6x_2^3)$

用 $m$ 种颜色染色的方案数： $\frac{1}{24}(m^6 + 3m^4 + 12m^3 + 8m^2)$

当 $m = 2$ 时：$\frac{240}{24} = 10$

当 $m = 3$ 时：$\frac{1368}{24} = 57$

7.6 加权形式的波利亚定理

定理 7.6.1（加权波利亚计数定理） 设 $a_k = \sum_{c \in C} w(c)^k$ 是颜色 $k$ 次幂的权重和，则模式清单为： $PI(G) = Z_G(a_1, a_2, \ldots, a_n)$

例 7.6.2（立方体二色染色，按颜色数生成）设颜色为红(r)和蓝(b)：

$PI = Z_G(r+b, r^2+b^2, r^3+b^3, r^4+b^4)$

展开后： $PI = r^6 + r^5b + 2r^4b^2 + 2r^3b^3 + 2r^2b^4 + rb^5 + b^6$

其中 $r^k b^{6-k}$ 的系数表示有 $k$ 个红面的不同染色方案数。验证：$1+1+2+2+2+1+1 = 10$。

8. 图论基础

8.1 基本定义

定义（图）：图 $G = (V, E)$，其中 $V$ 是顶点集，$E$ 是边集。

有向图：边是有序对 $(u, v)$ 无向图：边是无序对 $\{u, v\}$ 简单图：无自环、无重边

完全图 $K_n$：$n$ 个顶点，每对顶点间都有边。$|E(K_n)| = \binom{n}{2}$

超立方体 $Q_n$：顶点为 $\{0,1\}^n$，边连接汉明距离为 1 的顶点。$|V| = 2^n, |E| = n \cdot 2^{n-1}$

环图 $C_n$：$n$ 个顶点排成环 路径 $P_n$：$n$ 个顶点排成链

8.2 度数与握手定理

定义：顶点 $v$ 的度数 $\deg(v)$ 是与 $v$ 关联的边数。

定理 8.1（点握手定理）： $\sum_{v \in V} \deg(v) = 2|E|$

推论：奇度顶点的个数必为偶数。

定理 8.2（面握手定理，平面图）： $\sum_{f \in F} \deg(f) = 2|E|$

8.3 图的表示

邻接矩阵 $A$：$a_{ij} = 1$ 若 $v_i v_j \in E$，否则为 0。

关联矩阵 $B$（无向图）：$b_{ij} = 1$ 若顶点 $v_i$ 与边 $e_j$ 关联。

邻接表：为每个顶点维护邻居列表。

8.4 匹配与 Hall 定理

定义：匹配 $M \subseteq E$ 是边集，其中任意两条边无公共端点。 完美匹配：饱和所有顶点的匹配。

二分图：顶点集可划分为 $X, Y$，使得每条边一端在 $X$，一端在 $Y$。

定理 8.3（Hall 婚姻定理）：二分图 $G = (X, Y; E)$ 存在完美匹配当且仅当对所有 $S \subseteq X$，有 $|N(S)| \geq |S|$。

8.5 图同态与同构

图同态：映射 $\varphi: V_G \to V_H$ 保持邻接关系。

图同构：双射 $\varphi: V_G \to V_H$ 使得 $uv \in E_G \iff \varphi(u)\varphi(v) \in E_H$。

自同构群 $\text{Aut}(G)$：图 $G$ 到自身的所有同构构成的群。

8.6 欧拉路与哈密顿路

欧拉定理：连通图 $G$ 存在：

• 欧拉回路 $\iff$ 所有顶点度数为偶数
• 欧拉路（非回路）$\iff$ 恰有两个顶点度数为奇数

超立方体的哈密顿路：

定理 8.4：对 $n \geq 2$，超立方体 $Q_n$ 存在哈密顿回路。

证明（格雷码）：$n$ 位格雷码是 $\{0,1\}^n$ 的排列，相邻码字恰有一位不同。格雷码对应 $Q_n$ 中的哈密顿路，且首尾也相邻，形成哈密顿回路。

格雷码构造：$G_1 = (0, 1)$，$G_{n+1} = (0G_n, 1\overline{G_n})$

Dirac 定理：若 $G$ 是 $n \geq 3$ 个顶点的简单图，且 $\deg(v) \geq n/2$ 对所有 $v$ 成立，则 $G$ 存在哈密顿回路。

Ore 定理：若对任意不邻接的顶点对 $u, v$，有 $\deg(u) + \deg(v) \geq n$，则 $G$ 存在哈密顿回路。

8.7 单源最短路和最小生成树

Bellman-Ford 算法

• 处理负权边
• 时间复杂度：$O(|V| \cdot |E|)$
• 可检测负权圈

Dijkstra 算法

• 要求非负权边
• 时间复杂度：$O(|E| \log |V|)$（二叉堆）

Prim 算法（MST）

• 从单个顶点开始，每次添加连接已选集与未选集的最小权边
• 时间复杂度：$O(|E| \log |V|)$

Kruskal 算法（MST）

• 按权重排序边，依次添加不形成圈的边
• 使用并查集
• 时间复杂度：$O(|E| \log |V|)$

8.8 平面图

定义：图 $G$ 可画在平面上使边仅在端点处相交。

欧拉公式：连通平面图满足 $v - e + f = 2$。

边数上界：$e \leq 3v - 6$（$v \geq 3$）

判定定理：

1. Kuratowski 定理：$G$ 是平面图 $\iff$ $G$ 不含 $K_5$ 或 $K_{3,3}$ 的细分
2. Wagner 定理：$G$ 是平面图 $\iff$ $G$ 不含可收缩到 $K_5$ 或 $K_{3,3}$ 的子图
3. MacLane 定理：$G$ 是平面图 $\iff$ $G$ 的圈空间有基使每条边至多出现在两个基元素中

8.9 图染色

定义：图 $G$ 的**$k$-染色**是映射 $c: V \to \{1, \ldots, k\}$，使得相邻顶点颜色不同。

色数 $\chi(G)$：使 $G$ 为 $k$-可染的最小 $k$。

四色定理：任何平面图满足 $\chi(G) \leq 4$。

六色定理证明：对顶点数归纳。由 $e \leq 3v - 6$，存在顶点 $u$ 使 $\deg(u) \leq 5$。$G - u$ 可6-染色，$u$ 至多有5个邻居，至少一种颜色可用。

五色定理证明：类似六色定理，若5个邻居使用全部5种颜色，考虑颜色1和3（或2和4）的诱导子图，通过交换颜色释放一种颜色给 $u$。

8.10 树的性质

定义：无圈的连通图称为树。

等价定义：对 $n$ 个顶点的图 $G$，以下等价：

1. $G$ 是树（连通且无圈）
2. $G$ 无圈且有 $n-1$ 条边
3. $G$ 连通且有 $n-1$ 条边
4. $G$ 连通，但删除任意边后不再连通
5. $G$ 无圈，但添加任意边后产生唯一圈
6. $G$ 中任意两顶点间有唯一的路

Cayley 公式：$K_n$ 的生成树数目为 $\tau(K_n) = n^{n-2}$。

8.11 完美图

完美图（Perfect Graphs）是图论中最重要的图类之一，其核心思想是图的色数与团数之间存在简单的关系。完美图理论由Claude Berge在20世纪60年代提出，经历了几十年的发展，成为组合优化和算法图论的核心课题。

8.11.1 完美图的定义与历史背景

团数与色数

在引入完美图之前，我们需要回顾两个基本概念：

定义 8.11.1（团数） 图 $G$ 的团数（Clique Number），记为 $\omega(G)$，是指 $G$ 中最大完全子图（团）的顶点数。

定义 8.11.2（色数） 图 $G$ 的色数（Chromatic Number），记为 $\chi(G)$，是指对 $G$ 的顶点进行正常着色所需的最少颜色数，使得相邻顶点颜色不同。

引理 8.11.1 对任意图 $G$，都有 $\chi(G) \geq \omega(G)$。

证明：在一个团中，所有顶点两两相邻，因此必须使用不同的颜色。所以至少需要 $\omega(G)$ 种颜色。

通常情况下，$\chi(G)$ 可能严格大于 $\omega(G)$。例如，奇数长度的圈 $C_{2k+1}$（$k \geq 2$）满足 $\omega(C_{2k+1}) = 2$ 但 $\chi(C_{2k+1}) = 3$。

完美图的定义

定义 8.11.3（完美图，Berge 1961） 图 $G$ 称为完美图（Perfect Graph），如果对于 $G$ 的每一个诱导子图 $H$，都有：

$\chi(H) = \omega(H)$

换句话说，完美图要求色数和团数在每个诱导子图上都相等。

例子 8.11.1

• 完全图 $K_n$ 是完美图：$\chi(K_n) = \omega(K_n) = n$
• 空图 $\overline{K_n}$ 是完美图：$\chi(\overline{K_n}) = \omega(\overline{K_n}) = 1$
• 二分图是完美图：$\chi(G) = \omega(G) = 2$（若有边）或 $1$（若无边）
• 奇圈 $C_{2k+1}$（$k \geq 2$）不是完美图

Berge 的猜想

Claude Berge 提出了两个著名的猜想：

弱完美图猜想（Weak Perfect Graph Conjecture, WPGC）

一个图是完美图当且仅当其补图是完美图。

强完美图猜想（Strong Perfect Graph Conjecture, SPGC）

一个图是完美图当且仅当它不包含任何奇洞（odd hole）或奇反洞（odd antihole）作为诱导子图。

其中，奇洞是指长度至少为 5 的奇数长度的诱导圈 $C_{2k+1}$（$k \geq 2$）。奇反洞是指奇洞的补图。

这两个猜想引导了完美图理论几十年的发展。

8.11.2 完美图定理（PGT）

定理 8.11.1（完美图定理，Perfect Graph Theorem，Lovász 1972）

图 $G$ 是完美图当且仅当其补图 $\overline{G}$ 是完美图。

这是对弱完美图猜想的肯定回答。

Lovász 的强化形式

Lovász 实际上证明了一个更强的结果：

定理 8.11.2（Lovász 1972） 图 $G$ 是完美图当且仅当对 $G$ 的每个诱导子图 $H$，顶点数满足：

$|V(H)| \leq \alpha(H) \cdot \omega(H)$

其中 $\alpha(H)$ 是 $H$ 的独立数（最大独立集的大小）。

证明思路：

1. 定义复制（replication）操作：将某个顶点 $v$ 替换为一个团
2. 证明完美图在复制操作下保持完美性
3. 利用线性规划和多面体组合的方法建立对偶关系

完美图定理的一个重要推论是：补图保持完美性。这意味着完美图类在取补运算下是封闭的。

8.11.3 强完美图定理（SPGT）

强完美图猜想在 2002 年被 Chudnovsky、Robertson、Seymour 和 Thomas 证明，现称为强完美图定理。

定理 8.11.3（强完美图定理，Strong Perfect Graph Theorem，Chudnovsky et al. 2002）

图 $G$ 是完美图当且仅当 $G$ 和 $\overline{G}$ 都不包含长度至少为 5 的奇数长度的诱导圈（即不含奇洞和奇反洞）。

这个定理的证明极其复杂，发表于 Annals of Mathematics，是图论史上的里程碑成果。

结构定理

Chudnovsky 等人不仅证明了刻画定理，还建立了完美图的结构定理：

定理 8.11.4（完美图结构定理） 每个完美图都可以通过以下方式构造：

1. 基本完美图：二分图、二分图的补图、线图的二分图、线图的二分图的补图
2. 使用以下操作：不交并、连接和（join）、替换

这为完美图的算法研究奠定了基础。

8.11.4 重要的完美图类

完美图包含了许多在实际应用中非常重要的图类：

1. 二分图

定理 8.11.5 每个二分图都是完美图。

证明：设 $G$ 是二分图。对任意诱导子图 $H$：

• 若 $H$ 无边，则 $\chi(H) = \omega(H) = 1$
• 若 $H$ 有边，则 $\omega(H) = 2$，且由 Kőnig 定理，$\chi(H) = 2$

2. 弦图（Chordal Graphs）

定义 8.11.4 图 $G$ 是弦图，如果 $G$ 中每个长度至少为 4 的圈都有一条弦（连接非连续顶点的边）。

定理 8.11.6 每个弦图都是完美图。

弦图有完美的消去顺序（perfect elimination ordering），使得贪心着色算法最优。

3. 区间图（Interval Graphs）

定义 8.11.5 图 $G$ 是区间图，如果存在实数轴上的区间集合，使得顶点对应区间，边表示区间相交。

定理 8.11.7 每个区间图都是弦图，因此是完美图。

区间图在调度问题和生物信息学中有广泛应用。

4. 可比图（Comparability Graphs）

定义 8.11.6 图 $G$ 是可比图，如果存在一个偏序集 $P$，使得 $G$ 是 $P$ 的可比性图（边表示可比元素）。

定理 8.11.8 可比图是完美图。

可比图的补图称为不可比图（incomparability graphs），也是完美图。

5. 分裂图（Split Graphs）

定义 8.11.7 图 $G$ 是分裂图，如果顶点集可以划分为一个团和一个独立集。

定理 8.11.9 分裂图是完美图。

分裂图可以通过度序列刻画：度序列 $d_1 \geq d_2 \geq \cdots \geq d_n$ 对应分裂图当且仅当存在 $k$ 使得 $d_k \geq k-1$ 且 $d_{k+1} \leq k-1$。

完美图类之间的关系

        完美图
       /   |   \
   弦图  可比图  分裂图
    |           /
  区间图 ─────┘
    |
  树

8.11.5 算法意义

完美图的算法意义由 Grötschel、Lovász 和 Schrijver 在 1984 年的开创性工作奠定。

定理 8.11.10（Grötschel-Lovász-Schrijver 1984）

对于完美图，以下问题可以在多项式时间内求解：

1. 计算色数 $\chi(G)$
2. 计算团数 $\omega(G)$
3. 计算独立数 $\alpha(G)$
4. 计算团覆盖数 $\overline{\chi}(G)$

这些算法基于椭球方法和半定规划，虽然理论上是多项式时间，但实际效率不高。

着色算法

定理 8.11.11 对于完美图，存在多项式时间算法找到：

• 最优着色
• 最大团
• 最大独立集
• 最小团覆盖

这些结果与完美图定理相结合，说明了完美图类在组合优化中的重要性。

实际应用

完美图理论的应用包括：

• 排序问题：可比图的应用
• 资源分配：区间图的应用
• 调度问题：弦图和区间图的应用
• 通信网络：完美图的应用

8.12 竞赛图

竞赛图（Tournament）是有向图的重要子类，在竞赛理论、社会选择理论和生物信息学中有广泛应用。

8.12.1 定义与基本性质

竞赛图的定义

定义 8.12.1 竞赛图（Tournament）是指完全有向图，即对于每对不同的顶点 $u, v$，恰有 $u \to v$ 或 $v \to u$ 之一作为有向边。

等价地，竞赛图是给完全图 $K_n$ 的每条边指定一个方向的产物。

顶点数与边数

• 竞赛图有 $n$ 个顶点和 $\binom{n}{2} = \frac{n(n-1)}{2}$ 条有向边

得分序列

定义 8.12.2 顶点 $v$ 的得分（score）$s(v)$ 是 $v$ 的出度，即 $s(v) = d^+(v)$。

定义 8.12.3 竞赛图的得分序列（score sequence）是所有顶点得分按非降序排列的序列 $(s_1, s_2, \ldots, s_n)$，其中 $s_1 \leq s_2 \leq \cdots \leq s_n$。

引理 8.12.1 对 $n$ 个顶点的竞赛图，得分满足： $\sum_{i=1}^n s_i = \binom{n}{2} = \frac{n(n-1)}{2}$

证明：每条有向边恰好贡献一个出度。

引理 8.12.2 对每个顶点 $v$，有 $0 \leq s(v) \leq n-1$。

正则竞赛图

定义 8.12.4 竞赛图 $T$ 称为正则的（Regular），如果所有顶点的得分相同。

定理 8.12.1 $n$ 个顶点的正则竞赛图存在的充要条件是 $n$ 为奇数。

证明：

• 若 $T$ 正则，则每个顶点得分 $s = \frac{n-1}{2}$，所以 $n$ 必须为奇数
• 若 $n = 2k+1$ 为奇数，可以构造循环竞赛图：顶点 $0, 1, \ldots, 2k$，边 $i \to j$ 当且仅当 $j - i \pmod n \in \{1, 2, \ldots, k\}$

8.12.2 Redei 定理

定理 8.12.2（Redei 定理，1934）

每个竞赛图都包含一条哈密顿路（Hamiltonian path），即经过每个顶点恰好一次的有向路。

证明（归纳法）：

基础：$n = 1, 2$ 时显然成立。

归纳步骤：设 $T$ 是有 $n$ 个顶点的竞赛图，$v$ 是任意顶点。考虑 $T - v$，由归纳假设，$T - v$ 有哈密顿路 $v_1 \to v_2 \to \cdots \to v_{n-1}$。

考虑 $v$ 与这条路的关系：

1. 若存在 $i$ 使得 $v_i \to v$ 且 $v \to v_{i+1}$，则可插入 $v$：$v_1 \to \cdots \to v_i \to v \to v_{i+1} \to \cdots \to v_{n-1}$
2. 若对所有 $i$ 都有 $v \to v_i$，则 $v \to v_1 \to \cdots \to v_{n-1}$
3. 若对所有 $i$ 都有 $v_i \to v$，则 $v_1 \to \cdots \to v_{n-1} \to v$

因此 $T$ 也有哈密顿路。

唯一性：哈密顿路不一定唯一。例如，传递竞赛图有唯一的哈密顿路。

8.12.3 Moon 定理和 Camion 定理

强连通竞赛图

定义 8.12.5 竞赛图 $T$ 是强连通的（Strongly Connected），如果对任意两个顶点 $u, v$，都存在从 $u$ 到 $v$ 的有向路。

定理 8.12.3 竞赛图 $T$ 是强连通的当且仅当 $T$ 包含哈密顿回路。

证明：

• 哈密顿回路的存在性显然蕴含强连通性
• 反之，由 Redei 定理和强连通性可构造哈密顿回路

Camion 定理

定理 8.12.4（Camion 定理，1959）

强连通竞赛图包含哈密顿回路。

这是 Redei 定理的加强版。

Moon 定理

定理 8.12.5（Moon 定理，1963）

设 $T$ 是强连通的 $n$ 顶点竞赛图，$3 \leq k \leq n$。则 $T$ 包含长度为 $k$ 的有向圈。

换句话说，强连通竞赛图包含所有可能长度的有向圈！

证明概要：

1. 由 Camion 定理，存在长度为 $n$ 的圈（哈密顿回路）
2. 通过删除适当顶点，可以构造所有较短长度的圈

推论 8.12.1 强连通竞赛图是顶点泛圈的（Vertex-pancyclic）：通过每个顶点的所有长度圈都存在。

8.12.4 得分序列与 Landau 定理

传递竞赛图

定义 8.12.6 竞赛图 $T$ 是传递的（Transitive），如果 $u \to v$ 且 $v \to w$ 蕴含 $u \to w$。

定理 8.12.6 传递竞赛图的等价刻画：

1. $T$ 是传递竞赛图
2. $T$ 无有向圈
3. $T$ 的得分序列是 $(0, 1, 2, \ldots, n-1)$
4. 顶点可以排序使得边都从编号小的指向编号大的

传递竞赛图对应于全序关系。

Landau 定理

定理 8.12.7（Landau 定理，1953）

非负整数序列 $(s_1, s_2, \ldots, s_n)$ 是某个竞赛图的得分序列当且仅当：

1. $\sum_{i=1}^n s_i = \binom{n}{2}$
2. 对所有 $k = 1, 2, \ldots, n$：$\sum_{i=1}^k s_i \geq \binom{k}{2}$

且等号成立当且仅当对应的子竞赛图是传递的。

这是 Erdős-Gallai 定理在竞赛图中的类比。

证明思路：

• 必要性：前 $k$ 个顶点的诱导子图有 $\binom{k}{2}$ 条边，内部出度之和恰好为 $\binom{k}{2}$
• 充分性：使用构造性证明或网络流方法

算法：给定得分序列，可以在多项式时间内构造对应的竞赛图。

8.12.5 王（King）和皇帝

王的定义

定义 8.12.7 顶点 $v$ 称为王（King），如果从 $v$ 到任意其他顶点 $u$ 的有向距离至多为 2，即存在 $v \to u$ 或存在 $w$ 使得 $v \to w \to u$。

定理 8.12.8（Landau 定理的推论）

每个竞赛图都有至少一个王。

证明：设 $v$ 是得分最大的顶点。对任意其他顶点 $u$：

• 若 $v \to u$，则距离为 1
• 若 $u \to v$，由于 $s(v) \geq s(u)$，$v$ 必须”击败”某个 $w$ 而 $u$ “败给” $w$，即 $v \to w$ 且 $w \to u$（或类似），距离为 2

定理 8.12.9 得分最大的顶点一定是王。

多个王的存在

定理 8.12.10

• 若竞赛图有唯一的王，则该王击败所有其他顶点（即出度为 $n-1$）
• 若竞赛图没有出度为 $n-1$ 的顶点，则至少有 3 个王

皇帝

定义 8.12.8 顶点 $v$ 称为皇帝（Emperor），如果 $v$ 击败所有其他顶点（即出度 $s(v) = n-1$）。

显然，皇帝是唯一的王（如果存在）。

8.12.6 支配数

支配集的定义

定义 8.12.9 顶点子集 $D$ 称为支配集（Dominating Set），如果对每个顶点 $v \notin D$，存在 $u \in D$ 使得 $u \to v$。

定义 8.12.10 竞赛图 $T$ 的支配数（Domination Number）$\gamma(T)$ 是最小支配集的大小。

支配数的上界

定理 8.12.11 对任意 $n$ 顶点的竞赛图 $T$，有： $\gamma(T) \leq \lceil \log_2 n \rceil$

证明：归纳构造。每次选择一个支配尽可能多未支配顶点的顶点。

定理 8.12.12 对任意 $n$ 顶点的竞赛图 $T$，有： $\gamma(T) \leq \frac{n}{2}$

这是更紧的上界。

下界与极值问题

定理 8.12.13 存在竞赛图使得 $\gamma(T) \geq c \cdot \log n$（对某个常数 $c$）。

定理 8.12.14（Erdős）

对随机竞赛图，$\gamma(T) = \Theta(\log n)$ 以高概率成立。

这表明 $\log n$ 是支配数的典型值。

王与支配集的关系

引理 8.12.3 若 $v$ 是王，则 $\{v\}$ 是 2-步支配集（距离至多为 2）。

定理 8.12.15 竞赛图的所有王的集合本身构成一个支配集。

9. 组合代数

组合代数是组合数学中运用代数工具（特别是线性代数、多项式理论和群论）解决组合问题的重要分支。本章将探讨一系列经典的代数组合问题，从奇镇偶镇问题到设计理论，展示代数方法的强大威力。

9.1 奇镇与偶镇问题

9.1.1 奇镇问题描述

问题设定：假设有一个小镇，镇上有 $n$ 个居民。每个居民组织一个俱乐部，俱乐部成员是这 $n$ 个居民的子集。规定：任意两个不同俱乐部的交集都包含奇数个成员。问：最多可以有多少个俱乐部？

定理 9.1（奇镇上界定理）：在满足上述条件的奇镇中，俱乐部数量不超过 $n$。

9.1.2 线性代数证明

证明：将每个俱乐部 $A_i$ 表示为 $\mathbb{F}_2^n$ 中的特征向量 $\mathbf{v}_i$，其中第 $j$ 个分量为 1 当且仅当第 $j$ 个居民在俱乐部 $A_i$ 中。

任意两个俱乐部的交集大小为： $|A_i \cap A_j| = \mathbf{v}_i \cdot \mathbf{v}_j = \sum_{k=1}^{n} v_{i,k} v_{j,k}$

条件表明：对于 $i \neq j$，$\mathbf{v}_i \cdot \mathbf{v}_j \equiv 1 \pmod{2}$。

关键引理：这些向量在 $\mathbb{F}_2$ 上线性无关。

因此 $m \leq n$。 $\square$

9.1.3 偶镇问题描述与解

问题设定：偶镇中规定任意两个不同俱乐部的交集都包含偶数个成员。问：最多可以有多少个俱乐部？

定理 9.2（偶镇上界定理）：偶镇中俱乐部数量的最大值为 $2^{\lfloor n/2 \rfloor}$。

9.2 多项式空间方法

9.2.1 Larman-Rogers-Seidel定理

定理 9.5（Larman-Rogers-Seidel, 1977）：设 $S \subset \mathbb{R}^n$ 是有限点集，满足任意两点距离为 $a$ 或 $b$（$a \neq b$），则 $|S| \leq \frac{(n+1)(n+4)}{2}$。

9.2.2 Deza-Frankl-Singhi定理

定理 9.7（Deza-Frankl-Singhi）：设 $\mathcal{F}$ 是 $[n]$ 的 $k$-子集族，若任意两个集合的交大小属于集合 $L = \{\ell_1, \ldots, \ell_s\}$，则： $|\mathcal{F}| \leq \binom{n}{s}$

9.3 相交的集合族

9.3.1 Fisher不等式

定理 9.8（Fisher不等式）：设 $\mathcal{F} = \{A_1, \ldots, A_m\}$ 是 $[n]$ 的子集族，满足每个 $|A_i| = k$，任意两个不同集合的交 $|A_i \cap A_j| = \lambda$（常数）。若 $0 < \lambda < k$，则 $m \leq n$。