二分图

概念

假设 \(G=(V,E)\) 是一个无向图，若点集 \(V\) 可以分解成互不相交的子集 \((A,B)\)，并且图中所有边 \((i,j)\) 的端点 \(i\)、\(j\) 分别属于子集 \(A\)、\(B\)，则称 \(G\) 是一个二分图

定理：一张无向图时二分图，当且仅当图中不存在奇环。

染色法判定一个图是否是二分图

从其中一个点开始，将跟他链接的点染成与其不同的颜色，如果连接的点有颜色相同的，则说明不是二分图，每次用 bfs 遍历即可。

先补充一些概念：

• 匹配：无共同点的边的集合。
• 匹配数：边集中边的个数。
• 最大匹配：匹配数最大的匹配。