形式陈述

图 $G=(V,E)$$G=(V,E)$ 称为二分图，若存在不交划分

$$ V=L\dot\cup R $$$$V=L\dot{\cup }R$$

使每条边都有一个端点在 $L$$L$、另一个端点在 $R$$R$。等价地，$G$$G$ 可用两种颜色进行正常顶点着色；又等价于 $G$$G$ 不含奇长度圈。

直觉

二分图把顶点分成两类，边只连接异类对象。沿路每走一步颜色必须翻转，因此绕一圈回到起点需要偶数步。

例子与边界

树都是二分图，可按到根距离的奇偶分层。三角形不是二分图，因为三条边无法只用两色正常着色。一个图可能有多个二分划分；每个连通分量选择一侧颜色后，另一侧被确定，孤立点可任意放置。

推论与应用

二分图建模任务—机器、学生—课程等两类对象关系，并使匹配、顶点覆盖和网络流拥有特殊结构。BFS 的奇偶层可在线性时间判定二分性并在失败时恢复奇圈证据。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，§1.6。
• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，Ch. 12。