定义

如果一张无向图的 N 个节点 (N≥2) 可以分成 A,B 两个非空集合，其中 A∩B 是空集，并且在同一集合内的点之间都没有边相连，那么称这张无向图为一张二分图。A,B 分别称为二分图的左部和右部

二分图判定

定理：一张无向图是二分图，当且仅当图中不存在奇环（长度为奇数的环）。

根据该定理，我们可以用染色法进行二分图的判定。大致思想为：尝试用黑白两种颜色标记图中的节点，当一个节点被标记后，它的所有相邻节点应该被标记与它相反的颜色。若标记过程中产生冲突，则说明图中存在奇环。二分图染色一般基于深度优先遍历实现，时间复杂度为 O(N+M)

void dfs(int x,int color)赋值 v[x] ← color对于与 x 相连的每条无向边(x,y)if v[y] = 0 thendfs(y,3-color)else if v[y] = color then判定无向图不是二分图,算法结束
在主函数中for i ← 1 to Nif v[i] = 0 then dfs(i,1)判定无向图是二分图

二分图最大匹配

“任意两条边都没有公共端点”的边的集合被称为图的一组匹配。在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

对于任意一组匹配 S (S 是一个边集)，属于 S 的边被称为“匹配边”，不属于 S 的边被称为“非匹配边”。匹配边的端点被称为“匹配点”，其他节点被称为“非匹配点”。如果在二分图中存在一条连接两个非匹配点的路径 path，使得非匹配边与匹配边在 path 上交替出现，那么称 path 是匹配 S 的增广路，也称交错路。

增广路显然具有以下性质：

1. 长度 len 是奇数。

2. 路径上第 1,3,5,...,len 条边是非匹配边，第 2,4,6,...,len-1 条边是匹配边。

正因为以上性质，如果我们把路径上所有边的状态取反，原来的匹配边变成非匹配的，原来的非匹配边变成匹配的，那么得到的新的边集 S' 仍然是一组匹配，并且匹配边数增加了1。进一步可以得到结论：

二分图的一组匹配 S 是最大匹配，当且仅当图中不存在 S 的增广路。

匈牙利算法（增广路算法）

匈牙利算法，又称增广路算法，用于计算二分图最大匹配。它的主要过程为：

1. 设 S 为空集，即所有边都是非匹配边。

2. 寻找增广路 path，把路径上所有边的匹配状态取反，得到一个更大的匹配 S'。

3. 重复第2步，直至图中不存在增广路。

该算法的关键在于如何找到一条增广路。匈牙利算法依次尝试给每一个左部节点 x 寻找一个匹配的右部节点 y。右部点 y 能与左部点 x 匹配，需要满足以下两个条件之一：

1. y 本身就是非匹配点。

此时无向边 (x,y) 本身就是非匹配边，自己构成一条长度为 1 的增广路。

2. y 已经与左部点 x' 匹配，但从 x' 出发能找到另一个右部点 y' 与之匹配。

此时路径 x~y~x'~y' 为一条增广路。

在实际的程序实现中，我们采用深度优先搜索的框架，递归地从 x 出发寻找增广路。若找到，则在深搜回溯时，正好把路径上的匹配状态取反。另外，可以用全局 bool 数组标记节点的访问情况，避免重复搜素。

匈牙利算法的正确性基于贪心策略，它的一个重要特点是：当一个节点成为匹配点后，至多因为找到增广路而更换匹配对象，但是绝不会再变回非匹配点。

对于每个左部节点，寻找增广路最多遍历整张二分图一次。因此，该算法的时间复杂度为O(NM)。

bool dfs(int x){for(int i=head[x],y;i;i=nxt[i]){if(!vis[y=ver[i]]){vis[y]=1;if(!match[y]||dfs(match[y]){match[y]=x;return true;}}}return false;
}for(int i=1;i<=n;i++){ // 在 main 函数中memset(vis,0,sizeof(vis));if(dfs(i)) ans++;
}

完备匹配

给定一张二分图，其左部，右部节点数相同，均为 N 个节点。如果该二分图的最大匹配包含 N 条匹配边，则称该二分图具有完备匹配。

多重匹配

给定一张包含 N 个左部节点、M 个右部节点的二分图。从中选出尽量多的边，使第 i(1≤i ≤N) 个左部节点至多与 kli 条选出的边相连，第 j(1≤j≤M) 个右部节点至多与 krj 条选出的边相连，第 j(1≤j≤M) 个右部节点至多与 krj 条选出的边相连。该问题被称为二分图的多重匹配。

当 kli=krj=1 时，上述问题就简化为二分图最大匹配。因此，多重匹配是一个广义的“匹配”问题，每个节点可以与不止一条“匹配”边相连，但不能超过一个给定的限制。

多重匹配一般有四种解决方案：

1.拆点。把第 i 个左部节点拆成 kli 个不同的左部节点，第 j 个右部节点拆成 krj 个右部节点。对于原图中的每条边(i,j)，在 i 拆成的所有节点与 j 拆成的所有节点之间连边。然后求解二分图最大匹配

2. 如果所有的 kli=1，或者所有的 krj=1，即只有一侧是“多重”匹配，不妨设左部是“多重”的，那么可以直接在匈牙利算法中让每个左部节点执行 kli 次 dfs。

3. 在第 2 种方案中，当然也可以交换左右两部，设“右部”是多重的，修改匈牙利算法的实现，让右部节点可以匹配 krj 次，超过匹配次数后，就要依次尝试递归当前匹配的 krj 个左部节点，看能否找到增广路。

4. 网络流。

二分图带权匹配

给定一张二分图，二分图的每条边都带有一个权值。求出该二分图的一组最大匹配，使得匹配边的权值总和最大。这个问题称为二分图的带权最大匹配，也称二分图最优匹配。注意，二分图带权最大匹配的前提是匹配数最大，然后再最大化匹配边的权值总和。

二分图带权最大匹配有两种解法：费用流和KM算法。这里简单说一下KM算法程序实现简单，在稠密图上的效率一般高于费用流。不过，KM算法有很大的局限性，只能在满足“带权最大匹配一定是完备匹配”的图中正确求解。所以一般情况下，更推荐采用费用流来计算二分图带权最大匹配。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！