二部图

概述

二部图（Bipartite Graph）是一种特殊的图，其顶点集可划分为两个互不相交的子集，使得每条边的两个端点分别属于不同的子集。

定义

形式化定义

图 $G=(V,E)$ 称为二部图，当且仅当存在 $V$ 的一个划分 $V=L\cup R$（$L\cap R=\varnothing$），使得对每条边 $(u,v)\in E$，都有 $u\in L$ 且 $v\in R$（或反之）。

二部图通常记为 $G=(L,R,E)$，其中 $L$ 和 $R$ 分别称为左部和右部。

等价刻画

二部图有多种等价定义，以下条件互相等价：

1. 划分定义：$V$ 可划分为两个独立集 $L$ 和 $R$
2. 染色定义：$G$ 的色数（chromatic number）$\chi (G)\le 2$，即可以用两种颜色对顶点染色，使相邻顶点颜色不同
3. 奇环刻画：$G$ 不包含奇数长度的环（即不存在长度为奇数的回路）
4. 邻接矩阵刻画：适当排列顶点后，邻接矩阵可以写成 $\left(\begin{array}{cc}0& B\\ B^T& 0\end{array}\right)$ 的分块形式

判定方法

• BFS/DFS 染色法：从任意顶点出发，交替用两种颜色标记，若发现冲突（相邻顶点同色）则不是二部图。时间复杂度 $O(V+E)$

核心性质

• König 定理：在二部图中，最大匹配的边数 = 最小顶点覆盖的顶点数。这是二部图最重要的定理之一，将匹配问题与覆盖问题联系起来
• Hall 定理（Hall’s Marriage Theorem）：二部图 $G=(L,R,E)$ 存在完美匹配（$|L|$ 条边，覆盖 $L$ 中所有顶点），当且仅当对 $L$ 的每个子集 $S\subseteq L$，都有 $|N(S)|\ge |S|$，其中 $N(S)$ 是 $S$ 的邻居集
• 完全二部图 $K_{m,n}$ 有 $m\times n$ 条边

应用场景

• 二分匹配：二分匹配问题天然定义在二部图上，可通过添加超级源点和超级汇点转化为最大流问题
• 任务分配：将工人与任务分别放在 $L$ 和 $R$，边表示能力匹配
• 顶点覆盖的 2-近似算法：利用 König 定理，在二部图中通过最大匹配构造最小顶点覆盖，得到精确解；一般图中顶点覆盖是 NP 难的，但最大匹配给出 2-近似
• 课程安排：将课程与时间槽分别建模为二部图的两个部

参见

• 图论
• 完全图
• 最大流
• 二分匹配