大家好，欢迎来到IT知识分享网。

1. 前言

二分图是图论当中很重要的一个板块，由二分图的匹配与带权匹配可以推广出一般图的匹配与带权匹配。

本篇博文主要讲解：二分图的定义、性质、判定。

本文部分地方参考了 oi-wiki 的资料，在此表示感谢。

本篇博文约定：

1. 图 \(G=<V,E>\) 表示图 \(G\) 的所有点的集合为 \(V\)，所有边的集合为 \(E\)。
2. \((a,b)\) 表示 \(a\) 与 \(b\) 的连边。

2. 二分图

二分图的数学语言描述如下：

给出图 \(G=<V,E>\)，从中选出两个点集 \(V_1,V_2\)，且 \(V_1 \cap V_2 = \varnothing,V_1 \cup V_2 = E\)，如果 \(\forall a,b \in V_1,(a,b) \not \in E;\forall a,b \in V_2,(a,b) \not \in E\)，那么图 \(G\) 是二分图，后面记作 \(G=<V_1,V_2,E>\)。

说的通俗一点就是：

如果一张图 \(G=<V,E>\) 能够将所有点划分成两个组，组内的点互相都不直接连边，那么这张图就是二分图，划分成的两个组记作点集 \(V_1,V_2\)，后面对这张二分图记作 \(G=<V_1,V_2,E>\)。

比如下面的两张图都是二分图：

（绘图网址：link）

需要注意的是，二分图不一定要连通，比如上面的右边这张图，并不连通，但是其仍然是一张二分图。

二分图中有一类二分图叫完全二分图。

完全二分图的数学语言描述如下：

给出图 \(G=<V_1,V_2,E>\)，如果 \(\forall a \in V_1,b \in V_2,\) 必有 \((a,b) \in E\)，那么图 \(G\) 是完全二分图。

说的通俗一点就是：

选出的两个点集之间，每个点与另外一个点集的点都有连边。

比如下面这张图就是完全二分图。

需要注意的是，完全二分图一定是连通的。

习惯上，也会称 \(V_1\) 为左部点，\(V_2\) 为右部点。

二分图有一个很重要的性质：图中不会存在奇环。

为什么不会存在奇环？

证明：以左部点为例，随便选一个点走一条边，一定是走到右部点，而右部点又会走回到左部点。也就是说，左部点一定连着右部点，右部点一定连着左部点。

那么假设存在奇环，不妨设上面的一个点在左部点，那么与其相邻的点都在右部点，再相邻的点都在左部点。

设点数为 \(2k+1,k \in Z\)，那么第一次选取的点为左部点，以后一次选取两个点，那么最后两个点呢？根据第一段理论，这两个点应该不在一起，但是点数为奇数，这么选下去却又在一起，显然矛盾。因此原性质得证。

从这个性质中可以知道如何判定二分图：黑白染色。

具体的，对于每一个连通块，选择一个点染成黑色，周围的点染成白色，然后继续染成黑色……如果发现有一个点既染成黑色又染成白色，那么这张图就不是二分图。

同时如果是二分图 且这张图是连通的，那么黑色点就是左部点，白色点就是右部点（当然左右随意）。

判定完全二分图呢？黑白染色后已知图连通，左部点个数，右部点个数，算一算边数是否等于 \(|V_1| \times |V_2|\) 就好了。\(|V|\) 表示 \(V\) 的大小。

3. 匹配

匹配（又名独立边集）是图上一个重要的概念。在二分图中求匹配等价于网络流问题。

当然这篇博文不是讲网络流的

匹配就是一张图中没有公共点的边的集合。

数学语言描述如下：

在图 \(G=<V,E>\) 中，没有公共点的边集 \(M(M \subseteq E)\) 是图 \(G\) 的匹配。一张图有很多个匹配。

边数最大的匹配称为最大匹配。

当图上的边带权值的时候，边权和最大的匹配称为最大权匹配。

匹配中的边称为匹配边，反之称为未匹配边。

一个点如果在匹配中且至多属于一条边的端点，则将其称为匹配点。否则称为未匹配点。

以上定义全部摘自 图匹配 – OI Wiki，数学语言描述除外。

定义应该还是好理解的吧。

二分图呢？一张二分图上的匹配称为二分匹配。

本篇博文约定：如没有特殊说明，那么本文中的匹配默认为二分匹配。

而寻找最大匹配有两种算法：匈牙利算法（边不带权）与 KM 算法（边带权），后面都会一一提到。

3. 增广路

交错路与增广路也是匹配（一般图）中很重要的概念。

交错路从非匹配边开始，且非匹配边与匹配边交错的路径。

增广路就是指始于非匹配点且终于非匹配点的交错路。

当增广路上非匹配边比匹配边数量大一，那么将非匹配边改为匹配边，匹配边改为非匹配边，那么该路径依然是增广路而且匹配数加一。

可以参考下面的图理解（摘自 增广路 – OI Wiki）

这就是求最大匹配的核心思路：寻找增广路。

具体怎么求就是后话了。

4. 总结

本文当中提到的定义与性质如下：

1. 二分图与完全二分图
2. 二分图中不存在奇环
3. 二分图判定黑白染色
4. 图的匹配以及增广路

请自查有没有理解。