返回：0100 离散数学课程总目录 · 上一章：0111 图着色 · 下一章：0113 图论应用、习题课与课程总结

1、学习目标

本章把图论中的“选点/选边”问题系统化：支配、覆盖、独立、匹配和边覆盖。核心目标是会在这些参数之间互相转化，尤其是Gallai 恒等式、Berge 定理、Hall 定理。

2、核心概念

概念 记号 定义
支配集 D 每个不在 D 中的顶点都与 D 中某点相邻
支配数 gamma0(G) 最小支配集大小
点覆盖 K 每条边至少有一个端点在 K 中
点覆盖数 alpha0(G) 最小点覆盖大小
点独立集 S 任意两点不相邻
点独立数 beta0(G) 最大点独立集大小
匹配 M 任意两条边不相邻
匹配数 beta1(G) 最大匹配大小
边覆盖 L 每个顶点都与 L 中某条边关联
边覆盖数 alpha1(G) 最小边覆盖大小

“极小/极大”说的是不能再删或不能再加，是局部性质；“最小/最大”说的是数量最少或最多，是全局最优。极小支配集不一定是最小支配集，极大匹配也不一定是最大匹配。

3、支配、独立、点覆盖的关系

极大独立集一定是极小支配集：

1
V* 是极大独立集 => V* 是极小支配集

理由：若存在 v 不被 V* 支配，则 V*∪{v} 仍是独立集，矛盾。

支配数与点独立数：

1
gamma0(G) <= beta0(G)

无孤立点图中，点覆盖是支配集：

1
gamma0(G) <= alpha0(G)

团与独立集通过补图互相转化：

1
2
S 是 G 的团 <=> S 是 Gbar 的独立集
nu0(G)=beta0(Gbar)

4、关键定理

点覆盖与点独立互补：

1
2
S 是点独立集 <=> V-S 是点覆盖集
alpha0(G)+beta0(G)=n

若 G 无孤立点，则边覆盖与匹配满足 Gallai 恒等式：

1
alpha1(G)+beta1(G)=n

Berge 定理：

1
2
匹配 M 是最大匹配
<=> G 中不存在 M-可增广路径。

Hall 定理：二部图 G=<X,Y,E> 中存在覆盖 X 的匹配，当且仅当：

1
任意 S subset X，都有 |N(S)| >= |S|。

Tutte 定理：一般图存在完美匹配，当且仅当：

1
任意 V' subset V(G)，G-V' 的奇数阶连通分支数 <= |V'|。

常用推论：

1
无桥 3-正则图有完美匹配。

5、逻辑乘法求极小集

课件里求全体极小支配集、极小点覆盖集时常用“逻辑乘法”：

1
2
a+a=a
a*a=a

支配集生成式：

1
prod_{v in V}(v + sum_{u in Gamma(v)} u)

每个乘积项对应一个支配集，化简后保留不被其他项包含的项，就是全体极小支配集。

点覆盖生成式：

1
prod_{(u,v) in E}(u+v)

每条边至少选一个端点，化简后保留极小项，就是全体极小点覆盖。

点独立集可由点覆盖取补：

1
K 是极小点覆盖 <=> V-K 是极大点独立集

6、匹配与边覆盖做题流程

最大匹配到最小边覆盖：

1
2
3
4
5
1. 先找一个最大匹配 M。
2. M 已覆盖 2|M| 个顶点。
3. 每个非饱和点任选一条关联边补进来。
4. 得到最小边覆盖 W。
5. |W| = n - |M|。

最小边覆盖到最大匹配：

1
2
3
4
1. 从最小边覆盖 W 中开始。
2. 如果有相邻边，删除其中一条且保持覆盖尽量不破坏匹配结构。
3. 直到剩下边两两不相邻。
4. 剩下的是最大匹配。

Berge 增广路模板：

1
2
3
4
5
1. 标出当前匹配 M。
2. 从非饱和点出发，寻找“非匹配边、匹配边、非匹配边...”交替的路径。
3. 若路径另一端也是非饱和点，则这是 M-可增广路径。
4. 用 M 与该路径边集做对称差，匹配数增加 1。
5. 找不到可增广路径时，M 才是最大匹配。

极大匹配只是“不能再加边”，最大匹配才是“边数最多”。判断最大匹配要看可增广路径，而不是只看当前匹配还能不能直接加一条边。

7、Hall 定理与二部图匹配

1
2
3
二部图 G=<X,Y,E>, |X|<=|Y|
存在覆盖 X 的匹配
<=> 任意 S subset X, |N(S)| >= |S|

Hall 条件检查流程：

1
2
3
4
1. 明确要覆盖哪一侧，通常是人数少或“岗位/小组”那一侧。
2. 对这一侧任意子集 S，看它们合起来能连到多少候选点 N(S)。
3. 若存在 |N(S)|<|S|，则没有完备匹配。
4. 若所有 S 都满足 |N(S)|>=|S|，则存在完备匹配。

t-条件是 Hall 条件的常用充分条件：

1
2
3
X 中每个点至少关联 t 条边；
Y 中每个点至多关联 t 条边；
=> 存在覆盖 X 的匹配。

二部图重要结论：

1
2
k-正则二部图存在 k 个边不重的完美匹配。
无孤立点二部图中，alpha0=beta1。

8、常见做题方法

1
2
3
4
5
1. 点覆盖题：先找最大点独立集，再取补集。
2. 边覆盖题：先找最大匹配，再补未饱和顶点。
3. 匹配题：找可增广路径；没有可增广路径才是最大。
4. 二部图分配题：建二部图，用 Hall 条件判断完备匹配。
5. 完美匹配题：二部图优先 Hall，一般图才考虑 Tutte。

9、习题与答案

习题 13.1

给定 5 阶 6 边图，答案如下：

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}
gamma0=2

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

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

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

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

习题 13.3

证明任意无向图 G 有：

1
alpha0(G) >= delta(G)

证明：设 V* 是最大点独立集，N*=V-V* 是最小点覆盖。对任意 v in V*，其邻域都在 N* 中，所以：

1
alpha0=|N*| >= d(v) >= delta(G)

若 delta(G)=0，结论显然；若没有孤立点，上面的邻域论证直接成立。

习题 13.5

两人在图上轮流沿相邻点取未取过顶点，最后取点者胜。证明：先手有胜策当且仅当 G 无完美匹配。

答案思路：

1
2
3
若有完美匹配 M，后手总沿匹配边回应，后手胜。
若无完美匹配，取最大匹配 M 的非饱和点开局。
之后先手总沿匹配边回应；因不存在可增广路径，最后先手胜。

习题 13.8

3 个课外小组选 3 名不兼职组长。建二部图：

1
2
3
左部：物理、化学、生物
右部：张、王、李、赵、陈
边：同学属于该小组

答案：

1
2
3
(1) 满足 Hall 条件，可选，共 11 种。
(2) 满足 Hall 条件，可选，共 9 种。
(3) 不满足 Hall 条件，不可选。

10、复盘清单

1
2
3
4
5
6
7
8
1. 会写支配、点覆盖、点独立、匹配、边覆盖的定义。
2. 会用 alpha0+beta0=n。
3. 会用 alpha1+beta1=n（无孤立点）。
4. 会找可增广路径。
5. 会用 Hall 条件解决分配问题。
6. 会区分极小/最小、极大/最大。
7. 会从最大匹配构造最小边覆盖。
8. 知道二部图 alpha0=beta1。