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该节点被选中子节点可以是任意状态取各子树最小值之和再加 11未选中但至少一个子节点被选中来支配它至少选一个子节点为状态 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(nm) 就能完成。求最大独立集则是 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最后找两三道建模题练手。不要一上来就啃证明也不要只背定义不做题。这四个概念的价值不在定义本身而在它们之间的转化关系——能把一个问题从支配集翻译成覆盖集、从独立集翻译成匹配才是真正掌握了。后面如果继续往下学下一个自然的方向是团问题独立集在补图上的对应和支配集在平面图上的特殊性质那又是另一片天地了。
