二分图

二分图是能把顶点分成两组、且每条边都横跨两组的无向图。设 $G = (V, E)$ ，若存在互不相交的 $L, R$ ，满足 $V = L \cup R$ 且每条边的一端在 $L$ 、另一端在 $R$ ，就称 $G$ 为二分图。两组可以有一组为空；孤立顶点放在哪边都不影响条件。

从分组读出图的结构

假设三位学生 $a, b, c$ 与三项任务 $1, 2, 3$ 构成图，边 $a 1, a 2, b 1, c 2, c 3$ 表示“能够承担”。取 $L = {a, b, c}$ 、 $R = {1, 2, 3}$ ，每条边连接学生和任务，所以是二分图。图中的实线还展示了一组可以同时完成的指派；虚线表示虽可承担、但这一次没有选用的边。

左侧三人a、b、c与右侧任务1、2、3构成二分图，实线选择b1、a2、c3，虚线保留a1、c2 — 每条边都横跨左右两组；实线互不共端点，因而也构成一组全覆盖匹配。

$a$ 同时认识 $b$ 是否相关？不相关；当前图只记录可承担关系。若添上学生间边 $a b$ ，原分组就不再合格，且此时 $a - b - 1 - a$ 构成三角形，所以不存在别的二分分组。

一种不依赖画法的判据是：无向图是二分图，当且仅当它不含奇数长度的环。若已经分成 $L, R$ ，沿每条边都会换组，走完一个环回到出发组必须换偶数次，因此奇环不可能存在。反方向可对每个连通分量任选起点，把距起点的偶数长度最短路可达的顶点置于一组，奇数长度者置于另一组。若有一条边连接同组两点，两条从起点到端点的搜索路径连同这条边会产生奇数闭合行走；去掉其中重复部分后可抽出奇环，矛盾。故没有奇环时，每条边都跨组。这也给出了广度优先搜索的二着色检验。

三角形与四边形

三角形的三条边形成长度为 3 的环，无法在两组之间交替走三次又回到起点，所以不是二分图。四边形 $a - b - c - d - a$ 可分成 ${a, c}$ 与 ${b, d}$ ；加对角线 $a c$ 后出现三角形 $a - b - c - a$ ，就不再是二分图。这个例子说明顶点个数为偶数并非判据；关键是所有环的奇偶性。

匹配与完全二分图

在图中的学生与任务例子里， $b 2$ 根本不是边，因此不可把 $b$ 指派给任务 2。选择 $b 1, a 2, c 3$ 则得到大小为 3 的匹配，左侧三人各得一项任务。二分图让“人—任务”“课程—教室”等两类对象的配对问题有了准确语言，但存在边只表示允许，不保证所有左侧顶点都能同时配到不同右侧顶点。例如若三人都只连向同一项任务，图仍是二分图，却至多只能选一条边。

若任意 $u \in L$ 、 $v \in R$ 之间都有边，就得到完全二分图 $K_{m, n}$ ，其中 $m = | L |$ 、 $n = | R |$ ，边数为 $m n$ 。例如 $K_{2, 3}$ 有 6 条边，仍没有三角形；“完全”只表示所有跨组边都在，不表示组内有边。

作为检查，可把四边形的一条边删掉，得到四个顶点的链。沿链从一端开始交替涂两色，仍是二分图；再把链两端接起来恢复四边形，也仍是二分图。若在四边形上添一条对角线，立即出现奇环。这个小实验把判据中的“所有环”落到具体边上：没有环的树无论形状如何都必是二分图。

参考资料