首页 > 代码库 > 二分图基础知识
二分图基础知识
昨天晚上开始看二分图，到现在基本的东西学会了
我就写一下我自己的理解
首先什么是二分图
顾名思义就是能分成两个部分的图
要注意的是，‘分’的是点
并且这两个集合（这里我们称作X集合和Y集合）内部所有的点之间没有边相连，也就是说X集合中任何两点之间都不会有边相连， Y亦然
定理1：无向图G为二分图的一个冲要条件是 1、G中至少包含两个顶点 2、G中所有的回路长度都必须是偶数
接下来是一些概念：
匹配：设G=<V, E>为二分图，如果 M⊆E，并且 M 中没有任何两边有公共端点，则成M为G的一个匹配。【也就是说匹配的实质是一些边的集合。】
最大匹配：边数最多的匹配
完备匹配与完全匹配：若 X 中所有的顶点都是匹配 M 中的端点。则称 M 为X的完备匹配。 若M既是 X-完备匹配又是 Y-完备匹配，则称M 为 G 的完全匹配。
最小点覆盖：用尽可能少的点去覆盖所有的边【最小点覆盖集是点的集合，其个数为最小点覆盖数】
最大点独立：跟网络流中的最大点权独立集有点类似，这里指的是最大独立的个数
接下来是二分图的一些性质：
设无向图G有n个顶点，并且没有孤立顶点，那么，
1、点覆盖数 + 点独立数 = n
2、最小点覆盖数 = 二分图的最大匹配
3、最大点独立数 = n - 最小点覆盖数 = n - 最大匹配
二分图的判定：
判断一个图是不是二分图有两条1、n>= 2 2、不存在奇圈
我们可以用黑白染色的方法进行判断
1 const int maxn = 105; 2 3 int col[maxn]; 4 5 bool is_bi(int u) { 6 for(int i = 0; i < G[u].size(); i++) { 7 int v = G[u][i]; 8 if(col[v] == col[u]) return false; 9 if(!col[v]) {10 col[v] = 3 - col[u];11 if(!is_bi(v)) return false;12 }13 }14 return true;15 }
接下来介绍一下求二分图最大匹配的匈牙利算法。
匈牙利算法的思想是这样的：如果一个图中存在增广路，那么沿着这条路增广，匹配就会加1，知道不存在增广路为止
这里的增广路是这么定义的：对于一个未匹配或已经匹配好一部分的G来说
在X集合中的未匹配点出发，依次经过未匹配边匹配边未匹配边匹配边……而终点落在Y中的一个未访问点上，那么只要将该路上的匹配边于未匹配边调换，那么新的匹配必将比原来的匹配多1，【详细见http://blog.csdn.net/xuguangsoft/article/details/7861988中的图】//如果不理解可以看刘汝佳大白书，一会动手模拟一下程序即可
下面是匈牙利算法的邻接矩阵和邻接表程序
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 105; 7 const int INF = 1000000000; 8 9 bool vis[maxn];//查询右集合中的点有没有被访问过10 int link[maxn];//link[i]表示右集合中的i点是由左集合中的哪个点连接的11 int G[maxn][maxn];//邻接矩阵12 int x_cnt; int y_cnt;//左右集合的点的个数13 14 bool find(int u) {//用来寻找增广路15 for(int i = 1; i <= y_cnt; i++) {//遍历右集合中的每个点16 if(!vis[i] && G[u][i]) {//没有被访问过并且和u点有边相连17 vis[i] = true;//标记该点18 if(link[i] == -1 || find(link[i])){ //该点是增广路的末端或者是通过这个点可以找到一条增广路19 link[i] = u;//更新增广路 奇偶倒置20 return true;//表示找到一条增广路21 }22 }23 }24 return false;//如果查找了右集合里的所有点还没找到通过该点出发的增广路，该点变不存在增广路25 }26 27 int solve() {28 int num = 0;29 memset(link, -1, sizeof(link));//初始化为-1表示 不与左集合中的任何元素有link30 for(int i = 1; i <= x_cnt; i++) {//遍历左集合31 memset(vis, false, sizeof(vis));//每一次都需要清除标记32 if(find(i)) num++;//找到一条增广路便num++33 }34 return num;35 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 33; 7 const int INF = 1000000000; 8 9 struct Node {10 int to;11 int next;12 }q[MaxEdge];13 14 struct MaxMatch() {15 int head[MaxEdge];16 int tot;17 int vis[Y_cnt];18 int link[Y_cnt];19 20 void init(int x_cnt) {21 this -> x_cnr = x_cnt;22 tot = 0;23 }24 25 void AddEdge(int u, int v) {26 q[tot].to = v;27 q[tot].next = head[u];28 head[u] = tot ++;29 }30 31 bool find(int u) {32 for(int i = head[u]; i; i = q[i].next) {33 int v = q[i].to;34 if(!vis[v]) {35 vis[v] = 1;36 if(link[v] == -1 || find(link[v])) {37 link[v] = u;38 return true;39 }40 }41 }42 return false;43 }44 45 int Match() {46 int num = 0;47 memset(link, -1, sizeof(link));48 for(int i = 0; i < x_cnt; i++) { // ±éÀú×󼯺Ï49 memset(vis, 0, sizeof(vis));50 if(find(X[i])) num++;51 }52 return num;53 }54 };
可以用HDU2063熟悉模板
下面也是最重要也是最难理解的二分图的最佳匹配
上面介绍的匈牙利算法只能求出匹配边的条数，现在我们来加个条件：让二分图的每个边上都加一个权值
现在让你求出最大（最小）权值的匹配
这里有个常用算法--KM算法
首先要引入一个概念：可行顶标。
设顶点 Xi 的顶标为 lx[i]，顶点 Yj 的顶标为 ly[j]，顶点 Xi 与 Yj 之间的边权为 w[i][j] 。在算法执行过程中的任一时刻，对于任一条边 (i,j)，lx[i]+ly[j]>=w[i,j] 始终成立。
那么Lx[i] 为i可行顶标，Ly[j]为j的可行顶标
从这个角度考虑，如果满足lx[i]+ly[j]==w[i][j]的条件下的一个子图中存在一个完美匹配的话，那么这个匹配就一定是原图的最大全匹配
证明：由于该匹配的可行顶标之和等于匹配的权值之和，而由于lx[i]+ly[j]>=w[i,j]其它的所有匹配的防方案权值一定会小于顶标之和。
所以问题就转化成了通过修改可行顶标，求得最理想的匹配。
KM算法调整的方法是： 根据最后一次不成功的寻找交错路的 DFS，取所有 i 顶点被访问到而 j 顶点没被访问到的边 (i,j) 的 lx[i]+ly[j]-w[i][j] 的最小值 d。将交错树中的所有左端点的顶标减小d，右端点的顶标增加 d。
经过这样的调整以后： 原本在导出子图里面的边，两边的顶标都变了，不等式的等号仍然成立，仍然在导出子图里面；原本不在导出子图里面的边，它的左端点的顶标减小了，右端点的顶标没有变，而且由于 d 的定义，不等式仍然成立，所以他就可能进入了导出子图里，这样经过不断的调整，最后就可以找到 一个有完美匹配的导出子图（原图的完备匹配），也就求出了该图的最大权匹配。
代码是刘汝佳大白书上抄的：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 500 + 10; 7 const int INF = 1000000000; 8 9 int W[maxn][maxn], n;10 int Lx[maxn], Ly[maxn]; // 顶标11 int left[maxn]; // left[i]为右边第i个点的匹配点编号12 bool S[maxn], T[maxn]; // S[i]和T[i]为左/右第i个点是否已标记13 14 bool match(int i) {15 S[i] = true;16 for(int j = 1; j <= n; j++) if (Lx[i]+Ly[j] == W[i][j] && !T[j]){17 T[j] = true;18 if (!left[j] || match(left[j])){19 left[j] = i;20 return true;21 }22 }23 return false;24 }25 26 void update() {27 int a = INF;28 for(int i = 1; i <= n; i++) if(S[i])29 for(int j = 1; j <= n; j++) if(!T[j])30 a = min(a, Lx[i]+Ly[j] - W[i][j]);31 for(int i = 1; i <= n; i++) {32 if(S[i]) Lx[i] -= a;33 if(T[i]) Ly[i] += a;34 }35 }36 37 void KM() {38 for(int i = 1; i <= n; i++) {39 left[i] = Lx[i] = Ly[i] = 0;40 for(int j = 1; j <= n; j++)41 Lx[i] = max(Lx[i], W[i][j]);42 }43 for(int i = 1; i <= n; i++) {44 for(;;) {45 for(int j = 1; j <= n; j++) S[j] = T[j] = false;46 if(match(i)) break; else update();47 }48 }49 }
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 500 + 5; // 顶点的最大数目 8 const int INF = 1000000000; 9 10 // 最大权匹配11 struct KM {12 int n; // 左右顶点个数13 vector<int> G[maxn]; // 邻接表14 int W[maxn][maxn]; // 权值15 int Lx[maxn], Ly[maxn]; // 顶标16 int left[maxn]; // left[i]为右边第i个点的匹配点编号，-1表示不存在17 bool S[maxn], T[maxn]; // S[i]和T[i]为左/右第i个点是否已标记18 19 void init(int n) {20 this->n = n;21 for(int i = 0; i < n; i++) G[i].clear();22 memset(W, 0, sizeof(W));23 }24 25 void AddEdge(int u, int v, int w) {26 G[u].push_back(v);27 W[u][v] = w;28 }29 30 bool match(int u){31 S[u] = true;32 for(int i = 0; i < G[u].size(); i++) {33 int v = G[u][i];34 if (Lx[u]+Ly[v] == W[u][v] && !T[v]){35 T[v] = true;36 if (left[v] == -1 || match(left[v])){37 left[v] = u;38 return true;39 }40 }41 }42 return false;43 }44 45 void update(){46 int a = INF;47 for(int u = 0; u < n; u++) if(S[u])48 for(int i = 0; i < G[u].size(); i++) {49 int v = G[u][i];50 if(!T[v]) a = min(a, Lx[u]+Ly[v] - W[u][v]);51 }52 for(int i = 0; i < n; i++) {53 if(S[i]) Lx[i] -= a;54 if(T[i]) Ly[i] += a;55 }56 }57 58 void solve() {59 for(int i = 0; i < n; i++) {60 Lx[i] = *max_element(W[i], W[i]+n);61 left[i] = -1;62 Ly[i] = 0;63 }64 for(int u = 0; u < n; u++) {65 for(;;) {66 for(int i = 0; i < n; i++) S[i] = T[i] = false;67 if(match(u)) break; else update();68 }69 }70 }71 };