图的基本概念、路与回路

本节导读

图论在大纲里占两个单元。本节讲第一个：图的基本概念与性质、图的代数表示、途径与路、欧拉图、汉密尔顿图、最短路径、连通性和有向图；下一节讲树、平面图和着色。

图论题的特点是「概念多、结论硬」：握手定理、欧拉图的判定、汉密尔顿图的必要条件和充分条件、Whitney 不等式，都要能准确说出并会用。常见的考法是用握手定理求顶点数或边数、判断一个图能不能一笔画、证明某个图不是汉密尔顿图、手工跑一遍 Dijkstra 算法。

图的基本概念

图 $G = \langle V, E \rangle$G=⟨V,E⟩ 由顶点集 V 和边集 E 组成，边无方向的叫无向图，有方向的叫有向图。顶点数 n 叫图的阶，边数记作 m。两点间多于一条边叫平行边，两端是同一点的边叫环，既无平行边又无环的图叫简单图。

顶点 v 关联的边数叫 v 的度 $\deg(v)$deg(v)，环算 2 度。握手定理：所有顶点的度数之和等于边数的 2 倍，$\sum \deg(v) = 2m$∑deg(v)=2m；推论是奇度顶点的个数一定是偶数。有向图里，所有顶点的出度之和等于入度之和，都等于 m。例如一个无向图有 12 条边，其中 6 个顶点是 3 度、其余都是 2 度：$2 \times 12 = 24 = 6 \times 3 + 2k$2×12=24=6×3+2k，得 k = 3，共 9 个顶点。

几类常见的图：完全图 $K_n$Kn​（任意两点都相邻，共 $\frac{n(n-1)}{2}$2n(n−1)​ 条边）、完全二部图 $K_{m,n}$Km,n​（两部分之间全连，共 mn 条边）、k 正则图（每点都是 k 度，共 $\frac{nk}{2}$2nk​ 条边）。G 的补图是用 $K_n$Kn​ 的边去掉 G 的边得到的图。

图的代数表示

简单无向图的邻接矩阵 A：$v_i$vi​、$v_j$vj​ 相邻则 $a_{ij} = 1$aij​=1，否则为 0。它是对称矩阵，主对角线全为 0，第 i 行之和就是 $\deg(v_i)$deg(vi​)。有向图的邻接矩阵不一定对称，行和是出度，列和是入度。关联矩阵是 n 行 m 列的矩阵，记录每个顶点与每条边是否关联。

邻接矩阵最重要的性质：$A^k$Ak 的第 i 行第 j 列，等于从 $v_i$vi​ 到 $v_j$vj​ 长度为 k 的途径条数。特别地，$A^2$A2 主对角线上的数就是各顶点的度。

途径、迹、路与回路

名称	要求	闭合的叫法
途径	顶点和边都可以重复	闭途径
迹	边不重复，顶点可以重复	闭迹
路	顶点不重复（边自然也不重复）	回路（圈）

不同教材叫法不同，有的把迹叫「简单通路」、把路叫「初级通路」，答题时看清题目的定义。一个有用的结论：从 u 到 v 有途径，就一定有路，而且路的长度不超过 n − 1。

欧拉图

经过图中每条边恰好一次的闭迹叫欧拉闭迹（欧拉环游），有欧拉闭迹的图叫欧拉图；经过每条边恰好一次、但不闭合的迹叫欧拉迹。判定定理很简洁：

• 连通的无向图有欧拉闭迹，当且仅当每个顶点的度都是偶数；
• 连通的无向图有欧拉迹（不闭合），当且仅当恰好有两个奇度顶点，欧拉迹从其中一个出发、到另一个结束；
• 有向图有欧拉闭迹，当且仅当它连通且每个顶点的入度等于出度。

这就是「一笔画」问题：哥尼斯堡七桥图有 4 个奇度顶点，所以不能一笔画出。实际找欧拉闭迹可以用 Fleury 算法，要点是「除非别无选择，不走桥」。

汉密尔顿图

经过每个顶点恰好一次的回路叫汉密尔顿回路，有它的图叫汉密尔顿图。与欧拉图不同，汉密尔顿图没有简洁的充要条件，只能用必要条件否定、用充分条件肯定：

• 必要条件：对顶点集的任意非空真子集 S，从 G 中删去 S 后，连通分支数不超过 S 的元素个数。违反它的图一定不是汉密尔顿图。
• 充分条件（Ore）：n（n ≥ 3）阶简单图中，任意两个不相邻顶点的度数之和都不小于 n，则 G 是汉密尔顿图。特例（Dirac）：每个顶点的度都不小于 $\frac{n}{2}$2n​。

例如 $K_n$Kn​（n ≥ 3）是汉密尔顿图；完全二部图 $K_{m,n}$Km,n​ 当且仅当 $m = n \ge 2$m=n≥2 时是汉密尔顿图。

最短路径

带权图中，路上各边权之和叫路的长度。边权非负时求单源最短路径用 Dijkstra 算法：起点的距离设为 0，其余设为无穷大；每一步从「还没确定」的顶点里选距离最小的一个，把它定下来，再用它去更新相邻顶点的距离（经过它更近就改小）；重复到终点被定下来为止。手工做题时建议列表，每一行写出这一步定下的顶点和各点当前的距离。边权有负数时 Dijkstra 算法不适用。

连通性

无向图任意两点之间都有路，就叫连通图，否则分成若干连通分支。删去后使连通分支数增加的顶点叫割点，这样的边叫割边（桥）；使图不连通所需删去的最少顶点数叫点连通度 $\kappa(G)$κ(G)，最少边数叫边连通度 $\lambda(G)$λ(G)。Whitney 不等式：$\kappa(G) \le \lambda(G) \le \delta(G)$κ(G)≤λ(G)≤δ(G)，其中 $\delta(G)$δ(G) 是最小度。另外，n 阶简单图的边数多于 $\frac{(n-1)(n-2)}{2}$2(n−1)(n−2)​ 时一定连通。

有向图的连通性分三级：任意两点互相可达叫强连通；任意两点至少一个方向可达叫单向连通；把方向去掉后连通叫弱连通。强连通图一定单向连通，单向连通图一定弱连通。

易错提醒

• ❌ 用握手定理时把环算作 1 度。✅ 环给它所在的顶点贡献 2 度。因为一条环的两个端点是同一个顶点。

• ❌ 只要每个顶点度数是偶数，就一定有欧拉闭迹。✅ 还要求图连通（去掉孤立点后）。因为两个分开的圈各自度数都是偶数，却不能一笔走完。

• ❌ 找不到汉密尔顿回路就说「不是汉密尔顿图」。✅ 要用必要条件（删去 S 后分支数大于 S 的元素个数）给出证明。因为「没找到」不等于「不存在」。

• ❌ 把 Ore 条件当成充要条件。✅ 它只是充分条件。因为长度为 5 的圈是汉密尔顿图，却不满足 Ore 条件。

• ❌ $A^k$Ak 的元素数的是「路」的条数。✅ 数的是「途径」的条数，顶点和边都可以重复。因为矩阵乘法把所有中间顶点的组合都算了进去。

例题精讲

例题 1（填空）

无向简单图 G 有 16 条边，3 度与 4 度的顶点各有 4 个，其余顶点的度数都小于 3。G 至少有几个顶点？

答案：度数之和是 $2 \times 16 = 32$2×16=32，8 个顶点已经贡献 $3 \times 4 + 4 \times 4 = 28$3×4+4×4=28，还差 4。其余顶点每个至多 2 度，至少还要 2 个顶点，所以 G 至少有 10 个顶点。

例题 2（计算）

带权无向图的边为：s–a 权 4，s–b 权 1，b–a 权 2，a–c 权 1，b–c 权 5，c–t 权 3，a–t 权 6。用 Dijkstra 算法求 s 到 t 的最短路径。

答题要点示范：

步骤	定下的顶点	a	b	c	t
初始	s（0）	4	1	∞	∞
1	b（1）	3	—	6	∞
2	a（3）	—	—	4	9
3	c（4）	—	—	—	7
4	t（7）	—	—	—	—

最短距离为 7，路径 s → b → a → c → t。

点评：第 1 步经过 b 到 a 只要 3，比直达的 4 更短，这就是「更新」的意思；每一步都只定下当前距离最小的那个顶点。

例题 3（证明推导）

证明完全二部图 $K_{2,3}$K2,3​ 不是汉密尔顿图。

答题要点示范：取 S 为含 2 个顶点的那一部分，删去 S 后剩下 3 个孤立顶点，连通分支数 3 大于 S 的元素个数 2，违反汉密尔顿图的必要条件，所以 $K_{2,3}$K2,3​ 不是汉密尔顿图。

点评：证明「不是」汉密尔顿图，几乎都靠这个必要条件，关键是挑一个合适的 S。

本节小结

• 握手定理：度数和等于 2m，奇度顶点有偶数个；有向图出度和等于入度和。
• 邻接矩阵 $A^k$Ak 的元素是长度为 k 的途径条数；途径、迹、路依次加强要求。
• 欧拉图：连通且全是偶度；恰有两个奇度顶点时有欧拉迹。
• 汉密尔顿图：用「删 S 后分支数不超过 S 的元素个数」否定，用 Ore 或 Dirac 条件肯定。
• Dijkstra 算法要求边权非负；$\kappa \le \lambda \le \delta$κ≤λ≤δ；有向图分强连通、单向连通、弱连通。