1. 四个概念到底在解决什么问题
翻到图论笔记的第七篇，支配集、覆盖集、独立集、匹配这四个词摆在一起，很多人第一反应是“定义都认识，但不知道它们之间什么关系”。我当初学这一块的时候也卡了很久，教材上每个定义单独看都懂，合上书就串不起来。后来做了一些组合优化的题目，回头再看这四个概念，才发现它们其实是同一枚硬币的四个面——都在描述“顶点或边之间如何用最少的资源覆盖全部需求”这件事，只是约束条件和优化目标不同。
先把话说清楚：这篇笔记适合已经掌握图的基本概念（顶点、边、度、路径、连通性）的读者，如果你是刚接触图论的小白，建议先把前六篇的基础打牢。这四个概念在网络选址、任务调度、资源分配、无线传感器布点、排班匹配等场景里出现频率极高，理解它们之间的转化关系，比死记定义有用得多。
我个人的理解框架是这样的：支配集关心的是“顶点管顶点”，一个顶点能“罩住”自己和它的邻居；覆盖集关心的是“顶点管边”，一条边的两个端点至少有一个被选中；独立集关心的是“顶点之间互不打架”，选中的顶点两两不相邻；匹配关心的是“边之间互不打架”，选中的边两两不共端点。你看，前两个是“覆盖型”问题，后两个是“互斥型”问题，而支配集和覆盖集之间、独立集和匹配之间，又各自存在互补的对偶关系。这个框架一旦建立，后面所有定理和算法都能挂上去。
提示：学这四个概念时，不要孤立地背定义，先画一个小图（五六个顶点就够），把四种集合各标一遍，用不同颜色区分，比看十页书都管用。
2. 支配集：用最少的点罩住整张图
2.1 支配集的定义与直观理解
给定无向图 G=(V,E)，如果存在顶点子集 D⊆V，使得对于任意顶点 v∈V，要么 v 本身在 D 中，要么 v 至少有一个邻居在 D 中，那么 D 就叫支配集。换句话说，D 中的顶点能“支配”自己和所有与它相邻的顶点，整张图的每个顶点都被罩住了。
生活里的类比很直接：假设你在一栋楼里装 WiFi 路由器，每个路由器能覆盖自己所在房间和相邻房间，问最少装几个路由器能让所有房间都有信号——这就是最小支配集问题。注意“自己覆盖自己”这个细节，很多人第一次写判定程序时会漏掉，导致孤立顶点永远无法被支配。
最小支配集的规模记作 γ(G)，称为支配数。求精确的最小支配集是 NP 难问题，这一点必须提前说清楚，后面讲算法时所有“高效”方案都是近似或针对特殊图结构的。
2.2 贪心构造与它的局限
最直观的做法是贪心：每次选一个能支配最多“尚未被支配顶点”的顶点，直到全部被支配。这个思路实现简单，我用 Python 写过一个十几行的版本，核心就是维护一个未覆盖集合，每轮扫描所有顶点算增量收益。
def greedy_dominating_set(adj, n): uncovered = set(range(n)) chosen = [] while uncovered: best, gain = -1, -1 for v in range(n): cover = {v} | set(adj[v]) g = len(cover & uncovered) if g > gain: best, gain = v, g chosen.append(best) uncovered -= ({best} | set(adj[best])) return chosen实测下来，这个贪心在随机图上通常能得到接近最优的解，但在一些特殊结构上会翻车。我踩过的一个坑是星形图：中心点一次能覆盖全部，贪心第一步就选它，结果正确；但换成双星结构（两个中心各连一批叶子，两中心之间隔一条长路径），贪心可能先选路径中间的点，导致后面多选好几个。贪心的近似比大约是 ln(Δ)+1 量级（Δ 为最大度），不是常数因子，所以对精度要求高的场景不能只靠它。
2.3 树上支配集：动态规划才是正解
如果图是一棵树，最小支配集可以在 O(n) 时间内精确求出，方法是树形 DP。这个技巧值得单独记一笔，因为很多实际问题的底层结构就是树（组织架构、目录结构、部分通信网络）。
状态设计是难点。每个节点需要区分三种情况：节点被选中（自己支配自己）、节点未选中但被某个子节点支配、节点未选中且需要父节点来支配。我习惯记成 0/1/2 三态：
| 状态 | 含义 | 转移要点 |
|---|---|---|
| 0 | 该节点被选中 | 子节点可以是任意状态，取各子树最小值之和再加 1 |
| 1 | 未选中，但至少一个子节点被选中来支配它 | 至少选一个子节点为状态 0，其余取 min(0,1) |
| 2 | 未选中，等待父节点支配 | 所有子节点不能是状态 2，只能取 min(0,1) |
状态 1 的转移最容易写错，必须强制“至少一个子节点选 0”，实现时可以先全部取 min(0,1) 求和，再检查是否已有子节点取 0，没有的话补一个最小的“0 减 min(0,1)”差值。这个差值技巧在树形 DP 里非常常用，我第一次写的时候直接暴力枚举哪个子节点选 0，复杂度退化成 O(n·Δ)，虽然也能过，但不够优雅。
注意：树形 DP 的边界是叶子节点。叶子没有子节点，状态 0 代价为 1，状态 1 不可达（没有子节点能支配它），状态 2 代价为 0。初始化写错是新手最常见的 bug。
3. 覆盖集：顶点与边的另一种对话
3.1 顶点覆盖的定义与最小顶点覆盖
顶点覆盖（vertex cover）说的是：选一个顶点子集 C，使得图中每条边至少有一个端点在 C 中。注意它和支配集的区别——支配集管的是“所有顶点被罩住”，覆盖集管的是“所有边被碰到”。一条边的两个端点只要有一个在 C 里，这条边就被“覆盖”了。
最小顶点覆盖的规模记作 τ(G)。这个问题同样是 NP 难的，但它有一个非常漂亮的性质：在二分图中，最小顶点覆盖可以在多项式时间内求解，而且和最大匹配有直接的数量关系（König 定理，后面第 5 节会展开）。这个性质让顶点覆盖成为很多实际问题的建模工具，比如任务分配中“选最少的工人覆盖所有任务对”。
3.2 顶点覆盖与支配集的转化关系
这两个概念经常被混淆，我整理一下它们的联系：任何一个顶点覆盖都是支配集（因为每条边被覆盖意味着每个非孤立顶点要么自己被选、要么邻居被选），但反过来不成立。也就是说顶点覆盖是支配集的子集族，最小顶点覆盖 ≥ 最小支配集在规模上不一定，但覆盖的约束更强。
实际做题时有个常用技巧：如果题目要求“每条边至少一个端点被选”，那是顶点覆盖；如果要求“每个点要么被选要么邻居被选”，那是支配集。读题时把“边”和“点”这两个字圈出来，基本不会判断错。
3.3 边覆盖：换个对象继续覆盖
既然顶点可以覆盖边，边也可以覆盖顶点。边覆盖是选一个边子集 F，使得每个顶点至少与 F 中一条边关联。最小边覆盖的规模记作 ρ(G)，它和最大匹配有直接关系：在没有孤立顶点的图中，最小边覆盖 = 顶点数 − 最大匹配数。这个公式我建议直接背下来，做题时能省大量推导。
为什么这个公式成立？直观理解：最大匹配已经用最少的边覆盖了 2×|M| 个顶点，剩下 n−2|M| 个顶点每个需要一条额外的边去覆盖，所以总数是 |M| + (n−2|M|) = n−|M|。这个推导过程比公式本身更值得记住，因为它解释了“为什么匹配是边覆盖的核心”。
4. 独立集：互不干扰的最大集合
4.1 独立集的定义与最大独立集
独立集是顶点子集 I，其中任意两个顶点之间没有边相连。最大独立集的规模记作 α(G)。这个概念在冲突消解类问题里无处不在：选最多的任务同时执行且互不冲突、选最多的频率分配给互不干扰的设备、选最多的课程排进同一时间段。
独立集和顶点覆盖有一个极其简洁的互补关系：I 是独立集当且仅当 V−I 是顶点覆盖。证明只有两行——如果 I 中任意两点无边，那么每条边的两个端点不可能都在 I 中，所以至少一个在 V−I 中，即 V−I 覆盖所有边。这个对偶关系意味着 α(G) + τ(G) = n，求最大独立集和求最小顶点覆盖是同一个问题的两种说法。
4.2 极大独立集与最大独立集的区别
这两个词一字之差，含义完全不同，考试和面试里经常挖坑。极大独立集（maximal）是指不能再加入任何顶点而保持独立的集合，它是“局部饱和”的；最大独立集（maximum）是规模最大的独立集，是“全局最优”的。极大独立集不一定是最大独立集，但最大独立集一定是极大独立集。
求极大独立集很简单，随便从一个空集开始，不断加入不与现有集合冲突的顶点，直到加不进去为止，O(n+m) 就能完成。求最大独立集则是 NP 难的。我在面试里被问过“为什么贪心求极大独立集不能保证最大”，当时举的反例是一条长度为 4 的路径：贪心从中间开始选可能得到 2 个点的极大独立集，但最大独立集是 3 个点（选第 1、3、5 个顶点）。这个反例建议记牢，解释起来最省事。
4.3 二分图上的最大独立集
二分图里最大独立集可以多项式求解，利用上面的互补关系：α(G) = n − τ(G)，而二分图的最小顶点覆盖又等于最大匹配（König 定理），所以二分图最大独立集 = n − 最大匹配数。这条链路把四个概念全串起来了，是整篇笔记的核心脉络。
实际写代码时，流程是：先跑匈牙利算法或 Hopcroft-Karp 求最大匹配，然后用 n 减去匹配数得到最大独立集规模。如果需要输出具体集合，还得从最小顶点覆盖反推——从每个未匹配的左部顶点出发做交替路搜索，左部未访问点加右部已访问点构成最小顶点覆盖，取补集就是最大独立集。这个构造过程细节较多，我建议单独写个小函数封装，别和匹配算法混在一起。
5. 匹配：边与边的互斥选择
5.1 匹配的基本概念与分类
匹配是边子集 M，其中任意两条边不共享端点。根据是否要求覆盖所有顶点，分为完美匹配（所有顶点都被匹配）、最大匹配（边数最多）、极大匹配（不能再加边）。三者的关系是：完美匹配一定是最大匹配，最大匹配一定是极大匹配，反之不成立。
最大匹配的规模记作 ν(G)。求一般图的最大匹配要用带花树算法（Blossom），实现复杂度较高；二分图的最大匹配则简单得多，匈牙利算法 O(VE) 或 Hopcroft-Karp O(E√V) 都能搞定。日常遇到的建模问题绝大多数是二分图结构（左右两类对象之间的配对），所以重点掌握二分图匹配就够了。
5.2 匈牙利算法的实现要点
匈牙利算法的本质是不断找增广路。核心是一个match数组记录右部顶点当前匹配的左部顶点，对每个左部顶点尝试 DFS 寻找增广路，找到就把路径上的匹配状态翻转。
def hungarian(adj, n_left, n_right): match_r = [-1] * n_right def dfs(u, visited): for v in adj[u]: if visited[v]: continue visited[v] = True if match_r[v] == -1 or dfs(match_r[v], visited): match_r[v] = u return True return False result = 0 for u in range(n_left): if dfs(u, [False] * n_right): result += 1 return result这段代码短小但有几个易错点。第一，visited数组每轮要重置，它标记的是“本轮增广路搜索中右部顶点是否被访问”，防止死循环。第二，递归深度可能达到顶点数，图大的时候要改成迭代或调高递归限制。第三，这个版本只返回匹配数，如果需要输出匹配方案，从match_r反推即可。
5.3 König 定理：把四个概念串起来
König 定理说：二分图中最大匹配数等于最小顶点覆盖数，即 ν(G) = τ(G)。结合前面的互补关系 α(G) = n − τ(G)，立刻得到 α(G) = n − ν(G)。这一串等式是二分图理论的骨架，也是我前面说“四个概念是一枚硬币四面”的底气所在。
| 关系 | 公式 | 适用范围 |
|---|---|---|
| 独立集与顶点覆盖互补 | α(G) + τ(G) = n | 任意图 |
| 最小边覆盖与最大匹配 | ρ(G) = n − ν(G) | 无孤立点图 |
| König 定理 | ν(G) = τ(G) | 二分图 |
| 二分图最大独立集 | α(G) = n − ν(G) | 二分图 |
这张表我建议直接抄在笔记首页。做题时先判断图是不是二分图，是的话四个量知道一个就能推其余三个，效率提升非常明显。
6. 实操中的常见坑与排查思路
6.1 概念混淆类错误
最高频的错误是把支配集和顶点覆盖搞混。我见过不少人在建模时把“每个任务至少被一个工人覆盖”写成支配集约束，结果约束过松导致解不对。判断口诀：约束里出现“边”就是覆盖，出现“邻居”就是支配。另一个高频错误是极大和最大不分，写论文或报告时用词要精确，极大独立集不能直接说成“最大独立集”。
6.2 算法选择类错误
一般图的最大独立集、最小支配集都是 NP 难的，如果题目规模到了几千个顶点还硬上精确算法，必然超时。这时候要么确认图有特殊结构（树、二分图、区间图），要么改用近似算法或整数规划求解器。我踩过的坑是在一个上万个顶点的稀疏图上跑精确支配集，跑了半小时没出结果，后来发现图其实是二分图，换成匹配算法几毫秒就出答案。先看结构，再选算法，这个顺序不能反。
6.3 实现细节类错误
树形 DP 的状态转移、匈牙利算法的 visited 重置、König 定理构造最小覆盖时的交替路搜索，这三处是代码 bug 的重灾区。排查时建议用小规模手工可验证的图做单元测试，比如 5 个顶点的路径、6 个顶点的完全二分图 K3,3，把预期结果写死在测试里，改代码后先跑测试再提交。
| 问题现象 | 可能原因 | 排查方法 |
|---|---|---|
| 支配集结果偏大 | 贪心选点顺序问题 | 换随机顺序多次运行取最优 |
| 匹配数偏小 | visited 未重置或重置时机错 | 打印每轮增广路搜索日志 |
| 独立集与覆盖集之和不等于 n | 构造覆盖集时漏了孤立点 | 检查孤立点是否单独处理 |
| 树形 DP 结果异常 | 叶子节点初始化错误 | 用单节点、两节点树验证 |
提示：孤立顶点是很多公式的边界条件。最小边覆盖公式要求无孤立点，支配集里孤立点必须自己选自己，独立集里孤立点可以全部选入。写代码前先把孤立点单独拎出来处理，能避免一大类错误。
7. 从概念到建模：几个典型场景的映射
7.1 设施选址与支配集
在一个区域内部署应急设施，每个设施能服务自身位置和相邻区域，要求所有区域都被服务且设施数最少——标准的最小支配集。如果区域之间的相邻关系构成树（比如沿主干道分布），树形 DP 直接上；如果是一般图，用贪心加局部搜索的组合，先贪心得到一个可行解，再用 2-opt 交换局部优化，实测在几百个顶点的规模上效果不错。
7.2 任务分配与二分图匹配
工人和任务两类对象，工人能胜任某些任务，要求分配尽可能多的任务且一人一任务——二分图最大匹配。如果还要求“每个工人都必须有任务”，那就是完美匹配问题，先判断左右部顶点数是否相等，再用匈牙利算法跑，跑完检查匹配数是否等于左部顶点数。这个场景里 König 定理的用处是：当无法完美匹配时，最小顶点覆盖告诉你“最少卡在哪些工人或任务上”，对分析瓶颈很有帮助。
7.3 冲突消解与独立集
一组任务，某些任务两两冲突不能同时执行，要求选最多的任务同时执行——最大独立集。如果冲突关系构成二分图（比如任务分两类，冲突只发生在类间），用 n 减最大匹配秒解。如果不是二分图，规模小的时候可以上分支定界，规模大的时候考虑补图上的最大团算法或者直接上整数规划。
7.4 资源覆盖与边覆盖
一条流水线上有若干工位，每个工位需要至少一道工序覆盖，一道工序能覆盖它两端的工位，要求工序数最少——最小边覆盖。套公式 ρ = n − ν，先求最大匹配再减，比直接建模成集合覆盖问题高效得多。这个转化思路值得记住：看到“边覆盖顶点”就想到匹配。
8. 我自己的学习路径复盘
回过头看，这四个概念我真正搞懂是在把 König 定理的证明自己推了一遍之后。证明本身不长：从最大匹配出发，构造一个顶点覆盖，证明它的规模等于匹配数，再证明任何顶点覆盖都不小于最大匹配。构造过程用到了交替路和未匹配顶点的划分，把匹配、覆盖、独立集三个概念全用上了。推完那一遍，四个概念的关系图在我脑子里就闭合了。
如果你也在学这一块，我的建议是：先画图建立直觉，再背那张关系表，然后手写一遍匈牙利算法和树形 DP，最后找两三道建模题练手。不要一上来就啃证明，也不要只背定义不做题。这四个概念的价值不在定义本身，而在它们之间的转化关系——能把一个问题从支配集翻译成覆盖集、从独立集翻译成匹配，才是真正掌握了。
后面如果继续往下学，下一个自然的方向是团问题（独立集在补图上的对应）和支配集在平面图上的特殊性质，那又是另一片天地了。
