xxx 最小点覆盖问题（二分图上的匈牙利算法应用） 题目描述 最小点覆盖问题是指在给定的无向图中，找到一个顶点集合，使得图中的每条边至少有一个端点在这个集合中，同时要求这个集合的顶点数量尽可能少。在二分图中，这个问题可以通过 König 定理转化为二分图的最大匹配问题，并利用匈牙利算法高效求解。 解题过程 1. 问题分析 最小点覆盖定义 ：在无向图 \( G = (V, E) \) 中，点覆盖 \( C \subseteq V \) 满足每条边 \( e \in E \) 至少有一个端点在 \( C \) 中。最小点覆盖是满足该条件的顶点数最少的集合。 二分图性质 ：在二分图 \( G = (X \cup Y, E) \) 中，König 定理指出最小点覆盖的顶点数等于最大匹配的边数。 关键思路 ：通过匈牙利算法求出二分图的最大匹配 \( M \)，然后利用匹配结果构造最小点覆盖。 2. 匈牙利算法求最大匹配 步骤1 ：初始化匹配 \( M \) 为空。 步骤2 ：对左侧顶点集 \( X \) 中的每个未匹配顶点，尝试通过增广路径扩展匹配： 使用 DFS 或 BFS 搜索从该顶点出发的增广路径（交替路径，以未匹配边开始和结束）。 若找到增广路径，则沿路径翻转边的匹配状态，使匹配数增加 1。 步骤3 ：重复步骤2直至无法找到新的增广路径，此时 \( M \) 为最大匹配。 3. 构造最小点覆盖 步骤1 ：从左侧未匹配的顶点出发，进行交替路径搜索（类似匈牙利算法中的搜索）： 标记所有可通过交替路径（未匹配边 → 匹配边 → 未匹配边 → …）访问到的顶点。 步骤2 ：根据标记结果构造点覆盖集合 \( C \)： 包含所有 未被标记 的左侧顶点 \( x \in X \)。 包含所有 被标记 的右侧顶点 \( y \in Y \)。 验证 ：集合 \( C \) 覆盖所有边，且其大小等于最大匹配的边数 \( |M| \)。 4. 示例说明 考虑二分图 \( X = \{A, B, C\}, Y = \{D, E, F\} \)，边集 \( E = \{(A,D), (A,E), (B,E), (C,F)\} \)： 使用匈牙利算法找到最大匹配 \( M = \{(A,D), (B,E), (C,F)\} \)。 从左侧未匹配顶点（无）开始标记： 假设从任意点开始，标记所有可通过交替路径访问的顶点（此例中无未匹配点，标记为空）。 构造点覆盖： 左侧未被标记的顶点：\( \{A, B, C\} \)。 右侧被标记的顶点：无。 最小点覆盖 \( C = \{A, B, C\} \)，大小等于 \( |M| = 3 \)。 关键点总结 König 定理将二分图的最小点覆盖问题转化为最大匹配问题。 匈牙利算法不仅用于求最大匹配，还通过顶点标记机制直接导出最小点覆盖。 该方法的时间复杂度取决于匈牙利算法，通常为 \( O(|V| \cdot |E|) \)。