二分图的判定

记无向图 \(G = (V, E)\)，若存在点集 \(A,B\) 满足：

1. \(A \cup B = V\)
2. \(A \cap B = \varnothing\)
3. \(\forall e = (u,v) \in E\), 满足 \(u,v\) 不同时在 \(A\) 或 \(B\) 中。

则称图 \(G\) 为二分图，\(A,B\) 分别称作二分图的左部与右部。

二分图的判定定理

下面三个命题等价，可互相推出。

1. 图 \(G\) 是一个二分图，满足上述的可划分性。
2. 图 \(G\) 中不存在长度为奇数的环。
3. 图 \(G\) 可被二染色。

其中，\(1 \implies 2\) 因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合（from OI Wiki），\(3\) 中二染色表示可以把所有点染成两种颜色中的一种，对于 \(\forall e = (u,v) \in E\)，满足 \(u,v\) 的颜色不同。