二部图的最大匹配和最大权匹配
二部图的最大匹配和最大权匹配
- 二部图：可以划分为两个内部无边的子图的图
*存储二部图时注意点的下标不要重合！
-
二部图的判定：一个图是二部图的充要条件是没有无奇环
-
图的匹配：一个边的集合，其中任意两条边都没有公共顶点
-
匹配点、匹配边、非匹配点、非匹配边：即在（不在）匹配里的点（边）
-
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配，若最大匹配包含该图的所有点，则称为完美匹配。
-
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
-
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路
可以发现，增广路的长度为奇数，若交换增广路中的匹配边与非匹配边，匹配边数会加一，因而有：
定理：一个图的匹配是最大匹配的充要条件是这个匹配里不含增广路
通过不断交换增广路的匹配边与非匹配边，我们可以得到求解最大匹配的匈牙利算法
1.便利左部顶点，挑选非匹配点进行搜索，寻找增广路。
2.如果经过一个未匹配点，说明寻找成功。更新路径信息（交换匹配边和非匹配边），匹配边数 +1，停止搜索。
以下是匈牙利算法的BFS版本（据说效率高）：
int Hungarian() {
bool flag = 0;
queue<int> q;
int res = 0, prev[1005] = {0};
memset(matching, -1, sizeof(matching));
memset(check, -1, sizeof(check));
for (int i = 1; i <= n; i++) {
if (matching[i] != -1) continue;
while (!q.empty()) q.pop();
q.push(i);
prev[i] = -1;
check[i] = i;
flag = 0;
while (!q.empty() && flag == 0) {
int f = q.front(), t = adj[f];
while (t != 0 && flag == 0) {
if (check[p[t].end] == i) {
t = p[t].next;
continue;
}
check[p[t].end] = i;
if (matching[p[t].end] != -1) {
prev[matching[p[t].end]] = f; //连接前一组match
q.push(matching[p[t].end]);//将找到的match推入队列
}
else { //找到增广路
flag = 1;
int u = f, v = p[t].end;
while (u != -1) {
int g = matching[u];
matching[u] = v;
matching[v] = u;
u = prev[u];
v = g;
}
}
t = p[t].next;
}
q.pop();
}
if (matching[i] != -1) res++;
}
return res;
}此外，最小点覆盖、最小边覆盖、最大独立集、最大独立团等都可以归结为求解最大匹配的问题
定理
定理：一个图的最大独立集元素点数等于总点数减最小点覆盖数
参考文章：
二分图的最大匹配、完美匹配和匈牙利算法
题解 P6577 【模板】二分图最大权完美匹配】