• 文档
• 教程
• 示例工程

导读

本文聚焦《算法导论》（CLRS）第 35 章"近似算法"的核心案例——顶点覆盖（Vertex Cover）问题及其经典 2 倍近似算法 APPROX-VERTEX-COVER，并结合本仓库 C35-Approximation-Algorithms/35.1.md 中习题 35.1-1 与 35.1-2 的题解展开深度剖析。读完本文，你将掌握：顶点覆盖问题的形式化定义与 NP 难背景、APPROX-VERTEX-COVER 算法的完整伪代码与贪心机制、近似比为 2 的严格证明，以及如何用"两节点单边图"构造算法必然产生次优解的反例，并理解算法所选边集构成极大匹配（maximal matching）这一关键性质的证明脉络。

一、问题背景：顶点覆盖为什么需要"近似"而不是"精确"

1.1 顶点覆盖的定义

给定无向图 G = (V, E)，一个**顶点覆盖（vertex cover）**是顶点集合 C ⊆ V，使得图 G 中的每一条边至少有一个端点落在 C 中。最小顶点覆盖问题（Minimum Vertex Cover）要求找出包含顶点数最少的顶点覆盖 C*。

该问题在理论计算机科学中地位特殊：它是 Karp 21 个 NP 完全问题之一，其决策形式（给定 k，是否存在大小不超过 k 的顶点覆盖）是 NP 完全的。这意味着除非 P = NP，否则不存在多项式时间算法能够精确求出最小顶点覆盖。因此，研究界转而寻求多项式时间近似算法——用"稍微大一点"的覆盖换来"足够快"的运行时间，这正是第 35 章"近似算法"这一主题的出发点。

1.2 近似比与 2 倍近似的意义

对最小化问题而言，若算法 A 对任意实例都能在多项式时间内给出可行解 C，且满足

|C| ≤ 2 · |C*|

其中 C* 为最优解，则称 A 为2 倍近似算法（近似比为 2）。顶点覆盖恰好是少数几个拥有"常数倍近似比"的经典 NP 难问题之一，APPROX-VERTEX-COVER 正是教科书式的代表。

二、APPROX-VERTEX-COVER 算法剖析：行 4 的贪心本质

CLRS 第 35.1 节给出的 APPROX-VERTEX-COVER 算法基于一个极其朴素的贪心策略，其伪代码结构如下：

APPROX-VERTEX-COVER(G) 1 C = ∅ 2 E' = G.E 3 while E' ≠ ∅ 4 let (u, v) be an arbitrary edge of E' // 任选一条边 5 C = C ∪ {u, v} // 把两个端点都放入覆盖 6 remove from E' every edge incident on either u or v 7 return C

习题 35.1-2 中提到的"line 4"正是上述第 4 行——任选一条剩余边 (u, v) 并把其两个端点都加入顶点覆盖 C。算法的贪心逻辑可以概括为三步循环：

1. 任选边：在当前剩余边集 E' 中任取一条边 (u, v)；
2. 双端点入覆盖：将 u、v 同时加入 C（注意是加入两个端点，这正是与精确算法最大的不同——不做任何"二选一"的判断）；
3. 收缩子问题：删除 E' 中所有与 u 或 v 相关联的边，剩余图成为一个规模更小的子问题，循环直至 E' 为空。

值得强调的是，第 4 行中的"任选"（arbitrary）意味着该算法不依赖边的选择顺序——无论按何种顺序挑边，最终得到的覆盖大小都满足相同的 2 倍近似比保证。这个性质在 35.1-1 的反例构造中会被再次用到：正因为选择是任意的，反例必须对"任意选择"都成立，才能称得上"always yields a suboptimal solution"。

2.1 为什么近似比是 2：极大匹配视角

APPROX-VERTEX-COVER 的近似比证明并不直接来自"覆盖"本身，而是借助匹配这一桥接概念（其关键引理正是 35.1-2 的结论）：

• 算法在行 4 选出的所有边构成集合 A。因为每选一条边后，与它共享端点的所有边都被删除，所以 A 中任意两条边不共享端点——A 是一个匹配；
• 循环终止时 E' = ∅，意味着图中已不存在任何一条与 A 中所有边都不共享端点的边——A 是极大匹配（maximal matching）（35.1-2 的结论）；
• 由于任意顶点覆盖必须覆盖匹配 A 中每一条边，而一条边至少需要一个端点被选中，故最优覆盖满足 |C*| ≥ |A|；
• 算法输出的覆盖 C 包含 A 中每条边的两个端点，因此 |C| = 2|A| ≤ 2|C*|。

由此得到 |C| ≤ 2|C*|，即近似比为 2。这一推导链条完整展示了"近似算法的分析往往要借助问题之外的组合结构（这里是匹配）"这一思想。

三、习题 35.1-1 详解：两节点单边图——必然次优的反例

原题：给出一张图，使得 APPROX-VERTEX-COVER 在其上"总是"（always）产生次优解。

仓库题解（35.1.md）给出的反例：取一张只含两个节点 u、v 和一条边 (u, v) 的图。

分析如下：

• 最优解：最小顶点覆盖只需覆盖唯一边 (u, v)，因此选择 {u} 或 {v} 即可，|C*| = 1；
• 算法输出：算法在行 4 只能选中这条唯一的边，随即把 u 和 v同时加入覆盖，|C| = 2；
• 结论：|C| = 2 > |C*| = 1，且由于该图只有一条边、不存在其他选择分支，无论算法"任选"哪条边（事实上只有一条可选），输出都必然包含两个端点——因此算法在此图上总是产生次优解。

这个例子还有两个值得延伸的观察：

1. "总是"一词的精确含义：反例必须对所有可能的任选边顺序都成立，单边图恰好使得选择空间退化，保证了"always"；
2. 近似比上界是紧的（tight）：该例中算法输出恰好是最优解的 2 倍，说明 2 倍近似比这一上界无法被进一步改进到更小的常数（对 APPROX-VERTEX-COVER 这一具体算法而言）——这也是"用 2 倍解换多项式时间"这一取舍的直观注脚。

四、习题 35.1-2 详解：行 4 所选边集 A 是极大匹配

原题：设 A 为 APPROX-VERTEX-COVER 行 4 选出的边集，证明 A 是图 G 的一个极大匹配。

仓库题解（35.1.md）的论证思路：在行 4 中随机选择一条边 (u, v) 后，算法删除所有与 u 或 v 关联的边，剩余图成为子问题继续迭代。这一过程保证了 A 的两个性质：

1. A 是匹配：每当 (u, v) 被选入 A，所有与 u、v 中任一节点相邻的边都被立即删除，因此后续选出的任何边都不可能再包含 u 或 v，即 A 中任意两条边没有公共端点，满足匹配定义；
2. A 是极大匹配：当算法终止时 E' = ∅，图中已不存在任何"未被 A 中边覆盖端点"的边。换言之，任何一条不在 A 中的边都必然与 A 中某条边共享端点，无法再加入 A 而不破坏匹配性质——这正是极大匹配的定义：无法通过添加更多边来扩充的匹配。

把这两点合起来，即可严谨地写出完整证明：

证明：对任意两条不同的边 e1, e2 ∈ A，不妨设 e1 = (u, v) 在 e2 之前被选出。算法选完 e1 后即删除所有与 u 或 v 关联的边，故 e2 不可能包含 u 或 v，A 中任意两条边不相交，A 是匹配。又因算法循环至 E' = ∅ 才停止，图中不存在与 A 中所有边均不相交的剩余边，故 A 是极大匹配。∎

4.1 区分两个易混概念：极大匹配 vs 最大匹配

这一题的价值还在于帮读者厘清一对高频混淆概念：

APPROX-VERTEX-COVER 得到的只是极大匹配，而非最大匹配——这正是它只能保证 2 倍近似、无法保证精确的原因之一。任何极大匹配 M 都满足 |C*| ≥ |M|（最优覆盖至少要覆盖 M 中每条边的一个端点），这一不等式贯穿了整个近似比证明，是理解算法分析的关键纽带。

五、与本仓库的关联：C35 章节在仓库中的定位

本仓库（README.md 自述为Solutions to Introduction to Algorithms）以章节为单位组织《算法导论》全部习题题解，其中第 35 章近似算法位于目录表"Part VII: Selected Topics"下的 XXXV 行，目前包含两个文档：

• C35-Approximation-Algorithms/35.1.md：第 35.1 节"顶点覆盖问题"习题 35.1-1、35.1-2 的题解，即本文剖析的主体；
• C35-Approximation-Algorithms/35.2-5.md：第 35.2 节"旅行商问题"习题 35.2-5 的题解（利用欧氏距离满足三角不等式证明最优环游不自交），可作为第 35 章近似算法家族中"三角不等式"技巧的延伸阅读。

需要说明的是，35.1 节题解仓库并未附带顶点覆盖算法的可运行源码实现（该章节目录下仅有上述两个 Markdown 题解文档），因此本文的算法分析以题解文字与 CLRS 教材伪代码为准。依据仓库 README 末尾的声明，这些题解属于社区众包成果（crowdsourced work），阅读时可结合教材原文交叉验证。

六、要点总结

围绕 APPROX-VERTEX-COVER，本文覆盖的核心知识链条可归纳为：

1. 问题层面：最小顶点覆盖是 NP 完全问题，精确求解不可行，需要近似算法；
2. 算法层面：行 4 的"任选一条边、两个端点全收"的贪心策略，构造出大小恰为所选边数两倍的覆盖；
3. 证明层面：行 4 所选边集 A 是极大匹配（35.1-2），配合 |C*| ≥ |A| 推出 |C| = 2|A| ≤ 2|C*|，近似比为 2；
4. 紧性层面：两节点单边图（35.1-1）使算法必然输出 2 而最优解为 1，说明 2 倍上界对该算法是紧的。

这四条主线构成了理解"为什么近似算法也能给出可证明的次优保证"的最小完整闭环，也是继续阅读第 35.2 节旅行商问题近似算法（如利用三角不等式的 2 倍近似与 Christofides 3/2 近似）之前必备的知识铺垫。

• 文档
• 教程
• 示例工程