二分图的最大独立集问题（Maximum Independent Set in Bipartite Graphs） 题目描述 给定一个无向二分图 \( G = (U \cup V, E) \)，其中 \( U \) 和 \( V \) 是两个不相交的顶点集，边只存在于 \( U \) 和 \( V \) 之间。 最大独立集（Maximum Independent Set, MIS） 是指图中最大的顶点子集，使得该子集中任意两个顶点之间没有边相连。 要求找出二分图中的一个最大独立集，并输出其大小和具体顶点。 解题过程 步骤 1：理解独立集与图论概念的关系 独立集 ：顶点子集，其中任意两点无边相连。 最大独立集 ：在所有独立集中包含顶点数最多的一个。 补集关系 ：在一个图中，独立集的补集是一个 顶点覆盖 （Vertex Cover），即每条边至少有一个端点属于该集合。 König 定理 ：在二分图中， 最大匹配数 = 最小顶点覆盖数 。 因此， 最大独立集大小 = 顶点总数 - 最小顶点覆盖大小 。 步骤 2：问题转化 我们要找二分图的最大独立集，步骤为： 求出二分图的 最大匹配 （例如用匈牙利算法或 Hopcroft–Karp 算法）。 根据 König 定理，通过最大匹配构造一个 最小顶点覆盖 。 最大独立集 = 全体顶点 \ 最小顶点覆盖。 步骤 3：算法流程 1. 求最大匹配 使用 Hopcroft–Karp 算法（时间复杂度 \( O(\sqrt{V}E) \) ）或匈牙利算法（ \( O(VE) \) ）。 设匹配为 \( M \)，匹配大小为 \( |M| \)。 2. 通过最大匹配构造最小顶点覆盖 步骤： 从所有 未匹配的 \( U \) 顶点 出发，进行 DFS/BFS 寻找 交错路径 。 标记访问到的顶点： 从未匹配的 \( U \) 顶点出发，沿未匹配边走到 \( V \) 顶点； 再从 \( V \) 顶点沿匹配边走到 \( U \) 顶点； 重复直到无法继续。 最终得到的集合： 最小顶点覆盖 = （未访问的 \( U \) 顶点） ∪ （访问到的 \( V \) 顶点） 。 3. 计算最大独立集 最大独立集 = \( (U \cup V) \setminus \text{最小顶点覆盖} \)。 步骤 4：举例说明 图例 \( U = \{u1, u2, u3\} \)，\( V = \{v1, v2, v3\} \) 边： \( u1-v1, u1-v2, u2-v1, u2-v3, u3-v2 \) 求最大匹配 用匈牙利算法得到匹配：\( u1-v1, u2-v3 \)（大小 = 2）。 构造最小顶点覆盖 未匹配的 \( U \) 顶点：\( u3 \)。 从 \( u3 \) 出发： 沿未匹配边 \( u3-v2 \) 到 \( v2 \)（访问 \( v2 \)）。 从 \( v2 \) 沿匹配边？没有 \( v2 \) 的匹配边，停止。 标记访问的顶点：\( u3, v2 \)。 未访问的 \( U \) 顶点：\( u1, u2 \)。 访问到的 \( V \) 顶点：\( v2 \)。 最小顶点覆盖 = \( \{u1, u2, v2\} \)。 最大独立集 全集 \( \{u1,u2,u3,v1,v2,v3\} \) 去掉 \( \{u1,u2,v2\} \) → \( \{u3, v1, v3\} \)。 验证：这三个顶点之间没有边（\( u3 \) 只连 \( v2 \)，\( v1 \) 只连 \( u1,u2 \)，\( v3 \) 只连 \( u2 \)）。 大小 = 3。 步骤 5：算法正确性解释 König 定理保证了最小顶点覆盖大小等于最大匹配大小。 构造方法基于 二分图的交替路径标记 ，能正确找到最小顶点覆盖。 独立集 = 顶点覆盖的补集，因为每条边至少一端被覆盖，去掉覆盖顶点后剩下的顶点之间必然没有边。 步骤 6：复杂度 主要取决于求最大匹配的算法： Hopcroft–Karp：\( O(\sqrt{V} E) \)。 构造最小顶点覆盖只需一次 DFS/BFS：\( O(V+E) \)。 总复杂度与最大匹配算法相同。 步骤 7：扩展思考 此方法仅适用于 二分图 。一般图的最大独立集是 NP-hard 问题。 在二分图中，最大独立集问题通过匹配转化为多项式可解问题，是组合优化的经典例子。