树、平面图与图的着色

本节导读

这一节是图论的第二个单元，大纲列了七条：树的定义及等价条件、支撑树的计数、森林、最短树、平面图与极大平面图、对偶图、色数与色多项式。

这一块的计算题很多：按度数求树叶个数、用 Cayley 公式或矩阵树定理数支撑树、用 Kruskal 算法求最短树、用欧拉公式求面数、求色多项式；证明题的代表是「证明 $K_5$K5​ 或 $K_{3,3}$K3,3​ 不是平面图」。学完你应该能把这些计算一步不漏地写出来，并能用欧拉公式的推论完成非平面图的证明。

树及其等价条件

连通而且没有回路的无向图叫树，度为 1 的顶点叫树叶。对 n 阶无向图 G（m 条边），下面六条互相等价：

1. G 连通且无回路；
2. G 无回路且 $m = n - 1$m=n−1；
3. G 连通且 $m = n - 1$m=n−1；
4. G 无回路，但任意添一条边就恰好得到一条回路；
5. G 连通，且每条边都是桥；
6. G 的任意两个顶点之间恰有一条路。

n ≥ 2 的树至少有两片树叶。已知非叶顶点的度数求树叶数，用握手定理：度数之和 = 2(n − 1)。每个连通分支都是树的图叫森林，k 棵树组成的森林有 $m = n - k$m=n−k 条边。

连通图 G 的一个子图如果是树、又包含 G 的全部顶点，就叫 G 的支撑树（生成树）。支撑树有 n − 1 条边，G 中不在支撑树上的 m − n + 1 条边叫余树边。

支撑树的计数

两个常用结论。Cayley 公式：完全图 $K_n$Kn​ 有 $n^{n-2}$nn−2 棵支撑树，例如 $K_4$K4​ 有 16 棵。矩阵树定理：令 $L = D - A$L=D−A（D 是度数对角矩阵，A 是邻接矩阵），删去 L 的任意第 i 行和第 i 列，剩下矩阵的行列式就是 G 的支撑树棵数。

例如 $K_4$K4​ 去掉一条边（顶点 1、2 不相邻）：L 的对角线是 2、2、3、3，删去第 1 行第 1 列，剩下的三阶矩阵为

$\begin{pmatrix} 2 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{pmatrix}$​2−1−1​−13−1​−1−13​​

它的行列式是 8，所以这个图有 8 棵支撑树。另外，n 个顶点的圈恰有 n 棵支撑树（去掉任意一条边）。

最短树

带权连通图中，权和最小的支撑树叫最短树（最小生成树）。两种求法：

• Kruskal 算法（避圈法）：把边按权从小到大排好，依次考察，不与已选的边构成回路就选上，选够 n − 1 条为止；
• Prim 算法：从任一顶点出发，每次在「已选顶点」与「未选顶点」之间的边里挑权最小的一条加进来。

边权互不相同时最短树唯一；有相同的权时最短树可能不唯一，但最小的权和是确定的。

平面图与欧拉公式

能画在平面上、边与边只在端点相交的图叫平面图。平面图把平面分成若干个面，包括一个无界的外部面。围成一个面的边数叫这个面的度（桥在面的边界上算两次），所有面的度数之和等于 2m。

欧拉公式：连通平面图满足 $n - m + f = 2$n−m+f=2；有 k 个连通分支时，$n - m + f = k + 1$n−m+f=k+1。由它推出两个常用的不等式（简单连通平面图，n ≥ 3）：

条件	边数上界	用途
一般的简单平面图	$m \le 3n - 6$m≤3n−6	$K_5$K5​ 有 10 条边，超过 $3 \times 5 - 6 = 9$3×5−6=9，不是平面图
不含三角形（如二部图）	$m \le 2n - 4$m≤2n−4	$K_{3,3}$K3,3​ 有 9 条边，超过 $2 \times 6 - 4 = 8$2×6−4=8，不是平面图

这两个不等式只是必要条件：违反就一定不是平面图，满足了却不一定是。判断平面图的充要条件是 Kuratowski 定理：G 是平面图，当且仅当它不含与 $K_5$K5​ 或 $K_{3,3}$K3,3​ 同胚的子图。

在简单平面图上，再添任何一条边就不再是平面图，这样的图叫极大平面图。n ≥ 3 的极大平面图每个面都是三角形，边数正好是 $3n - 6$3n−6，面数是 $2n - 4$2n−4。

对偶图

给连通平面图 G 的每个面放一个顶点，G 的每条边 e 都画一条穿过 e 的边，连接 e 两侧的面所对应的顶点（e 是桥时得到一个环），得到的图叫 G 的对偶图 $G^{*}$G∗。它们的数量关系是：$G^{*}$G∗ 的顶点数等于 G 的面数，边数相同，$G^{*}$G∗ 的面数等于 G 的顶点数；$G^{*}$G∗ 中顶点的度等于 G 中对应面的度。对偶图总是连通的。给平面图的面着色，相邻面不同色，等价于给它的对偶图的顶点着色。

色数与色多项式

给顶点着色，要求相邻顶点颜色不同，所需的最少颜色数叫色数 $\chi(G)$χ(G)。几个结论：$\chi(K_n) = n$χ(Kn​)=n；有边的图 $\chi(G) = 2$χ(G)=2 当且仅当它是二部图，也就是没有奇数长的回路；奇数长的圈色数是 3；四色定理说任何平面图的色数不超过 4。着色问题的典型应用是排考场：每门课是一个顶点，有共同考生的两门课连边，色数就是最少需要的考试时段数。

色多项式 $P(G, k)$P(G,k) 是用至多 k 种颜色对 G 正常着色的方法数。常用结果：

图	色多项式
n 个孤立点	$k^n$kn
完全图 $K_n$Kn​	$k(k-1)(k-2)\cdots(k-n+1)$k(k−1)(k−2)⋯(k−n+1)
n 个顶点的树	$k(k-1)^{n-1}$k(k−1)n−1
n 个顶点的圈 $C_n$Cn​	$(k-1)^n + (-1)^n (k-1)$(k−1)n+(−1)n(k−1)

一般的图用删收公式递推：$P(G, k) = P(G - e, k) - P(G \cdot e, k)$P(G,k)=P(G−e,k)−P(G⋅e,k)，$G - e$G−e 是删去边 e，$G \cdot e$G⋅e 是把 e 收缩成一个点。比如 $C_4$C4​ 在 k = 3 时有 $2^4 + 2 = 18$24+2=18 种着色。使 $P(G, k) \gt 0$P(G,k)>0 的最小正整数 k 就是色数。

易错提醒

• ❌ n 个顶点、n − 1 条边的图就是树。✅ 还要加上「连通」或「无回路」中的一条。因为一个三角形加一个孤立点也是 4 个顶点 3 条边。

• ❌ 不连通的平面图也用 $n - m + f = 2$n−m+f=2。✅ 有 k 个连通分支时是 $n - m + f = k + 1$n−m+f=k+1。因为外部面被各个分支共用，只算一次。

• ❌ 满足 $m \le 3n - 6$m≤3n−6 就是平面图。✅ 它只是必要条件。因为 $K_{3,3}$K3,3​ 的 9 条边小于 12，却不是平面图。

• ❌ 计算面的度时，桥只算一次。✅ 桥的两侧是同一个面，要算两次。因为沿面的边界走一圈会经过桥两次。

• ❌ 把树的色多项式套到圈上。✅ 圈要用 $(k-1)^n + (-1)^n (k-1)$(k−1)n+(−1)n(k−1)。因为圈首尾两个顶点也相邻，比树多一个约束。

例题精讲

例题 1（填空）

一棵树有 2 个 3 度顶点、1 个 4 度顶点，其余都是树叶。它有几片树叶？

答案：设树叶有 x 片，顶点数 $n = 3 + x$n=3+x。由握手定理 $3 \times 2 + 4 + x = 2(n - 1) = 2(2 + x)$3×2+4+x=2(n−1)=2(2+x)，即 $10 + x = 4 + 2x$10+x=4+2x，得 x = 6。

例题 2（计算）

带权图 G 的边为：ab 权 4，ac 权 3，bc 权 2，bd 权 5，cd 权 6，ce 权 7，de 权 1，df 权 8，ef 权 9。用 Kruskal 算法求最短树的权。

答题要点示范：按权排序依次考察：de（1）选；bc（2）选；ac（3）选；ab（4）与 a、c、b 成回路，弃；bd（5）选，把 {a, b, c} 与 {d, e} 连起来；cd（6）、ce（7）成回路，弃；df（8）选，此时已有 5 条边。最短树由 de、bc、ac、bd、df 组成，权为 $1 + 2 + 3 + 5 + 8 = 19$1+2+3+5+8=19。

点评：每弃一条边都写一句「成回路」，阅卷时一眼就能看出算法用对了。

例题 3（证明推导）

证明 $K_{3,3}$K3,3​ 不是平面图。

答题要点示范：$K_{3,3}$K3,3​ 中 n = 6，m = 9。假设它是平面图。它是二部图，没有三角形，每个面的度至少是 4，所以 $4f \le 2m = 18$4f≤2m=18，$f \le 4.5$f≤4.5。而由欧拉公式 $f = 2 - n + m = 5$f=2−n+m=5，矛盾。所以 $K_{3,3}$K3,3​ 不是平面图。

点评：也可以直接用推论 $m \le 2n - 4$m≤2n−4：9 大于 8。写出「每个面的度至少是 4」这一步，说明你知道推论是怎么来的。

本节小结

• 树的六个等价条件记住「连通、无回路、n − 1 条边」三者任取两个；树叶数用握手定理求。
• $K_n$Kn​ 有 $n^{n-2}$nn−2 棵支撑树；一般图用矩阵树定理，删去 $D - A$D−A 的一行一列求行列式。
• 最短树：Kruskal 从小到大避圈，Prim 从一个点向外长。
• 欧拉公式 $n - m + f = 2$n−m+f=2；推论 $m \le 3n - 6$m≤3n−6、无三角形时 $m \le 2n - 4$m≤2n−4，用来否定平面性。
• 对偶图：点与面互换、边数不变；色数看奇圈与二部性，色多项式用公式或删收递推。