1.定义
一个二分图满足有一种划分方案使得它节点的被分为两部分，且所有边的端点所在的部分不相同。即每条边都连接两个部分。
变量说明：没有特殊说明时，\(n\) 表示 a 部分点数，\(m\) 表示 b 部分点数，\(e\) 表示边数。
2.判定
显然我们给二分图染色，确定一个点所有点都确定。如果在染的时候发现冲突就代表不是二分图。复杂度 \(O(n+m+e)\)。
一张图是二分图当且仅当其中间没有奇环。
证明：
-
奇环本身就不能染成二分图。
-
如果没有奇环，我们需要找出两条从 \(s\) 到 \(t\) 的路径使得通过这两道路径会让 \(t\) 的颜色产生冲突。
-
很明显就是使这两条路径长度奇偶性不同。
-
因为有两条路径，这两条路径一定形成一个环，因为没有奇环，所以这两个路径长度加起来为偶数，所以这两个路径奇偶性相等。
-
也就是说没有奇环的图一定是二分图。