xxx 顶点覆盖问题（近似算法）

题目描述
给定一个无向图 G=(V, E)，顶点覆盖是指一个顶点集合 S ⊆ V，使得图中的每条边至少有一个端点在 S 中。顶点覆盖问题要求找出规模最小的顶点覆盖，即包含顶点数量最少的覆盖。这是一个经典的 NP-完全问题，因此我们通常使用近似算法来寻找接近最优的解。

解题过程

1. 问题理解
   顶点覆盖的目标是选择最少的顶点，使得每条边都被“覆盖”（即至少有一个端点被选中）。例如，在社交网络中，这可能相当于选择最少数量的监控点来覆盖所有通信链路。

2. 核心思路：贪心近似算法
   由于精确求解需要指数时间，我们采用一种简单的贪心策略：

   • 不断选择一条边，将其两个端点加入覆盖集，然后删除所有与这两个端点相连的边。
   • 该算法保证得到的顶点覆盖规模不超过最优解的 2 倍（即 2-近似算法）。

3. 算法步骤

   • 步骤 1：初始化空集合 cover 作为顶点覆盖，复制图的边集 remaining_edges = E。
   • 步骤 2：当 remaining_edges 非空时，重复以下操作：
     1. 从 remaining_edges 中任意选取一条边 (u, v)。
     2. 将 u 和 v 加入 cover。
     3. 删除所有与 u 或 v 相连的边（即删除包含 u 或 v 的边）。
   • 步骤 3：返回 cover。

4. 实例演示
   考虑一个简单图：顶点集 {A, B, C, D}，边集 {(A,B), (B,C), (C,D), (D,A), (A,C)}。

   • 第 1 轮：选择边 (A,B)，加入 A 和 B，删除边 (A,B)、(A,C)、(A,D)、(B,C)。剩余边：{(C,D)}。
   • 第 2 轮：选择边 (C,D)，加入 C 和 D，删除边 (C,D)。剩余边为空。
   • 最终覆盖为 {A, B, C, D}（规模为 4）。但最优解可能是 {A, C}（规模为 2），说明近似解可能不是最优，但规模不会超过最优的 2 倍。

5. 近似比证明

   • 算法每轮选择的边之间没有公共顶点（因为已删除关联边），这些边构成一个“匹配”（即没有共享顶点的边集）。
   • 最优覆盖必须至少包含每条匹配边的一个端点，而匹配边的数量等于算法选择边的数量。
   • 算法每轮添加 2 个顶点覆盖 1 条边，因此覆盖规模 ≤ 2 × 匹配边数 ≤ 2 × 最优覆盖规模。

6. 优化与变体

   • 实际应用中可优化边的选择顺序（如优先选择度数高的边），但最坏情况下的近似比仍为 2。
   • 另一种常用算法是基于线性规划舍入的近似方法，同样满足 2-近似比。

总结
顶点覆盖的贪心算法通过逐步覆盖边来构建解，虽然不一定最优，但保证了理论上的近似比，适用于大规模图的高效求解。