xxx 最小点覆盖问题（二分图上的匈牙利算法应用）

题目描述
在一个无向图中，点覆盖是一个顶点集合，使得图中的每条边都至少有一个端点在这个集合中。最小点覆盖问题就是要找到一个顶点数量最少的点覆盖。在一般的图中，这是一个NP难问题，但在二分图中，该问题存在多项式时间解法。给定一个二分图G = (X, Y, E)，其中X和Y是两部分顶点集合，E是边集，请利用匈牙利算法的结果，找出该二分图的最小点覆盖。

解题过程

1. 问题转换与理论基础
   在二分图中，最小点覆盖的大小等于最大匹配的大小（König定理）。因此，我们可以先通过匈牙利算法求出二分图的最大匹配M，然后基于匹配M构造出最小点覆盖集合S。

2. 使用匈牙利算法求最大匹配
   匈牙利算法通过寻找增广路径来逐步扩大匹配。

   • 初始化匹配M为空集。
   • 对X中的每个未匹配顶点u，尝试寻找一条从u出发的增广路径（路径交替经过非匹配边和匹配边，且终点为Y中的未匹配顶点）。
   • 若找到增广路径，则沿路径翻转匹配状态（非匹配边变为匹配边，匹配边变为非匹配边），从而增加匹配大小。
   • 重复直至无法找到新的增广路径。

3. 构造最小点覆盖集合
   设最大匹配为M，构造步骤：

   • 从X中所有未匹配的顶点出发，进行深度优先搜索（DFS）或广度优先搜索（BFS），标记所有能访问到的顶点。
     • 路径需满足交替特性：从X到Y只能走非匹配边，从Y到X只能走匹配边。
   • 最小点覆盖S = (X中未被标记的顶点) ∪ (Y中被标记的顶点)。

4. 算法正确性解释

   • König定理保证最小点覆盖大小等于最大匹配大小。
   • 上述标记过程确保了S覆盖所有边：
     • 若一条边的一端在X中被标记，另一端在Y中未被标记，该边可能是非匹配边，但Y端未被标记说明边未被覆盖？实际上需分类讨论：
       1. 匹配边：若匹配边(u,v)中u在X未被标记，则v在Y必被标记（因从u无法经匹配边到v），故v在S中；若u被标记，则v可能未被标记，但u不在S中，此时v是否在S？需结合规则：S包含X的未标记点和Y的标记点。
       2. 非匹配边：若边(u,v)中u在X被标记，则v在Y可能被标记（通过非匹配边），此时v在S中；若u未被标记，则u在S中。
   • 集合S的大小等于最大匹配大小，因为S中每个顶点唯一对应一条匹配边。

5. 示例演示
   考虑二分图：X={1,2,3}, Y={4,5,6}, 边集E={(1,4),(1,5),(2,5),(2,6),(3,5)}。

   • 步骤1：用匈牙利算法求最大匹配M，例如M={(1,4), (2,5)}。
   • 步骤2：从X的未匹配顶点3出发标记：
     从3经非匹配边(3,5)到5，从5经匹配边(5,2)到2。
     标记顶点：{3,5,2}。
   • 步骤3：S = (X中未标记的顶点{1}) ∪ (Y中标记的顶点{5}) = {1,5}。
   • 验证：边(1,4)、(1,5)被1覆盖；(2,5)、(2,6)被5覆盖；(3,5)被5覆盖。所有边被覆盖，且|S|=2=|M|。

关键点

• 该算法依赖二分图性质，一般图不适用。
• 时间复杂度由匈牙利算法主导，为O(VE)或优化后O(E√V)。