二分图

概述

二分图是顶点能划分成两个集合、使每条边的两端分属不同集合的无向图，等价于用两种颜色就能给全图正常染色。一个图是二分图当且仅当它不含奇环，因此可用黑白染色法判定：从任一未染色点出发遍历，给相邻点染上相反颜色，一旦发现某条边两端同色，就说明存在奇环，不是二分图。染色只需遍历一遍全图，复杂度 O(n+m)。二分图的最大匹配、最大权匹配等进一步内容另见图匹配一节，此页仅交代判定。

参考资料

• 二分图 - OI Wiki

简介

二分图（Bipartite Graph）的顶点可分成两个集合，使每条边的两端分属不同集合，等价于图中不存在奇环，用黑白染色法可 $O(n+m)$ 判定。

二分图的最大匹配、最大权匹配等见 图匹配。