1 定义与基本概念
二分图是图论中一种最基础也最常见的结构。它的核心特点是：顶点可以分成两个互不重叠的部分，且任意一条边都只能连接这两个部分中的不同顶点，而不会落在同一部分内部。正因为这种“二元分区”的形式，二分图常被用来描述配对、对应、关联和分工等关系。
1.1 图与顶点集划分
在一般图中，顶点之间可以任意连边；而在二分图里，顶点集首先被划分为两个集合，通常记作 \(U\) 和 \(V\)。划分的含义是每个顶点恰好属于其中一个集合，两个集合彼此没有交集。之后，图中的边只能从 \(U\) 连到 \(V\)，不能连接 \(U\) 内部两个点，也不能连接 \(V\) 内部两个点。
这种划分并不只是形式上的分组，它直接决定了图的结构。很多实际问题中，两个集合往往代表两类不同对象，例如“人”和“任务”“学生”和“课程”“产品”和“类别”等。
1.2 二分图的形式化定义
一个图若存在顶点集的划分 \(V(G)=U\cup V\)，且 \(U\cap V=\varnothing\)，并满足每条边都在 \(U\) 与 \(V\) 之间，则称该图为二分图。若图是有向图或带权图，通常仍先关注其底层无向结构是否满足这一条件。
从定义上看，二分图强调的是“边跨越两个部分”的限制，因此它天然排除了同部分内部的直接联系。这一限制使其在许多算法中更易处理，也为后续的匹配与覆盖理论奠定了基础。
1.3 二分图的等价表述
二分图除了按定义判断外，还可以通过其他等价方式识别。最常用的两种表述是可2-染色性和不含奇环。这些等价条件在理论证明和算法判定中都非常重要。
1.3.1 可2-染色性
若一个图的所有顶点都能用两种颜色着色，并且任意相邻两个顶点颜色不同，则该图是二分图。换句话说，二分图的两个顶点集可以看作两种颜色的集合。
这一性质在实际判定中非常直观：只要能将图“黑白相间”地染色而不冲突，就说明它具有二分结构。
1.3.2 不含奇环
一个图是二分图，当且仅当它不包含长度为奇数的简单环。这里的奇环指边数为 3、5、7 等奇数的回路。
这是二分图最经典的判别定理之一。其直观原因在于：沿着二分图中的边交替经过两个部分，走一圈返回起点时，回路长度必须是偶数，否则无法保持两部分交替的结构。
1.4 相关基础术语
理解二分图时，几个常用术语经常会同时出现，包括左右顶点集、邻接关系以及子图、诱导子图等。
1.4.1 左右顶点集
在二分图中，两个顶点部分常被习惯性地称为“左侧”和“右侧”，也可称为第一部和第二部。这个叫法更多是约定俗成，并不要求图在几何上真的具有左右方向。
这种称法便于描述匹配、流网络和矩阵表示等问题，尤其是在算法中常见。
1.4.2 邻接关系
如果一条边直接连接两个顶点，则称这两个顶点邻接。对于二分图而言，邻接关系只能发生在两个不同部分之间，同一部分内的顶点不会邻接。
邻接概念是构造路径、寻找匹配以及描述局部结构的基础。
1.4.3 子图与诱导子图
子图是从原图中选取部分顶点和部分边后得到的新图；诱导子图则是先选定一组顶点，再保留这组顶点之间在原图中原本存在的所有边。
二分图的任意子图仍然是二分图。诱导子图也继承这一性质，因此二分结构在局部上具有稳定性。
2 二分图的基本性质
二分图的结构相对简洁，因此具有许多清晰而稳定的性质。这些性质不仅便于理论研究，也为算法设计提供了便利。
2.1 结构性质
二分图最显著的特征就是边的连接方式受到严格限制。由此产生的整体结构往往呈现出一种“层次分明”的形态。
2.1.1 边的连接方式
在二分图中，每条边都连接两个不同部分的顶点。这意味着同一部分内部不会出现直接连接，因此图中不存在“局部闭合”的三角关系。
这种结构使得二分图特别适合表示两类对象之间的关系网络，例如人-任务、学生-课程、供应商-订单等。
2.1.2 连通二分图的分层特征
如果一个二分图是连通的，那么从任一顶点出发按距离分层时，层与层之间的顶点会交替落在两个部分中。也就是说，距离为偶数的顶点常与起点处在同一部分，距离为奇数的顶点则落在另一部分。
这一层次特征是二分图的重要直观表现，也常用于证明某些路径和环的性质。
2.2 染色性质
二分图的染色性质是其最经典的特征之一。由于只需要两种颜色即可完成合法着色，因此二分图与“二染色”紧密相关。
2.2.1 二染色方法
对一个连通图进行二染色时，通常从某个起点开始赋予一种颜色，再将其所有邻接点染成另一种颜色，之后继续向外扩展。如果过程中未出现冲突，就说明该图可以二染色。
这一过程与广度优先搜索非常接近，因此在算法实现上也很自然。
2.2.2 染色数与二分图
图的染色数是使相邻顶点不同色所需的最少颜色数。对于非空二分图而言，染色数不超过 2；若图至少包含一条边，则染色数恰为 2。
如果一个图的染色数为 1，则它只能是没有边的孤立点集合，这通常不被看作具有典型二分结构的情形。
2.3 回路性质
回路是判断二分图性质的重要线索。由于二分图中边必须跨部连接，回路长度会受到明显限制。
2.3.1 奇环与偶环
二分图中不允许出现奇环，但偶环是允许的。事实上，偶环是二分图中常见的基本回路形式之一。
奇环之所以被排除，是因为沿环行走时，顶点必须在两个部分之间交替出现，回到起点时边数只能是偶数。
2.3.2 二分图中的最短环
若二分图存在环，其最短环一定是偶环。最常见的短环是 4 环，也就是由四个顶点组成的闭合回路。
在一些稠密的二分图中，4 环十分普遍；而在树这种无环图中，则根本不存在回路。
2.4 度数与规模特征
二分图的顶点度数分布和边数规模通常会受到两侧顶点数量的限制，因此具有一些简单而实用的估计关系。
2.4.1 顶点度分布
在二分图中，某个顶点的度数等于它在另一侧顶点中的邻接个数。由于同侧不能连边，度数完全由对侧顶点决定。
这使得二分图中的度数统计常呈现明显的“左右对应”特征，特别是在建模问题里更为明显。
2.4.2 边数上界
若二分图两侧顶点数分别为 \(m\) 和 \(n\)，则边数最多不超过 \(mn\)。当每个左侧顶点都与每个右侧顶点相连时，便达到这个上界。
这个上界对应的就是完全二分图，也是二分图中最密集的一类。
3 特殊类型的二分图
二分图内部还有若干常见的特殊类型，它们在结构上更具规律性，便于研究和应用。
3.1 完全二分图
完全二分图是二分图中最规则的一类，其两侧顶点之间的连接最为完整。
3.1.1 定义与记号
若一个二分图的左侧有 \(m\) 个顶点、右侧有 \(n\) 个顶点，并且每个左侧顶点都与每个右侧顶点相连，则称其为完全二分图，记作 \(K_{m,n}\)。
在这种图中，同侧没有边，而异侧之间的所有可能边都被包含。
3.1.2 边数计算
完全二分图 \(K_{m,n}\) 的边数等于 \(mn\)。因为左侧每个顶点都要与右侧全部 \(n\) 个顶点连接，共有 \(m\) 组这样的连接。
这一简单公式使完全二分图常作为极值问题中的比较对象。
3.2 正则二分图
正则二分图是指每个顶点的度数都相同的二分图。它在组合结构中具有较强的均衡性。
3.2.1 k-正则二分图
若二分图中每个顶点的度都等于 \(k\)，则称其为 \(k\)-正则二分图。此时两侧顶点总数必须满足一定的平衡条件，否则无法实现每个点同度。
这类图常出现在均匀分配、对称设计和某些网络模型中。
3.2.2 典型例子
常见的正则二分图包括偶环、若干规则网格的局部结构，以及某些完全二分图。特别是 \(K_{n,n}\) 是 \(n\)-正则二分图的代表。
3.3 树与森林中的二分图
树和森林具有天然的二分结构，因此它们在图论中常被用作二分图的基础例子。
3.3.1 树的二分性
树是连通无环图。由于它不含任何环，尤其不含奇环，因此必然是二分图。实际操作中，只要从某点出发交替染色，就能得到树的二分划分。
树的这种性质在层次结构、家族关系和组织结构建模中经常出现。
3.3.2 森林的二分性
森林是若干棵树的并集，因此同样不含环。由此，森林也是二分图。
与树不同，森林可以由多个连通分量组成，但每个分量都可分别进行二分划分。
3.4 网格图与路径图
路径图和网格图是二分图中非常典型的结构，常用于离散空间和算法实例中。
3.4.1 路径图的二分结构
路径图由一串按顺序连接的顶点构成，边只连接相邻点。由于顶点可以按奇偶位置分成两类，因此路径图天然是二分图。
这类图常作为最简单的二分图示例，用于演示染色、匹配和搜索算法。
3.4.2 网格图的二分结构
网格图通常可以按棋盘格方式染色：相邻格点颜色不同，因此网格图往往具有明显的二分性。二维矩形网格尤其常见，其顶点可按坐标奇偶性分组。
4 经典定理
二分图理论中有若干核心定理，它们将结构性质与组合优化联系起来，构成了该领域的重要基础。
4.1 Hall婚配定理
Hall婚配定理是二分图匹配理论中最著名的结果之一，主要用于判断是否存在覆盖一侧顶点的匹配。
4.1.1 条件表述
| 设二分图左侧顶点集为 \(U\)，右侧为 \(V\)。若对任意左侧顶点子集 \(S\subseteq U\)，其邻接到右侧的顶点集合 \(N(S)\) 都满足 \( | N(S) | \ge | S | \)，则存在一个匹配，使得 \(U\) 中每个顶点都能被匹配到。 |
|---|
这个条件常被称为 Hall 条件，反映了“局部不拥挤”是全局可匹配的前提。
4.1.2 应用场景
Hall 定理常用于安排配对、分配岗位、组合选择等问题。只要能证明任意子集都不会“需求超过供给”，就能保证完备配对的存在。
4.2 König定理
König定理是二分图中匹配与覆盖关系的核心结论，揭示了两个看似不同的问题之间的精确等价。
4.2.1 最大匹配与最小点覆盖
在二分图中，最大匹配的大小等于最小点覆盖的大小。也就是说，能选出的最多互不冲突边数，恰好等于覆盖所有边所需的最少顶点数。
这是二分图的标志性定理之一，在一般图中并不成立。
4.2.2 二分图中的对偶关系
该定理体现了二分图在“选择边”与“选择点”之间的对偶平衡。它不仅有理论价值，也直接带来了高效算法，用于将匹配问题转化为覆盖问题，反之亦然。
4.3 Berge定理
Berge定理给出了判断匹配是否可以继续扩充的经典标准，尤其适合算法分析。
4.3.1 增广路判定
若一个匹配不存在增广路，则它已经是最大匹配。增广路指一条交替经过“未匹配边”和“已匹配边”的路径，并且两端点都是未匹配顶点。
这一判定在实际求最大匹配时极其重要，因为它把“是否最优”转化成“是否还能增广”。
4.3.2 匹配最优性
Berge 定理说明，匹配的最优性可以通过局部路径结构来验证，而不必穷举所有可能匹配。这也是很多匹配算法效率较高的根本原因。
4.4 相关推论
由上述定理可进一步得到若干常用结论，这些结论在二分图理论和应用中都十分实用。
4.4.1 完全匹配存在条件
如果二分图满足 Hall 条件，则一侧顶点集存在覆盖全部顶点的匹配；若两侧顶点数相等且双方都满足相应条件，则可得到完全匹配。
这类结论常用于判断是否能实现“无遗漏配对”。
4.4.2 覆盖与独立集关系
在图中，独立集是指顶点之间没有边相连的集合。对二分图来说，点覆盖与独立集之间存在明确联系：一个顶点集是点覆盖，当且仅当其补集是独立集。
因此，最小点覆盖和最大独立集之间也存在互补意义上的关系。
5 匹配与覆盖
匹配与覆盖是二分图研究中最核心的两类组合对象，也是应用最广的部分。
5.1 匹配的定义
匹配是图中若干条互不共享端点的边组成的集合。它对应于“成对安排”或“互不冲突连接”。
5.1.1 单匹配与最大匹配
单匹配通常指任意满足互不冲突条件的边集。若在所有匹配中边数达到最大，则称为最大匹配。
最大匹配并不一定唯一，但其大小是图的重要参数。
5.1.2 完全匹配与完美匹配
完全匹配通常指覆盖某一侧全部顶点的匹配；若匹配覆盖了图中的所有顶点，则称为完美匹配。
在二分图中，完美匹配要求两侧顶点数相等，且每个顶点都恰好被匹配一次。
5.2 点覆盖
点覆盖关注的是用尽量少的顶点去“触及”所有边，是匹配问题的重要对偶对象。
5.2.1 顶点覆盖问题
一个顶点集合若与图中每条边至少有一个公共端点，则称其为点覆盖。这个问题在资源监控、故障检测和控制节点选择中经常出现。
5.2.2 最小点覆盖
在所有点覆盖中，顶点数最少的那个称为最小点覆盖。对二分图而言，最小点覆盖大小与最大匹配大小相等，这一结果由 König 定理给出。
5.3 边覆盖
边覆盖与点覆盖相近，但对象换成了边，常用于描述“用尽量少的边覆盖所有顶点”。
5.3.1 边覆盖的概念
若一组边使得每个顶点至少与其中一条边相接，则称这些边构成边覆盖。边覆盖常用于检查每个对象是否至少被某个关系连接到。
5.3.2 与匹配的联系
在二分图中，边覆盖和匹配之间存在紧密关系。一般来说，最大匹配提供了构造较小边覆盖的基础，而边覆盖的规模也会反映图的结构稠密程度。
5.4 算法求解
二分图的匹配和覆盖问题之所以重要，很大程度上是因为它们有高效可行的算法解法。
5.4.1 增广路算法
增广路算法通过不断寻找增广路并更新匹配来扩大匹配规模。只要还能找到增广路，就说明当前匹配还不是最大匹配。
这是求二分图最大匹配的经典方法之一。
5.4.2 Hungarian算法
Hungarian算法常用于带权二分图的最优匹配问题，尤其适合求解最小权完美匹配或最大权匹配。该算法在指派问题中尤为著名。
它的优势在于结构清晰、理论完备，并且适合较大规模的优化任务。
5.4.3 最大流建模
二分图匹配问题可以转化为最大流问题：从源点连向左侧顶点，再由左侧连向右侧，最后由右侧连向汇点，边容量通常设为 1。这样，最大流值就对应匹配大小。
这种建模方法使二分图问题能够调用成熟的网络流算法求解。
6 二分图的判定与构造
除了研究性质与定理，实际中还常需要判断一个图是否为二分图，并据此构造合理的顶点划分。
6.1 判定方法
二分图判定通常通过图遍历实现，核心思想是尝试进行二染色，并检查是否出现冲突。
6.1.1 深度优先搜索判定
深度优先搜索可以沿图递归着色：从一个未访问顶点开始，给它赋色，然后将其邻点染成相反颜色。如果在递归过程中发现相邻点颜色相同，则说明该图不是二分图。
这种方法实现简单，适合在递归框架下使用。
6.1.2 广度优先搜索判定
广度优先搜索通常更适合层次化地完成二染色。它按距离一层层推进，天然符合二分图“奇偶层交替”的结构特征。
在实际算法中，BFS 判定常被视为较稳健的做法。
6.2 构造方法
当确认一个图是二分图后，还需要把两个部分显式构造出来。构造过程本质上就是把染色结果或层次结果转换为顶点划分。
6.2.1 从奇环排除出发构造
如果能证明图中不存在奇环，通常就能据此构造二分划分。做法是选定一个起点，按路径长度的奇偶性将顶点分到两个集合中。
只要图没有奇环，这种划分就不会产生矛盾。
6.2.2 从配色结果构造划分
若已经得到二染色结果，那么可直接把两种颜色对应到两个顶点集。染成同一颜色的顶点放在同一侧，不同颜色的顶点放在另一侧，即得到二分结构。
这一方法简洁直观，也是最常见的构造方式。
6.3 典型例题
二分图的判定与构造常以实例形式出现，既可以是小型图的手算，也可以是复杂网络的程序处理。
6.3.1 简单图判定
对于少量顶点的图，通常通过观察是否存在三角形、五边形等奇环来快速判断。若图是树、路径或偶环组合，往往可以直接确认其为二分图。
6.3.2 复杂网络建模
在复杂网络中，图的结构未必一眼可见，但只要能将对象分成两类并保证边只跨类连接，就能建立二分模型。此类问题在数据关联、排班系统和任务分派中很常见。
7 组合数学与算法中的应用
二分图不仅是理论对象，也是一种非常实用的建模框架。凡是涉及两类对象之间关系的问题，往往都可以考虑转化为二分图。
7.1 任务分配问题
任务分配是二分图应用最典型的场景之一，常见于人员安排、课程指派和作业分工。
7.1.1 人员与任务匹配
当若干人员与若干任务之间存在“适合”或“可执行”关系时，可以把人员和任务分别作为二分图两侧顶点，再把可执行关系画成边。寻找匹配就是寻找合适的分配方案。
7.1.2 资源调度模型
在资源调度中，一侧可以表示资源，另一侧表示需求项，边表示可分配关系。通过匹配或带权匹配，可以得到较优的调度结果。
7.2 关系网络建模
许多二元关系天然适合用二分图描述，因为它们本身就具有“对象—对象”的双侧结构。
7.2.1 二元关系表示
若一类对象与另一类对象之间存在关联，如“作者—文章”“用户—商品”等，就可以用二分图表示这种二元关系。边的存在意味着关系成立。
这种表示方式比单纯的表格更利于分析结构、寻找规律和执行算法。
7.2.2 数据关联图
在数据处理中，二分图可用于表示样本与特征、实体与标签、记录与属性之间的关系。通过图结构可以更清晰地研究关联密度、匹配可能性与覆盖情况。
7.3 计算机科学中的应用
二分图在计算机科学中用途广泛，尤其在编译优化和推荐系统中非常常见。
7.3.1 编译与寄存器分配
在编译理论中，变量、活跃区间或操作需求有时可以转化为二分结构，再借助匹配或覆盖思想进行资源分配。虽然具体模型较复杂，但二分图提供了重要的抽象工具。
7.3.2 推荐与匹配系统
推荐系统中，用户与物品之间的交互关系常可以用二分图表示。根据边的结构，可以分析偏好、相似性和潜在匹配机会。
7.4 其他应用
除了常见的分配与推荐问题，二分图还出现在分组、配对和稳定性分析等多个领域。
7.4.1 项目分组
在项目管理中，可将成员与项目、技能与岗位等关系建模为二分图，从而更方便地组织分组与分派。
7.4.2 稳定配对问题
稳定配对问题关注的是在匹配过程中避免明显冲突或不满意的组合。二分图为此提供了清晰的结构基础，便于定义约束并寻找可行解。