OI-wiki 二分图专题定义、等价刻画与 O(|V||E|) 染色判定算法【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki二分图bipartite graph是图论中结构最简单、性质最优雅的图类之一它的顶点可以分成互不相交的两部分所有边都只连接这两个部分之间。得益于这种结构许多在一般图上难以解决的优化问题最大匹配、最小点覆盖、最大独立集等都能在二分图上高效求解。本文以 OI-wiki 的 bi-graph.md 为骨架系统讲解二分图的定义、两条等价刻画、基于染色的线性时间判定算法并结合仓库中的参考实现与测试用例给出可直接运行的完整代码最后梳理二分图相关的经典应用与进阶专题入口。引入二分图又称二部图是一类结构特殊的图。它的顶点集可以划分为两个互不相交的子集使得图中的每条边都连接这两个集合之间的一对点而不会连接同一集合内部的点。得益于这种简单的结构二分图不仅展现出许多优雅的性质也广泛应用于现实生活中的建模场景例如任务分配、推荐系统、匹配市场等。许多在一般图上困难的优化问题在二分图上都可以高效、准确地求解——这正是二分图在算法竞赛与图论研究中始终占据核心地位的原因。定义如果图 $G(V,E)$ 的顶点集 $V$ 可以分为两个互不相交的子集 $X$ 和 $Y$使得每条边 $e\in E$ 的两个端点都分别属于 $X$ 和 $Y$就称图 $G$ 是一个二分图bipartite graph。集合 $X$ 和 $Y$ 常称作它的两个部分part或者分别称为二分图的左部和右部。当二分图的两个部分 $X$ 和 $Y$ 已知时也可以用三元组 $(X,Y,E)$ 来表示二分图 $G$。一个典型的二分图如下图所示——红色圆点为左部顶点青色圆点为右部顶点所有边都横跨左右两个部分没有任何一条边落在同一部分内部。树、偶环、网格图等都是常见的二分图的例子。例如任意一棵树可以按深度奇偶性把顶点分到两侧网格图按格子坐标的奇偶性黑白染色后相邻格子的颜色必然不同因而也是二分图。这类直觉在后文的判定算法中会反复出现。等价刻画二分图除了上述的划分定义之外还可以由下列性质等价地定义图 $G$ 是可 2-着色的。也就是说可以用至多两种颜色给图的所有顶点染色并且保证相邻顶点颜色不同。图 $G$ 中不存在奇数长度的环简称奇环。这两条性质与划分定义是完全等价的理解它们是把判定一个图是不是二分图转化为可执行算法的关键。可 2-着色与定义直接等价第一条性质与二分图的定义直接等价只需要将二分图的两个部分各染一种颜色即可。反过来如果一张图能被两种颜色正常染色相邻顶点异色那么把同色顶点归为一类就自然得到了一个合法的二划分 $X$、$Y$。不含奇环构造性理解第二条性质稍微复杂一些。可以考虑用两种颜色尝试给图 $G$ 染色。因为不同连通分量之间染色互不干扰只需要逐个考虑连通分量就好了。任选连通分量中的一个顶点 $s$进行 DFS并记录连通分量中每个顶点 $v$ 与 $s$ 的距离。从 $s$ 开始在 DFS 生成树上进行归纳可知如果存在一种可行的染色方法一定是根据每个顶点 $v$ 到起点 $s$ 的距离的奇偶性分别染成两种颜色。继而考虑那些不在生成树中的边即非树边。如果这些非树边的两个端点的颜色都不一样就说明当前的染色方案可行否则就不存在可行的方案。进一步地两个顶点颜色不同当且仅当它们到树根 $s$ 的距离一奇一偶而这又等价于加入该非树边形成的是一个偶环而非奇环。因此只要没有奇环这些非树边必然连接颜色不同的点进而整张图都可以用两种颜色染色图就一定是二分图。简而言之这一小节建立起了如下的判定链存在二划分 ⇔ 可 2-着色 ⇔ 不含奇环其中可 2-着色直接给出了算法染色尝试不含奇环给出了图论直觉二者共同支撑起下一节的判定算法。判定算法二分图染色要判定一个图是不是二分图只需要利用上述等价刻画尝试给二分图染色即可。为此可以使用 DFS 或者 BFS 来遍历这张图。如果发现了奇环——也就是出现无法染色的情况——那么就不是二分图否则就是二分图。算法流程具体流程如下遍历顶点如果发现还没有染色的顶点说明发现了新的连通分量。任选一种颜色给该顶点染色并以它为起点做 DFS 或者 BFS尝试给该连通分量染色。遍历相邻的顶点时如果发现已经染色的顶点检查颜色是否与当前顶点相同相同则不是二分图直接返回否则继续遍历。如果发现尚未染色的顶点将尚未染色的顶点染上与当前顶点相反的颜色。由于两个部分之间的对称性第 1 步保证每个连通分量都会被访问到第 3 步负责抓住奇环一旦遇到同色相邻顶点即奇环出现的证据第 4 步则保证染色的传播方式唯一且一致染成相反颜色。参考实现与源码分析原文档中给出的参考代码如下完整可编译版本位于 check-bipartite.cpp文档正文通过--8--片段嵌入其core标注区间即第 4–36 行int n; std::vectorstd::vectorint gr; std::vectorint colors, vis; // Depth-first search to color vertices. bool dfs(int cr) { vis[cr] true; for (int nt : gr[cr]) { if (vis[nt]) { if (colors[cr] colors[nt]) return false; } else { colors[nt] colors[cr] ^ 1; if (!dfs(nt)) return false; } } return true; } // Check whether the graph GR is bipartite. // If so, the vector COLORS will store a feasible coloring. bool check_bipartite() { for (int i 1; i n; i) { // Check connected components one by one. if (!vis[i]) { colors[i] 0; if (!dfs(i)) return false; } } return true; }结合源码结构可以提炼出实现要点colors[nt] colors[cr] ^ 1是染色的核心一行用0/1两种颜色编码异或 1即翻转颜色正好对应染上与当前顶点相反的颜色实现简洁且无需分支。if (vis[nt]) { if (colors[cr] colors[nt]) return false; }对应算法流程第 3 步遇到已染色邻居时校验颜色是否冲突一旦发现同色相邻边等价于找到奇环立即返回false并提前终止。check_bipartite()中的外层循环对应流程第 1 步跳过已访问顶点每次从未染色的顶点重新开始一轮 DFS即逐个处理连通分量。图以邻接表gr存储n为顶点数main函数第 37–55 行支持多组测试数据按n m读入后建双向边最终输出Yes/No。测试用例验证仓库为这份代码配套了标准测试数据位于 check-bipartite.in 与 check-bipartite.ans共 10 组用例覆盖了多种关键形态长度为 4 的路径4 顶点 3 边→Yes三元环3 顶点 3 边→No最小的奇环完全二分图$K_{2,3}$ →Yes含奇环与孤立链的混合图6 顶点 5 边→No零边图5 顶点 0 边→Yes平凡二分图星形图10 顶点 9 边顶点 1 连接其余全部顶点→Yes长度为 11 的环→No奇环4×4 的网格图→Yes含偶环的图18 顶点 17 边→Yes完全二分图$K_{8,9}$ →Yes。将输入文件喂给上述参考程序输出应与答案文件完全一致第 3、4 组分别验证了奇环导致判定失败与偶环不影响判定这两个最核心的场景。这组用例同时验证了算法在处理多连通分量、零边图与大密度二分图时的正确性。时间复杂度整个判定过程对每个顶点和每条边各访问常数次因此时间复杂度为 $O(|V||E|)$空间复杂度为 $O(|V||E|)$存储邻接表。这是判定二分图问题的最优量级读取图本身就需要 $\Omega(|V||E|)$ 的时间。应用由于结构简单很多图论优化问题都可以在二分图上高效解决。以下应用在 OI-wiki 中均有对应的主条目可按需深入阅读极大团平凡二分图中不可能存在大小超过 2 的团因为任何三条边两两相连的顶点集必然引入同部连边因此极大团的处理非常直接。最小点着色平凡由 2-着色性质二分图的色数至多为 2无需复杂算法。最小边着色由 Vizing 定理的构造性证明二分图的最小边着色可用最大度数种颜色完成边色数恰为最大度 $\Delta$且证明过程本身是构造性的。最大匹配Kuhn 算法、Hopcroft–Karp 算法$O(|V|^{1/2}|E|)$以及归约为最大流的做法都以二分图染色得到的两部划分为前提当划分未知时正是用本文的染色算法在 $O(|V||E|)$ 时间内求出。最小边覆盖可借助最大匹配求解。最小点覆盖由 Kőnig 定理二分图最小点覆盖大小等于最大匹配大小且证明给出了构造方法。最大独立集由于点覆盖与独立集互为补集最大独立集同样归约为最大匹配问题。最大权匹配匈牙利算法Kuhn–Munkres 算法等可在带权二分图上求解最优匹配。二分图博弈一种与最大匹配及最大匹配关键点紧密相关的博弈模型常用于构造高级竞赛题目。可以看到判定一个图是否为二分图并求出其两部划分即本文主题是上述几乎所有应用的前置步骤例如 bigraph-match.md 明确说明若事先不清楚顶点集 $V$ 的划分方法可以通过本文第 判定 一节的染色算法在 $O(|V||E|)$ 时间内求出划分。小结二分图是结构简单但解法丰富的典型代表一条定义、两条等价刻画可 2-着色、不含奇环、一个 $O(|V||E|)$ 的染色判定算法即可支撑起最大匹配、最小点覆盖、最大独立集、边着色、带权匹配与博弈等一系列重要问题的求解。掌握本文的染色判定实现含 参考代码 与 配套测试数据就拥有了进入二分图匹配与相关图论专题的钥匙。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考