二分图最小顶点覆盖问题的 König 定理算法 问题描述 给定一个 无向二分图 \( G = (U, V, E) \)，其中 \( U \) 和 \( V \) 是两个不相交的顶点集合，\( E \) 是边集。 最小顶点覆盖 ：寻找一个顶点集合 \( C \subseteq U \cup V \)，使得图中每条边至少有一个端点属于 \( C \)，且 \( |C| \) 最小。 König 定理指出： 在二分图中，最小顶点覆盖的大小等于最大匹配的大小 。 本题要求： 利用 König 定理，通过最大匹配构造出具体的最小顶点覆盖方案 。 解题思路 König 定理不仅给出了最小顶点覆盖的 大小 （等于最大匹配大小），还提供了一个构造性证明，能够从最大匹配出发，通过以下步骤找到具体覆盖集合： 求出二分图的一个 最大匹配 \( M \)。 从所有 未匹配的左侧顶点 出发，进行交替路径搜索（类似匈牙利算法中的DFS）。 标记访问过的顶点。 最终最小顶点覆盖为： 左侧未标记的顶点 ∪ 右侧标记的顶点 。 详细步骤 步骤1：求最大匹配 使用任意二分图最大匹配算法（如匈牙利算法或 Hopcroft-Karp 算法）得到一组最大匹配 \( M \)。 假设我们得到匹配边集 \( M \)，并记录每个顶点的匹配对象（若未匹配则为空）。 示例图 （方便后续说明）： \( U = \{u_ 1, u_ 2, u_ 3, u_ 4\} \) \( V = \{v_ 1, v_ 2, v_ 3, v_ 4\} \) 边：\( (u_ 1,v_ 1), (u_ 1,v_ 2), (u_ 2,v_ 2), (u_ 2,v_ 3), (u_ 3,v_ 3), (u_ 4,v_ 3), (u_ 4,v_ 4) \) 最大匹配 \( M = \{ (u_ 1,v_ 1), (u_ 2,v_ 2), (u_ 3,v_ 3) \} \)（大小为3） 步骤2：构建方向图 为了进行交替路径搜索，将原图转化为 有向图 ： 对于每条匹配边 \( (u,v) \in M \)，添加有向边 \( u \to v \)（从左侧到右侧）。 对于每条非匹配边 \( (u,v) \notin M \)，添加有向边 \( v \to u \)（从右侧到左侧）。 这样构造的有向图可以方便地进行“交替路径”搜索（匹配边→非匹配边→匹配边…）。 步骤3：从所有未匹配的左侧顶点出发DFS 初始化标记数组： visitedU （标记左侧顶点）， visitedV （标记右侧顶点），初始均为 false 。 遍历所有左侧顶点 \( u \in U \)，如果 \( u \) 在最大匹配中 未匹配 ，则从 \( u \) 开始进行DFS（或BFS）。 DFS规则（在有向图中）： 当前在左侧顶点 \( u \)：遍历所有从 \( u \) 出发的有向边（即匹配边 \( u \to v \)），如果 \( v \) 未访问，则标记 visitedV[v]=true 并递归进入 \( v \)。 当前在右侧顶点 \( v \)：遍历所有从 \( v \) 出发的有向边（即非匹配边 \( v \to u \)），如果 \( u \) 未访问，则标记 visitedU[u]=true 并递归进入 \( u \)。 这个DFS实际上是在寻找 交替路径 ，即从未匹配左侧顶点出发，经过非匹配边→匹配边→非匹配边…所能到达的所有顶点。 步骤4：标记结果解释 所有被访问的顶点是：从某个未匹配左侧顶点出发，通过交替路径能到达的顶点。 根据König定理的构造： 最小顶点覆盖 = （左侧未被标记的顶点）∪ （右侧被标记的顶点） 。 为什么这样构造是对的？ 左侧未被标记的顶点：说明从任何未匹配左侧顶点都无法通过交替路径到达它，这意味着它在匹配中且所有邻接的右侧顶点都未被标记（否则会被访问）。这些顶点必须被选入覆盖，以覆盖它们的匹配边。 右侧被标记的顶点：说明它可以从某个未匹配左侧顶点通过交替路径到达，因此它连接着一些未覆盖的边（通过非匹配边连接到左侧被标记顶点），需要被选入覆盖。 这两部分的并集恰好覆盖所有边，且大小等于最大匹配数。 步骤5：示例执行 对示例图： 最大匹配 \( M \)：\( u_ 1-v_ 1, u_ 2-v_ 2, u_ 3-v_ 3 \)。 未匹配左侧顶点：\( u_ 4 \)。 从 \( u_ 4 \) 开始DFS： \( u_ 4 \) 未匹配，无法走匹配边（无出边），DFS结束？ 注意 ：在有向图中，从左侧顶点只能沿匹配边走到右侧，但 \( u_ 4 \) 无匹配边，所以实际上不会标记任何顶点。但标准算法中，我们是从未匹配左侧顶点出发，尝试走 非匹配边 ？这里要小心：在构造的有向图中，从未匹配左侧顶点没有出边（因为匹配边不存在），所以DFS直接结束。 因此，只有 visitedU[u4]=true （因为起始点被访问），其他顶点均未标记。 根据规则： 左侧未被标记的顶点：\( u_ 1, u_ 2, u_ 3 \)。 右侧被标记的顶点：无。 最小顶点覆盖 = \(\{u_ 1, u_ 2, u_ 3\}\)，大小=3，与最大匹配大小相同。 检查：边 \( (u_ 4,v_ 3) \) 是否被覆盖？\( u_ 4 \) 不在覆盖中，\( v_ 3 \) 也不在覆盖中，但边 \( (u_ 4,v_ 3) \) 的端点 \( v_ 3 \) 是否被标记？根据DFS，\( u_ 4 \) 无匹配边，所以不会走到 \( v_ 3 \)。但注意，我们的覆盖集合是 \(\{u_ 1,u_ 2,u_ 3\}\)，这条边未被覆盖！这说明我的示例执行有误。 纠正 ：实际算法中，DFS不是直接在原图做，而是在 有向图 中从 未匹配左侧顶点 出发，但需要正确构造有向图： 匹配边方向 \( u \to v \)（对 \( M \) 中所有边）。 非匹配边方向 \( v \to u \)（对所有不在 \( M \) 中的边）。 然后从未匹配左侧顶点开始DFS，但注意：从未匹配左侧顶点，它没有出边（因为匹配边不存在），所以DFS不会继续。这会导致标记很少的顶点。 正确步骤 （经典描述）： 找到最大匹配 \( M \)。 从所有 未匹配的左侧顶点 出发，寻找 交替路径 （交替经过非匹配边和匹配边），并标记所有访问到的顶点。 实现时，可以从左侧未匹配顶点开始，走 非匹配边 到右侧，然后从右侧走 匹配边 回到左侧，如此交替。 标记所有在交替路径上的顶点（包括起点）。 最小顶点覆盖 = \(\{\)左侧未被标记的顶点\(\} \cup \{\)右侧被标记的顶点\(\}\)。 重新执行示例 ： 匹配 \( M = \{(u1,v1),(u2,v2),(u3,v3)\} \)。 未匹配左侧顶点：\( u4 \)。 从 \( u4 \) 开始交替路径搜索： 走非匹配边：\( u4 \to v3 \)（非匹配边），标记 \( v3 \)。 从 \( v3 \) 走匹配边：\( v3 \to u3 \)（匹配边方向是 \( u3\to v3 \)，但交替路径中，从右侧走匹配边回左侧，即 \( v3 \to u3 \)），标记 \( u3 \)。 从 \( u3 \) 走非匹配边：无其他非匹配边，停止。 标记集合：左侧 \( \{u4, u3\} \)，右侧 \( \{v3\} \)。 左侧未被标记的顶点：\( u1, u2 \)。 右侧被标记的顶点：\( v3 \)。 最小顶点覆盖 = \( \{u1, u2, v3\} \)，大小=3。 检查：边集每条边至少有一个端点在 \(\{u1,u2,v3\}\) 中，例如 \( (u4,v3) \) 被 \( v3 \) 覆盖，\( (u4,v4) \) 呢？\( u4 \) 不在，\( v4 \) 不在，但 \( (u4,v4) \) 未被覆盖！这说明还有问题。 再次纠正 ：交替路径的定义是：从未匹配左侧顶点开始，先走 非匹配边 ，然后走匹配边，再走非匹配边…。在搜索时，我们只标记 能通过这种交替路径到达的顶点 。但实现时，常用以下方法： 从所有未匹配左侧顶点出发， 只沿非匹配边 走到右侧顶点，并标记这些右侧顶点。 然后从这些右侧顶点， 只沿匹配边 走到左侧顶点，并标记这些左侧顶点。 重复1和2直到无法继续。 这等价于在 二部图 上做BFS：队列初始为所有未匹配左侧顶点，步骤： 从左侧顶点出发，沿非匹配边到右侧顶点（如果未访问），标记并加入队列。 从右侧顶点出发，沿匹配边到左侧顶点（如果未访问），标记并加入队列。 最终标记所有可达顶点。 对示例 ： 未匹配左侧：\( u4 \)。 从 \( u4 \) 走非匹配边：可到 \( v3, v4 \)（因为边 \( (u4,v3),(u4,v4) \) 是非匹配边）。标记 \( v3,v4 \)。 从 \( v3 \) 走匹配边：到 \( u3 \)（因为 \( (u3,v3) \) 是匹配边）。标记 \( u3 \)。 从 \( v4 \) 走匹配边：无（\( v4 \) 未匹配）。 从 \( u3 \) 走非匹配边：无（\( u3 \) 只有匹配边 \( (u3,v3) \) 已访问过）。 最终标记：左侧 \( \{u4,u3\} \)，右侧 \( \{v3,v4\} \)。 左侧未标记：\( u1,u2 \)。 右侧标记：\( v3,v4 \)。 最小顶点覆盖 = \( \{u1,u2,v3,v4\} \)？大小=4，但最大匹配大小=3，不对。 错误原因 ：我混淆了标记规则。经典König构造是： 最小顶点覆盖 = （左侧未访问的顶点） ∪ （右侧已访问的顶点） 。 其中“访问”是指从 未匹配左侧顶点 通过交替路径能到达的顶点（BFS/DFS）。 但BFS时，我们从左侧顶点只能通过 非匹配边 走到右侧，从右侧顶点只能通过 匹配边 走到左侧。 这样，访问集是： 初始：所有未匹配左侧顶点被访问。 扩展：从左侧走非匹配边到右侧；从右侧走匹配边到左侧。 对示例： 初始访问左侧：\( u4 \)。 从 \( u4 \) 走非匹配边到右侧：\( v3,v4 \) 被访问。 从 \( v3 \) 走匹配边到左侧：\( u3 \) 被访问。 从 \( v4 \) 走匹配边：无。 从 \( u3 \) 走非匹配边：无。 访问集：左侧 \( \{u4,u3\} \)，右侧 \( \{v3,v4\} \)。 左侧未访问：\( u1,u2 \)。 右侧已访问：\( v3,v4 \)。 覆盖 = \( \{u1,u2,v3,v4\} \)（大小4）≠最大匹配大小3，说明这个覆盖不是最小的？但König定理说最小覆盖大小等于最大匹配大小（3），所以我的最大匹配可能不是最大的？ 检查：图中最大匹配可以是 \( \{(u1,v1),(u2,v2),(u4,v4)\} \) 也是3，或者 \( \{(u1,v2),(u2,v3),(u4,v4)\} \) 也是3。我最初选的 \( \{(u1,v1),(u2,v2),(u3,v3)\} \) 是最大匹配吗？边数3，但有没有4的匹配？尝试：\( (u1,v1),(u2,v3),(u3,?),(u4,v4) \) 不可能同时。所以最大匹配大小确实是3。那么我的覆盖大小是4，说明构造错误。 查阅标准算法 ： 正确步骤（来自经典资料）： 求最大匹配 \( M \)。 从 所有未匹配的左侧顶点 出发，进行交替路径搜索（ 交替走未匹配边和匹配边 ），并标记所有访问到的顶点。 注意：从未匹配左侧顶点，第一步走的是 未匹配边 （因为从左侧到右侧的边，如果不在匹配中，就是未匹配边）。 然后从右侧顶点，走 匹配边 回左侧（如果存在）。 重复。 设 \( Z \) = 所有从 未匹配左侧顶点 通过交替路径可达的顶点。 最小顶点覆盖 = \( (U \setminus Z) \cup (V \cap Z) \)。 即：左侧不在Z中的顶点 + 右侧在Z中的顶点。 对示例 （匹配 \( M=\{(u1,v1),(u2,v2),(u3,v3)\} \)）： 未匹配左侧顶点：\( u4 \)。 从 \( u4 \) 开始交替路径： 走未匹配边到 \( v3 \)（访问 \( v3 \)）。 从 \( v3 \) 走匹配边到 \( u3 \)（访问 \( u3 \)）。 从 \( u3 \) 走未匹配边？无。 从 \( u4 \) 走未匹配边到 \( v4 \)（访问 \( v4 \)）。 从 \( v4 \) 走匹配边？无。 访问集 \( Z = \{u4, v3, u3, v4\} \)。 \( U \setminus Z = \{u1,u2\} \)。 \( V \cap Z = \{v3,v4\} \)。 覆盖 = \( \{u1,u2,v3,v4\} \)（大小4）→ 不是最小覆盖？矛盾。 这意味着我的匹配 \( M \) 可能不是最大匹配？实际上，存在匹配 \( \{(u1,v2),(u2,v3),(u4,v4)\} \) 大小3，但我的M也是3，所以都是最大匹配。但不同最大匹配导出的最小覆盖可能不同？不对，König定理说任何最大匹配都能导出最小覆盖，但构造必须正确。我的构造似乎得到覆盖大小4，说明我漏掉了某些可达顶点。 再仔细检查：从 \( u4 \) 到 \( v3 \) 后，\( v3 \) 的匹配边到 \( u3 \)，然后 \( u3 \) 还有其他未匹配边吗？没有。所以Z只有 \(\{u4,v3,u3,v4\}\)。那么覆盖 \(\{u1,u2,v3,v4\}\) 确实覆盖所有边吗？检查： (u1,v1): u1在覆盖中 ✓ (u1,v2): u1在 ✓ (u2,v2): u2在 ✓ (u2,v3): u2在 ✓ (u3,v3): v3在 ✓ (u4,v3): v3在 ✓ (u4,v4): v4在 ✓ 都覆盖了。但大小为4，比最大匹配大小3大，这说明这个覆盖不是最小的？但König定理说最小覆盖大小等于最大匹配大小（3），所以我的覆盖 \(\{u1,u2,v3,v4\}\) 不是最小的，那么存在更小的覆盖吗？尝试 \(\{u1,u2,u4\}\) 大小3，检查： (u3,v3) 未被覆盖 → 不行。 尝试 \(\{u2,u3,v1\}\) 大小3： (u1,v1): v1在 ✓ (u1,v2): 未被覆盖 → 不行。 所以似乎没有大小3的覆盖？但König定理保证一定有。我的图最大匹配真的是3吗？验证：匹配 \(\{(u1,v1),(u2,v3),(u4,v4)\}\) 大小3，是最大匹配吗？尝试找4的匹配：需要4条边无公共顶点，但左侧4个顶点，每个至少有一条边，可能吗？考虑匹配 \(\{(u1,v1),(u2,v2),(u3,v3),(u4,v4)\}\)，但(u3,v3)和(u4,v4)同时存在吗？(u3,v3)存在，(u4,v4)存在，但(u2,v2)存在，这样四条边无冲突，似乎是大小为4的匹配！我最初漏掉了这个。所以最大匹配大小是4，不是3。 因此，我一开始假定的最大匹配 \( \{(u1,v1),(u2,v2),(u3,v3)\} \) 不是最大的，因为可以加入 \( (u4,v4) \) 得到大小4的匹配。所以我的示例错误在于没有用真正的最大匹配。 修正示例 ：取真正最大匹配 \( M = \{(u1,v1),(u2,v2),(u3,v3),(u4,v4)\} \)。 未匹配左侧顶点：无。 因此Z为空（因为没有未匹配左侧顶点出发）。 左侧未访问 = \( \{u1,u2,u3,u4\} \)。 右侧已访问 = 空。 最小顶点覆盖 = \( \{u1,u2,u3,u4\} \) 大小4，等于最大匹配大小4。 这符合König定理。 最终算法总结 使用匈牙利算法或Hopcroft-Karp算法求出二分图的最大匹配 \( M \)。 进行交替路径BFS/DFS： 初始化队列，包含所有在 \( M \) 中 未匹配 的左侧顶点，并标记它们为已访问（左侧）。 BFS过程： 从左侧顶点 \( u \)：遍历所有与 \( u \) 相邻的右侧顶点 \( v \)，若边 \( (u,v) \) 不在 \( M \) 中，且 \( v \) 未访问，则标记 \( v \) 并加入队列（作为右侧已访问）。 从右侧顶点 \( v \)：若 \( v \) 在 \( M \) 中有匹配边 \( (u,v) \)，且 \( u \) 未访问，则标记 \( u \) 并加入队列（作为左侧已访问）。 设 \( L \) 为左侧顶点集合，\( R \) 为右侧顶点集合。 最小顶点覆盖 = \( \{ u \in L \mid u \text{ 未被访问} \} \cup \{ v \in R \mid v \text{ 已被访问} \} \)。 输出该覆盖。 时间复杂度 ：取决于最大匹配算法，若用Hopcroft-Karp为 \( O(E \sqrt{V}) \)，构造覆盖的BFS为 \( O(V+E) \)，总复杂度相同。 关键点 König定理保证了二分图中最小顶点覆盖大小等于最大匹配大小。 该构造性算法不仅给出大小，还给出具体覆盖集合。 注意算法中的“访问”标记是从 未匹配左侧顶点 出发进行交替路径搜索得到的，不要混淆方向。