最小点覆盖（Minimum Vertex Cover）：在图中选最少的顶点，使每条边至少有一个端点被选中。一般图为 NP-难；在二分图上由 König 定理，最小点覆盖大小等于最大匹配大小，可在线性时间从最大匹配恢复一个最小点覆盖。
Description: Minimum vertex cover. NP-hard on general graphs; on bipartite graphs, by König’s theorem, min vertex cover size equals max matching size. Recover a minimum cover from any maximum matching via alternating-BFS. Time: Bipartite case: O(E√V) to find max matching (Hopcroft–Karp) + O(E) to recover cover Status: tested
展开阐述
-
问题与结论
- 一般图：求最小点覆盖为 NP-难（常用近似或分支限界）。
- 二分图：|最小点覆盖| = |最大匹配|（König 定理）；可由任一最大匹配构造一个最小点覆盖。
-
接口（据实现）
- 已有最大匹配（如由 067-图论-HopcroftKarp 得到 mateL, mateR）。
- minVertexCoverBipartite(nL, nR, adj, mateL, mateR) → {coverL, coverR}：
- 返回左侧需选的点集 coverL 与右侧需选的点集 coverR，二者并集为一个最小点覆盖。
-
构造算法（交替可达集）
- 取所有未匹配的左侧顶点为起点，建“交替图”做 BFS/DFS：
- 仅沿未匹配边从左→右、沿已匹配边从右→左前进。
- 记可达的左侧集合为 Z_L、右侧集合为 Z_R。
- 一个最小点覆盖即：cover = (Left \ Z_L) ∪ (Right ∩ Z_R)。
- 规模恰为最大匹配大小；正确性由 König 定理保证。
- 恢复复杂度 O(E)。
- 取所有未匹配的左侧顶点为起点，建“交替图”做 BFS/DFS：
-
输出语义
- 返回 bipartite 的一个最小点覆盖（coverL, coverR）。
- 其大小等于最大匹配条数；与072-图论-最大独立集互为补：|MIS| = |V| − |MVC|。
-
复杂度
- 匹配阶段：Hopcroft–Karp O(E√V)；恢复覆盖 O(E)。
-
使用与注意
- 仅对二分图成立：图需分左右两侧且只跨侧连边。
- 若只需覆盖大小，可直接取最大匹配大小；若需具体点集，按上述步骤恢复。
- 一般图最小点覆盖可转化为最小割仅在二分图设置下（匹配网络）成立；更一般的有向/费用版本参考074-图论-最小割与073-图论-最小费用最大流。