图论-二分图专题

图论-二分图专题(二分图匹配、匈牙利算法、KM算法) 😊 | Powered By HeartFireY | BG 📕 | 需要的前导知识：图论基础

一、二分图-定义与基本性质 1.二分图-定义

二分图(Bipartite graph)，也称作”二部图“。简单的来说，二分图由两个点集和他们之间的映射(连边)构成，点集内部的点相互独立，不存在连边。

换而言之，我们可以对一个图采取某种方案，得到一张所有节点被划分为两个集合，且两个集合内部没有边的图。

如上图-(示例一)所示，就是一张构造好的二分图， S E T 1 SET_1 SET1​和 S E T 2 SET_2 SET2​集合之间存在连边关系，两个集合的内部不存在任何边关系，集合内点相互独立。

2.二分图-性质

根据二分图的定义，我们可以发现对于任意节点一定满足：

图中任意一条边一定满足起点是从 S E T 1 SET_1 SET1​出发，然后到达 S E T 2 SET_2 SET2​，也就是说，任意一条边的起止点一定属于不同的集合。

格局上面的性质，我们可以进一步推广：二分图不存在长度为奇数的环。

因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。

3.二分图-判定

显然对于给定的图，枚举答案集合是过于朴素的做法，应该考虑更高效的做法。

我们可以直接 d f s dfs dfs或者 b f s bfs bfs来遍历整张图，遍历过程中不断的查环的长度，如果查到了奇环，那么说明一定不是二分图。

二、二分图-匹配、最大匹配、完美匹配和最优匹配 1.匹配

在图论中，一个"匹配"就是一个边集，这个边集中的任意两条边都没有公共顶点

匹配点： 位于匹配(边集)中某条连接的点，也就是已经匹配的点；

匹配边： 位于匹配(边集)中的某条边，也就是已经匹配的边；

未匹配点、未匹配边： 顾名思义，尚未匹配的点和边

如下图所示就是上文二分图示例一的一个匹配。

显然，红色的边是匹配边，红边连接的点为匹配点…

2.最大匹配

一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

如上图所示，两个图片都为示例一的匹配，其中Graph_2为示例一的最大匹配。

3.完美匹配

如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。图 4 是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。

显然，Graph_2并不是一个完美匹配。

我们通过一些示例继续说明完美匹配和最大匹配的区别：

如P_1所示，假设女生和男生之间的连线表示彼此之间存在好感。现在要求求最多多少对男女匹配，使得每对匹配的男生女生相互喜欢。那么这就是一个求最大匹配的问题。

那么我们根据最大匹配的定义可以知道：P_2不是最大匹配，因为并不满足”最多“；而P_3是满足题意的一个匹配。

我们换一种问问题的方式：是否可能让所有男生和女生两两配对，使得每对男生女生之间都相互喜欢？那么这就是一个求完美匹配的问题。

通过上面的示例，我们不难发现：完美匹配一定是最大匹配，而最大匹配不一定就是完美匹配。

4.最优匹配

最优匹配又称为带权最大匹配，是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和最大。

三、二分图-增广路、交错路

这两个概念将为求解二分图最大匹配的匈牙利算法做前置知识铺垫。

1.交错路

交错路又称交替路，从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径。

2.增广路

从一个未匹配点出发，走交替路，如果途径另一个未匹配点(不能是出发的点)，则这条交替路称为增广路(Agumenting Path)。

容易发现：增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的状态交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。

四、二分图-最小覆盖、最大独立集 1.最小覆盖

二分图的最小覆盖分为最小顶点覆盖和最小路径覆盖：

1. 最小顶点覆盖：指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联，二分图的最小顶点覆盖数=二分图的最大匹配数；

2. 最小路径覆盖：也称为最小边覆盖，是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。

3. 二 分 图 的 最 小 路 径 覆 盖 数 = ∣ V ∣ − 二 分 图 的 最 大 匹 配 数 二分图的最小路径覆盖数=|V|-二分图的最大匹配数 二分图的最小路径覆盖数=∣V∣−二分图的最大匹配数；

2.最大独立集

最大独立集是指寻找一个点集，使得其中任意两点在图中无对应边。对于一般图来说，最大独立集是一个NP完全问题，对于二分图来说：最大独立集=|V|-二分图的最大匹配数。

五、二分图-匈牙利算法 1.简介

匈牙利算法的主要用于解决二分图的最大匹配、最小覆盖问题。

我们不难发现，对于求解最大匹配问题，实际上就是在求解在二分图中最多能找到多少条没有公共端点的边。在下面的样例中，我们会详细的分析这个过程。

OI-WIKI上对二分图的最大匹配算法中提到了"增广路算法"。从实现原理上来看，个人觉得跟匈牙利算法就是同一个算法。

2.过程分析

我们首先继续引用男女配对这个经典的例子：如图L_1所示，图中的各个男生和女生之间存在着相互的好感。我们首先从第一个女生开始配对(如图L_2所示)，按照边的顺序我们会选择第一个男生，此时没有发生任何冲突，因此我们继续：

如图L_3所示，我们给第二个女生进行配对，此时按顺序首先选择第一个男生，此时我们可以清楚的发现：产生冲突了。那么我们该怎样找到一种通用的方法解决这个冲突呢？我们使用匈牙利算法的思路继续分析：寻找增广路。

如上图L_5所示，按照增广路的定义，我们从第二个女生(未匹配点)出发走到第一个男生(已匹配点)，再经过第一个女生(未匹配点)到达第三个男生(未匹配)，这样一条路径便是一条交错路，而到达了第一个为匹配点时的路便是增广路。找到这样一条增广路后，我们对增广路进行一个"取反"操作，也就是让匹配边变为未匹配边，未匹配边变为匹配边，如图L_6所示。经此变化后，我们不难发现匹配的问题已经得到了解决。

这个过程很好的利用了增广路的性质：非匹配边比匹配边多一条，中间的匹配节点不存在其他相连的匹配边。因此我们进行取反操作不会影响匹配的性质，同时通过交换我们使得匹配边和非匹配边的数量互换，也就是匹配边比原来多出一条。匹配性质不变+匹配边多一条，一次来继续匹配的过程，便是匈牙利算法的核心思想。

我们可以继续根据以上思路匹配，直至所有的点都被匹配。当然，有些图可能并非所有的点都能够得到匹配。

如图L_11便是一个 最大匹配&&完美匹配 。

3.实现

const int MAXN = GRAPH_SIZE_L， MAXM = GRAPH_SIZE_W;

int M, N;            //M, N分别表示左、右侧集合的元素数量
int g[MAXM][MAXN]; //邻接矩阵存图
int p[MAXN];         //记录当前右侧元素所对应的左侧元素
bool vis[MAXN];      //记录右侧元素是否已被访问过
bool dfs(int i){
    for (int j = 1; j