返回：0100 离散数学课程总目录 · 上一章：0112 支配、覆盖、独立与匹配 · 下一章：0114 代数结构基础

1、学习目标

本章是图论部分的收束：把欧拉图、哈密顿图、最短路、最小生成树和匹配组合起来解决带权图问题。

重点只抓两类模型：

1
2
中国邮递员问题：边必须都走到，目标是最短闭迹。
货郎担问题 / TSP：点必须都走到，目标是最短哈密顿回路。

记忆口令：邮递员走边，货郎走点。邮递员问题可以转成最短路 + 最小权完美匹配 + 欧拉回路；货郎担问题一般是难解问题，常用近似算法或动态规划。

2、带权图与应用问题建模

带权图记为：

1
G=<V,E,W>,  W:E -> R

其中 W(e) 是边 e 的权，可以表示距离、时间、费用、容量损耗等。

常见题目翻译：

真实问题 图论模型 关键对象
邮递员走完所有街道 连通带权图中最短闭迹，覆盖全部边 欧拉回路、奇度顶点、匹配
旅行商访问所有城市 带权完全图中最短哈密顿回路 哈密顿回路、近似算法
路线补边 / 重复边 让所有顶点变成偶度 最短路、最小权完美匹配
小规模求精确最优 枚举所有候选回路 (n-1)!/2 条不同回路

3、中国邮递员问题

目标：

1
2
在带权连通图 G 中找一条闭迹 Γ，
使 Γ 经过每条边至少一次，并且 W(Γ) 最小。

如果 G 已经是欧拉图，则：

1
2
3
所有顶点度数均为偶数
=> 任意欧拉回路都是最优投递路线
=> 最优权 = 原图所有边权之和

如果 G 不是欧拉图，就要把若干边重复一次，使所有奇度顶点变成偶度。

标准算法

1
2
3
4
5
6
1. 找出 G 中所有奇度顶点，记为 V'。
2. 用 Dijkstra 等算法求 V' 中任意两点之间的最短路径长度。
3. 以 V' 为顶点，构造带权完全图 K，边权取两点间最短路长度。
4. 在 K 中求最小权完美匹配 M。
5. 在原图 G 中，把 M 对应的最短路径上的边重复一次，得到 G*。
6. G* 中所有顶点都是偶度，求 G* 的欧拉回路，即最优投递路线。

最优权的计算公式：

1
W(最优投递路线) = W(G 的全部边) + W(奇度顶点最小权完美匹配)

为什么只看奇度顶点？闭迹中每次进入一个顶点也要离开一个顶点，所以最终每个顶点被使用的边次数必须是偶数。原图中偶度顶点不用补，奇度顶点必须两两配对补成偶度。

做题模板

1
2
3
4
5
第一步：列奇度顶点集 V'。
第二步：列 V' 中两两最短路和权。
第三步：比较所有完美匹配的总权，取最小者。
第四步：说明重复哪些最短路径。
第五步：给出最优权；若题目要求路线，再写一条欧拉回路。

容易错的点：

1
2
3
4
1. 匹配边的权不是原图中一条边的权，而是两点之间最短路径的权。
2. 最小权匹配可能不唯一，只要总权最小都可以。
3. 最后路线不是哈密顿回路，顶点和边都可以重复。
4. 写路线时要检查每条原边至少经过一次，重复边正好来自匹配对应短路。

4、货郎担问题

目标：

1
2
给定带权完全图 G=<V,E,W>，
求经过每个顶点恰好一次并回到起点的最短哈密顿回路。

货郎担问题又叫旅行商问题，简称 TSP。它和中国邮递员问题的核心差别是：

1
2
中国邮递员：要求覆盖边，允许重复顶点和边，是易解问题。
货郎担：要求覆盖顶点且每个顶点只访问一次，一般是难解问题。

复杂度要点：

1
2
3
穷举法需要检查 (n-1)!/2 条不同哈密顿回路。
动态规划 Held-Karp 思路可做到 O(n^2 * 2^n)，比穷举好，但仍不是多项式时间。
目前不知道一般 TSP 是否存在多项式时间算法，通常认为没有。

5、TSP 的常见算法

5.1 最邻近法

1
2
3
从起点出发；
每一步选择距离当前顶点最近、且尚未访问的顶点；
访问完全部顶点后回到起点。

优点是很快，缺点是容易被局部最优骗住。

最邻近法不保证最优。课程答案中的 K5 例子里，从 v1 出发可得到权 33 的回路，但最优权是 31。

5.2 最小生成树法

适用于满足三角不等式的 TSP：

1
W(a,c) <= W(a,b) + W(b,c)

算法流程：

1
2
3
4
1. 求原图的最小生成树 T。
2. 将 T 的每条边复制一份，得到欧拉图 G*。
3. 在 G* 中取一条欧拉回路。
4. 按“抄近路法”跳过已经访问过的顶点，得到哈密顿回路。

近似保证：

1
T* <= H <= 2T*

其中 T* 是最优 TSP 权，H 是最小生成树法得到的权。

5.3 最小权匹配法

这是比 MST 复制边更精细的近似方法，也就是 Christofides 思路：

1
2
3
4
5
1. 求最小生成树 T。
2. 找出 T 中的奇度顶点集 V'。
3. 在 V' 导出的完全图中求最小权完美匹配 M。
4. 将 M 加到 T 上，得到欧拉图 G*。
5. 取欧拉回路，再抄近路得到哈密顿回路。

近似保证：

1
T* <= K <= 1.5T*

其中 K 是最小权匹配法得到的权。

5.4 动态规划法

设起点为 1，S 是 {2,...,n} 的子集，且 i in S：

1
2
3
4
Opt[S;i] = 从 1 出发，经过 S 中所有顶点，最后到达 i 的最短路径长度
Opt[{i};i] = W(1,i)
Opt[S;i] = min_{j in S-{i}} Opt[S-{i};j] + W(j,i)
T* = min_{2<=j<=n} Opt[{2,...,n};j] + W(j,1)

复杂度：

1
O(n^2 * 2^n)

6、算法对比表

问题 精确 / 近似 核心工具 复杂度印象 考试写法
中国邮递员 精确 奇度点最短路 + 最小权完美匹配 + 欧拉回路 多项式时间 必须列奇度点和匹配
TSP 穷举 精确 枚举哈密顿回路 (n-1)!/2 n 很小时可用
TSP 动态规划 精确 状态压缩 O(n^2 2^n) 会写递推式即可
最邻近法 近似 贪心 快 不保证最优
MST 抄近路 近似 最小生成树 + 欧拉回路 多项式时间 满足三角不等式时有 2 近似
最小权匹配法 近似 MST + 奇度点最小权匹配 多项式时间 满足三角不等式时有 1.5 近似

7、图论习题课答案摘记

习题 12.1：色多项式

1
2
3
4
f(G,k) = k^5 - 5k^4 + 9k^3 - 7k^2 + 2k
χ(G) = 3
f(G,χ(G)) = f(G,3) = 24
f(G,4) = 216

习题 12.3：树与圈组成的图

若 G 由一棵 n(n>=2) 阶树和一个 m(m>=3) 阶圈组成，则：

1
2
f(G,k) = f(Tn,k) * f(Cm,k)
       = k(k-1)^(n-1) * ((k-1)^m + (-1)^m(k-1))

习题 12.11：3-正则哈密顿图的边色数

结论：

1
若 G 是 3-正则哈密顿图，则 χ'(G)=3。

证明思路：

1
2
3
4
5
1. 由 Vizing 定理或下界，χ'(G) >= Δ(G)=3。
2. 3n=2m，所以 n 为偶数。
3. 哈密顿回路 C 是偶圈，可用两种颜色给 C 的边着色。
4. 不在 C 上的边彼此不相邻，可全部用第三种颜色。
5. 因此 χ'(G)<=3，合并得 χ'(G)=3。

习题 12.12：彼得森图

1
χ'(Petersen)=4。

理由：

1
2
3
Δ=3，所以 3 <= χ' <= 4。
若只用 3 色，外圈奇圈已经迫使颜色排列，继续推到内侧会出现某条边三种颜色都不能用。
所以 3 色不够，χ'=4。

彼得森图不是哈密顿图，可用反证：若存在哈密顿圈，则它是一个覆盖全部顶点的 2-因子；但彼得森图的 2-因子只能分成两个 5-圈，不能成为一个 10-圈，矛盾。

习题 13.1：支配、覆盖、独立、匹配、边覆盖

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
极小支配集：
{v1,v3}, {v1,v4}, {v1,v2}, {v1,v5},
{v2,v3}, {v3,v4}, {v3,v5}, {v2,v4,v5}
γ0 = 2

极小点覆盖集：
{v1,v3}, {v2,v4,v5}
α0 = 2

极大点独立集：
{v1,v3}, {v2,v4,v5}
β0 = 3

极大匹配：
{a,c}, {a,f}, {b,d}, {d,e}, {c,e}, {b,f}
β1 = 2

极小边覆盖：
{a,c,e}, {a,c,f}, {d,b,e}, {d,b,f}, {d,e,c}, {a,f,b}
α1 = 3

习题 13.3：证明 α0(G) >= δ(G)

证明骨架：

1
2
3
4
5
取最大点独立集 V*。
则 N* = V(G)-V* 是最小点覆盖集。
任取 v in V*，因为 V* 内顶点互不相邻，所以 N(v) subseteq N*。
又 d(v) >= δ(G)，于是 |N*| >= δ(G)。
因此 α0(G) >= δ(G)。

习题 13.5：图上取点游戏

结论：

1
第一个人有必胜策略 <=> G 中无完美匹配。

证明思路：

1
2
3
4
5
6
7
8
若 G 有完美匹配 M：
第一个人选 v0 后，第二个人总沿 M 中与当前点匹配的边回应。
第二个人总能走到匹配点，所以第二个人胜。

若 G 无完美匹配：
取最大匹配 M，必有 M-非饱和点 v0。
第一个人先选 v0，之后总沿 M 中的匹配边回应。
因为 M 无可增广路径，最后一步落在第一个人手里。

习题 13.8：课外小组选组长

把小组和学生建成二部图，问能否选出 3 名不兼职组长，等价于问左部三个小组到右部学生是否存在完备匹配。

1
2
3
(1) 满足 t=2 条件，有完备匹配，共 11 种方案。
(2) 满足 Hall 相异性条件，有完备匹配，共 9 种方案。
(3) 不满足 Hall 相异性条件，无完备匹配，不能选出 3 名不兼职组长。

8、应用题答案

习题 14.8：中国邮递员问题

奇度顶点集：

1
V' = {v2, v4, v6, v8}

两两最短路径权：

1
2
3
4
5
6
v2-v4: v2 v1 v4, 权 7
v2-v6: v2 v5 v6, 权 10
v2-v8: v2 v5 v8, 权 10
v4-v6: v4 v5 v6, 权 7
v4-v8: v4 v5 v8, 权 7
v6-v8: v6 v5 v8, 权 8

最小权匹配：

1
M = {(v2,v4), (v6,v8)}

把 v2-v4 与 v6-v8 对应最短路径上的边重复一次，得到欧拉图。最优投递路线权：

1
W(G*) = 68

一条最优欧拉回路：

1
v1 v4 v7 v8 v5 v8 v9 v6 v5 v6 v3 v2 v5 v4 v1 v2 v1

习题 14.13：货郎担问题

题目中的 K5 满足三角不等式，但各算法给出的解可能不唯一。

最邻近法：

1
从 v1 出发，得到哈密顿回路权 W=33。

最小生成树法：

1
2
3
从 v1 出发，可得到：
H1 = v1 v2 v5 v4 v3 v1, W=33
H2 = v1 v2 v5 v3 v4 v1, W=31

最小权匹配法：

1
2
H1 = v1 v2 v5 v3 v4 v1, W=31
H2 = v1 v4 v5 v3 v2 v1, W=31

穷举精确最优解：K5 中不同哈密顿回路共有 4!/2=12 条。

1
2
3
4
5
6
7
8
9
10
11
12
H1  = v1 v2 v3 v4 v5 v1, W=32
H2  = v1 v2 v3 v5 v4 v1, W=31
H3  = v1 v2 v4 v3 v5 v1, W=33
H4  = v1 v2 v4 v5 v3 v1, W=34
H5  = v1 v2 v5 v3 v4 v1, W=31
H6  = v1 v2 v5 v4 v3 v1, W=33
H7  = v1 v3 v2 v4 v5 v1, W=37
H8  = v1 v3 v2 v5 v4 v1, W=35
H9  = v1 v3 v4 v2 v5 v1, W=37
H10 = v1 v3 v5 v2 v4 v1, W=36
H11 = v1 v4 v2 v3 v5 v1, W=35
H12 = v1 v4 v3 v2 v5 v1, W=34

所以：

1
2
最短哈密顿回路：H2 与 H5，权均为 31。
最长哈密顿回路：H7 与 H9，权均为 37。

9、期末样卷图论速记

5 阶无向树

1
互不同构类型共有 3 种：路型、星型、丫型。

K5 的标定生成树数

由 Cayley 公式：

1
2
n 阶完全图 K_n 的标定生成树数 = n^(n-2)
K5 的生成树数 = 5^3 = 125

彼得森图常用结论

1
2
3
4
5
最大独立集大小：4
最小点覆盖大小：6
最小支配集大小：3
有哈密顿通路，但无哈密顿回路
点割集大小示例：3 个顶点，注意要检查极小性

11 阶 k-正则简单图

k 的可能性先用握手定理筛选：

1
2
11k 必须为偶数，所以 k 只能是偶数。
k=1,3,5,7,9 时不存在 11 阶 k-正则简单图。

一定欧拉 / 一定哈密顿：

1
2
3
k=6,8,10 时一定哈密顿：
任意两点度数和为 2k >= 12 > 11，可用 Ore 型条件。
又因为 k 为偶数且图连通，所以一定欧拉。

反例说明：

1
2
k=0,2,4 时可能不连通，所以不一定哈密顿，也不一定欧拉。
k=4 的反例：K5 并上 K6 去掉一个完美匹配。

边色数：

1
2
3
4
k=2,4,6,8,10 时，边色数一定是 k+1。
理由：每种颜色在 11 阶图中至多染 5 条边，而总边数是 11k/2，
因此至少需要 k+1 种颜色；再由 Vizing 定理，χ' 只能是 k 或 k+1。
k=0 时边色数为 0。

10、图论复盘主线

主题 关键工具 做题入口
图的基本概念 顶点、边、度数、同构、子图 先数 n,m,d(v)
通路与回路 简单通路、回路、距离 找路径、证连通
连通性 连通分支、割点、割边、块 删除点/边后看分支数
欧拉图 全偶度、欧拉回路 看边是否能一次走完
哈密顿图 Dirac、Ore、必要条件 看点是否能一次走完
树 m=n-1、生成树、基本回路/割集 用无圈连通等价条件
矩阵表示 邻接矩阵、可达矩阵 幂矩阵数通路
平面图 欧拉公式、Kuratowski 定理 先用边数上界排除
着色 色多项式、Vizing 定理 点色、边色、面色分清
匹配 可增广路径、Hall、Tutte 二部图先想 Hall
带权应用 最短路、MST、匹配 邮递员和 TSP 分模型

11、复盘清单

1
2
3
4
5
6
7
1. 会把邮递员问题转成“奇度点最小权完美匹配”。
2. 会用 W(G*) = W(G) + W(M) 计算最优投递路线权。
3. 会区分欧拉回路、哈密顿回路和最优带权回路。
4. 会说明 TSP 为什么通常用近似算法。
5. 会写最邻近法、MST 抄近路法、最小权匹配法的流程。
6. 会写 TSP 动态规划递推式 Opt[S;i]。
7. 会用期末样卷里的 11 阶 k-正则图做握手定理、Ore 条件、Vizing 定理综合判断。