二分图最小点覆盖问题的 König 定理算法 题目描述 ： 给定一个 无向二分图 \( G = (U, V, E) \)，我们需要找到最小的点覆盖。点覆盖是指一个顶点集合，使得图中的每条边至少有一个端点属于这个集合。二分图最小点覆盖问题是：在所有点覆盖中，找到包含顶点数最少的一个。König 定理指出，在二分图中，最小点覆盖的大小等于最大匹配的大小，并且我们可以从最大匹配构造出具体的最小点覆盖。题目要求：给定一个二分图，求出其最小点覆盖的顶点集合。 解题过程循序渐进讲解 ： 步骤1：理解 König 定理的核心结论 König 定理包含两个部分： 在任意二分图中，最小点覆盖的大小 = 最大匹配的大小。 可以从一个已知的最大匹配，通过以下方法构造出最小点覆盖： 在二分图中，从未匹配的左边顶点（U 中）出发，沿着“非匹配边 → 匹配边 → 非匹配边 → …”的交替路径进行 DFS/BFS 标记。 最小点覆盖 = (U 中未被标记的顶点) ∪ (V 中被标记的顶点)。 步骤2：为什么这个定理成立？直观理解 最大匹配的每条边至少需要一个端点来覆盖它。如果覆盖边数等于匹配数，那么每个覆盖点必须覆盖一条不同的匹配边。König 的构造方法实际上找到了这样一个覆盖：从左边未匹配点出发，能到达的所有顶点构成了一个集合，未被标记的左边顶点和已被标记的右边顶点正好覆盖了所有边。 步骤3：算法详细步骤 假设二分图分左右两部分：左顶点集 \( U \)，右顶点集 \( V \)。 求最大匹配 使用匈牙利算法（或 Hopcroft–Karp 算法）求出最大匹配 \( M \)，并记录每个顶点的匹配对象（若无匹配则为空）。 构造顶点覆盖 初始化标记数组： markU[U] = false ， markV[V] = false 。 从 \( U \) 中 所有未匹配的顶点 出发，进行 DFS 或 BFS 遍历，遍历规则如下： 从 \( u \in U \) 出发时，只能走 非匹配边 到 \( v \in V \)。 从 \( v \in V \) 出发时，只能走 匹配边 到 \( u \in U \)。 在遍历过程中，将访问到的 \( U \) 中的顶点标记为 markU[u] = true ，访问到的 \( V \) 中的顶点标记为 markV[v] = true 。 最终，最小点覆盖的顶点集合为： \[ \{ u \in U \mid \text{markU}[ u] = \text{false} \} \cup \{ v \in V \mid \text{markV}[ v ] = \text{true} \} \] 步骤4：示例演示 考虑二分图： \( U = \{u1, u2, u3\} \) \( V = \{v1, v2, v3\} \) 边：\( (u1,v1), (u1,v2), (u2,v2), (u2,v3), (u3,v2) \) 最大匹配 \( M = \{(u1,v1), (u2,v2)\} \)（大小=2）。 按步骤： 未匹配的左边顶点：\( u3 \)。 从 \( u3 \) 出发： 走非匹配边到 \( v2 \)（边 \( (u3,v2) \) 是非匹配边），标记 \( u3, v2 \)。 从 \( v2 \) 只能走匹配边到 \( u2 \)（因为 \( (u2,v2) \) 是匹配边），标记 \( u2 \)。 从 \( u2 \) 走非匹配边到 \( v3 \)（边 \( (u2,v3) \) 是非匹配边），标记 \( v3 \)。 从 \( v3 \) 没有匹配边出去，停止。 标记结果： markU: u2=true, u3=true, u1=false ； markV: v2=true, v3=true, v1=false 。 最小点覆盖 = \( \{u \in U \mid \text{markU}[ u]=false\} \) 即 \( \{u1\} \) ∪ \( \{v \in V \mid \text{markV}[ v ]=true\} \) 即 \( \{v2,v3\} \) = \( \{u1, v2, v3\} \)。 验证：边 \( (u1,v1) \) 被 u1 覆盖，\( (u1,v2) \) 被 u1 或 v2 覆盖，\( (u2,v2) \) 被 v2 覆盖，\( (u2,v3) \) 被 v3 覆盖，\( (u3,v2) \) 被 v2 覆盖。覆盖大小=3，与最大匹配大小=2 相等（注意 König 定理说的是“大小相等”，这里覆盖大小=3？等一下，我们检查匹配大小实际上是2，但覆盖我们得到3，说明匹配不是最大？） 重新检查匹配：实际上最大匹配可以是 \( \{(u1,v1), (u2,v3), (u3,v2)\} \) 大小=3。之前我错误地取了一个大小为2的匹配。用正确的最大匹配 \( M=\{(u1,v1),(u2,v3),(u3,v2)\} \) 重新计算： 未匹配左边顶点：无。 从所有未匹配左边顶点出发（无），所以没有标记发生，所有 markU=false, markV=false。 最小点覆盖 = \( \{u\in U \mid false\} = \emptyset \cup \{v\in V \mid false\} = \emptyset \)？这显然不对，因为需要覆盖所有边。 注意：当左边没有未匹配顶点时，应该从右边已匹配顶点出发吗？不，König 构造的标准流程是：从左边 所有 未匹配顶点出发标记。如果左边没有未匹配点，那么左边所有顶点都在匹配中，那么最小点覆盖就是 \( U \) 本身吗？检查：最大匹配大小=3，最小点覆盖大小也应是3，\( U \) 大小=3，所以最小点覆盖可以是 \( U \)。但我们的构造似乎没给出这个。 实际上，在标准算法中，如果左边没有未匹配点，那么从左边出发标记的顶点集合为空，于是“U 中未被标记的顶点”就是所有 U，“V 中被标记的顶点”为空，所以最小点覆盖 = U。这正好满足。 步骤5：算法正确性证明思路 证明这样选出的集合确实是一个点覆盖： 考虑任意边 \( (u,v) \)。如果 \( u \) 没有被标记且 \( v \) 没有被标记，那么 \( u \) 一定是从某个未匹配左边点可达的，矛盾。详细需分匹配边/非匹配边讨论，但结论是每条边至少有一个端点在集合内。 证明大小等于最大匹配： 因为构造中，每条匹配边恰好有一个端点被选入覆盖（左边未被标记或右边被标记，且不可能同时选两个），所以覆盖大小等于匹配数，由 König 定理，这就是最小可能的。 步骤6：算法复杂度 求最大匹配：匈牙利算法 \( O(|U||E|) \)，Hopcroft–Karp 算法 \( O(\sqrt{|U|}|E|) \)。 标记过程：一次 DFS/BFS \( O(|V|+|E|) \)。 总体复杂度由最大匹配部分决定。 步骤7：实现注意事项 需分别存储左、右顶点的邻接表。 匹配可以用数组 matchU[u] = v 和 matchV[v] = u 表示，-1 表示无匹配。 标记时注意避免重复访问。 这样，我们就得到了二分图最小点覆盖的具体构造方法，不仅知道大小，还能给出覆盖集合。