数学建模二分图匹配

1、二分图匹配二分图匹配匈牙利算法简介及应用匈牙利算法简介及应用软件学院软件学院 周娟周娟回 顾v上一讲：最大网络流问题上一讲：最大网络流问题v 江西省江西省2012年数学建模年数学建模B题题 一等奖，华东交一等奖，华东交通大学基础学院周琴、胡媛媛、郭文文同学在通大学基础学院周琴、胡媛媛、郭文文同学在论文中写到：论文中写到： “利用网络流算法的方法，得到最均匀的分利用网络流算法的方法，得到最均匀的分发方法，并且可以使得任何两位教师交叉共同发方法，并且可以使得任何两位教师交叉共同评阅一份试卷的情况也尽量均匀。评阅一份试卷的情况也尽量均匀。”v “计算最大流的计算最大流的Dinic算法去安排阅卷。算法

2、去安排阅卷。”v “Dinic算法是网络流的优化算法之一，每算法是网络流的优化算法之一，每一步对原图进行分层，然后用递归搜索的方式一步对原图进行分层，然后用递归搜索的方式求求增广路增广路，算法的时间复杂度是，算法的时间复杂度是O(n2m)，n为为有向图的顶点数，有向图的顶点数，m为有向图的边数。为有向图的边数。” 二分图的概念二分图的概念v二分图又称作二部图，是图论中的一种特二分图又称作二部图，是图论中的一种特殊模型。殊模型。v设设G=(V,R)是一个无向图。如顶点集是一个无向图。如顶点集V可可分割为两个互不相交的子集，并且图中每分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个

3、不同的子条边依附的两个顶点都分属两个不同的子集。则称图集。则称图G为二分图。为二分图。112233445最大匹配最大匹配v给定一个二分图给定一个二分图G，在，在G的一个子图的一个子图M中，中，M的边集的边集E中的任意两条边都不依附于同一个中的任意两条边都不依附于同一个顶点，则称顶点，则称M是一个匹配。是一个匹配。112233445最大匹配最大匹配v给定一个二分图给定一个二分图G，在，在G的一个子图的一个子图M中，中，M的边集的边集E中的任意两条边都不依附于同一个中的任意两条边都不依附于同一个顶点，则称顶点，则称M是一个匹配。是一个匹配。v选择这样的边数最大的子集称为图的最大匹选择这样的边数最大

4、的子集称为图的最大匹配问题配问题(maximal matching problem)v如果一个匹配中，图中的每个顶点都和图中如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也某条边相关联，则称此匹配为完全匹配，也称作完备匹配。称作完备匹配。匈牙利算法匈牙利算法v求最大匹配的一种显而易见的算法是：先找求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。此，需要寻求一种更加高效的算法。v增广路的定义增广路

5、的定义(也称增广轨或交错轨也称增广轨或交错轨)： 若若P是图是图G中一条连通两个未匹配顶点的路径，中一条连通两个未匹配顶点的路径，并且属并且属M的边和不属的边和不属M的边的边(即已匹配和待匹即已匹配和待匹配的边配的边)在在P上交替出现，则称上交替出现，则称P为相对于为相对于M的的一条增广路径。一条增广路径。匈牙利算法匈牙利算法v由增广路的定义可以推出下述三个结论：由增广路的定义可以推出下述三个结论：v1P的路径长度必定为奇数，第一条边和最的路径长度必定为奇数，第一条边和最后一条边都不属于后一条边都不属于M。v2P经过取反操作可以得到一个更大的匹配经过取反操作可以得到一个更大的匹配M。v3M为为

6、G的最大匹配当且仅当不存在相对于的最大匹配当且仅当不存在相对于M的增广路径。的增广路径。匈牙利算法匈牙利算法v用增广路求最大匹配用增广路求最大匹配(称作匈牙利算法，匈牙称作匈牙利算法，匈牙利数学家利数学家Edmonds于于1965年提出年提出)v算法轮廓：算法轮廓：v(1)置置M为空为空v(2)找出一条增广路径找出一条增广路径P，通过取反操作获得，通过取反操作获得更大的匹配更大的匹配M代替代替Mv(3)重复重复(2)操作直到找不出增广路径为止操作直到找不出增广路径为止 算法的核心就是根据一个初始匹配不停算法的核心就是根据一个初始匹配不停的找增广路，直到没有增广路为止。的找增广路，直到没有增广路

7、为止。 找增广路的时候既可以采用找增广路的时候既可以采用dfs也可以也可以采用采用bfs，两者都可以保证，两者都可以保证O(nm)的复杂度，的复杂度，因为每找一条增广路的复杂度是因为每找一条增广路的复杂度是O(m)，而，而最多增广最多增广n次，次，dfs在实际实现中更加简短在实际实现中更加简短。匈牙利算法匈牙利算法v题目大意：有题目大意：有P门课程，门课程，N个学生，一些学生个学生，一些学生选了一些课，某个学生可能选选了一些课，某个学生可能选1门或多门课程，门或多门课程，也可以一门也不选。现在从学生中选每门课也可以一门也不选。现在从学生中选每门课的课代表，如果某个学生已经当了某门课的的课代表，

8、如果某个学生已经当了某门课的代表，就不能代表别的课了。一门课也只能代表，就不能代表别的课了。一门课也只能有一个课代表。由这些课代表组成了一个代有一个课代表。由这些课代表组成了一个代表委员会。现在给出学生选课的情况，求这表委员会。现在给出学生选课的情况，求这P门课是否都能够找到学生来做代表。门课是否都能够找到学生来做代表。例题1 Courses（hdu1083）v题目大意：有题目大意：有P门课程，门课程，N个学生，一些学生选了一些课，个学生，一些学生选了一些课，某个学生可能选某个学生可能选1门或多门课程，也可以一门也不选。现在门或多门课程，也可以一门也不选。现在从学生中选每门课的课代表，如果某个

9、学生已经当了某门课从学生中选每门课的课代表，如果某个学生已经当了某门课的代表，就不能代表别的课了。一门课也只能有一个课代表。的代表，就不能代表别的课了。一门课也只能有一个课代表。由这些课代表组成了一个代表委员会。现在给出学生选课的由这些课代表组成了一个代表委员会。现在给出学生选课的情况，求这情况，求这P门课是否都能够找到学生来做代表。门课是否都能够找到学生来做代表。例题1 Courses（hdu1083）v解题思路：本题是一道典型的二分图最大匹配解题思路：本题是一道典型的二分图最大匹配题。采用匈牙利算法。本题的题。采用匈牙利算法。本题的构图构图是这样的，是这样的，左右两边的左右两边的x和和y，

10、分别是，分别是x学生，学生，y课程。那么课程。那么已知哪些学生可以学哪些课，也就是在已知哪些学生可以学哪些课，也就是在x的点的点 和和y的点之间首先连上线。求的点之间首先连上线。求xy的的最大匹配最大匹配。如果。如果有有P个学生做了课代表，那么就是个学生做了课代表，那么就是P门课程都有门课程都有课代表了。课代表了。v样例样例v3 3v3 1 2 3v2 1 2v1 1123213X学生学生Y课程课程（1）建图）建图例题1 Courses（hdu1006）123213X学生学生Y课程课程（1）建图）建图例题1 Courses（hdu1006）123213X学生学生Y课程课程（2）连接连接x1-y

11、1x2-y2得 到 此得 到 此匹 配 ，匹 配 ，匹 配 数匹 配 数为为2.123213X学生学生Y课程课程（3）例题1 Courses（hdu1006）123213X学生学生Y课程课程（2）连接连接x1-y1x2-y2得 到 此得 到 此匹 配 ，匹 配 ，匹 配 数匹 配 数为为2.要使要使x3找找到 匹 配 ，到 匹 配 ，只 能 找 到只 能 找 到与 它 相 连与 它 相 连的的y1,此时此时需 要 删 除需 要 删 除x1-y1123213123213X学生学生Y课程课程（3）例题1 Courses（hdu1006）X学生学生Y课程课程（4）再尝试再尝试x1与 其 他 点与 其

12、 他 点连 ， 尝 试连 ， 尝 试x1-y2,此此时 需 要 删时 需 要 删除除x2-y2,无 法 找 到无 法 找 到与与x2连接连接的新边的新边,此此尝试失败。尝试失败。要使要使x3找找到 匹 配 ，到 匹 配 ，只 能 找 到只 能 找 到与 它 相 连与 它 相 连的的y1,此时此时需 要 删 除需 要 删 除x1-y1123213123213X学生学生Y课程课程（5）例题1 Courses（hdu1006）X学生学生Y课程课程（4）再尝试再尝试x1与 其 他 点与 其 他 点连 ， 尝 试连 ， 尝 试x1-y2,此此时 需 要 删时 需 要 删除除x2-y2,无 法 找 到无

13、法 找 到与与x2连接连接的新边的新边,此此尝试失败。尝试失败。再尝试再尝试x1-y3,得到匹配数得到匹配数3X1-y3,X2-y2,X3-y1123213123213123213例题1 Courses（hdu1006）（4）123213（5）123213123213123213（2）123213（3）（1）X学生学生Y课程课程 while(cases-) scanf(%d%d,&P,&N);/课程数课程数 学生数学生数 memset(link,0,sizeof(link); for(y=1;y=P;+y) scanf(%d,&j);/一共有一共有j个学生学个学生学y课

14、课程程 for(i=1;i=j;+i) scanf(%d,&x); linkxy=1;/x学生学习学生学习y课程课程 int gg=MMG(); if(gg=p)printf(YESn);/coutYESendl; else printf(NOn);/coutNOendl; return 0;#includeint link303303;int used303,mathy303;using namespace std;int P,N;int find(int x)/x学生可以匹配到某课程学生可以匹配到某课程么么 /可以返回可以返回1，不可以返回，不可以返回0 int MMG() /计算

15、最大匹配数，计算最大匹配数， 调用了调用了find int main( ) int x,y,i,j; int cases; scanf(%d,&cases); int MMG() int x ,sum=0,j; memset(matchy,-1,sizeof(matchy); for(x=1;x=N;+x) /以此考查每个学生以此考查每个学生 memset(used,0,sizeof(used);/x学生尚未代表任何一门课程学生尚未代表任何一门课程 if(find(x) /x学生代表了某课学生代表了某课程，程，x匹配到了某课程匹配到了某课程 sum+; /被代表的课程数加被代表的课程数

16、加1 return sum;int find(int x)/x学生可以匹配到某课程么学生可以匹配到某课程么 for(int y=1;y=P;y+) if(!usedy&linkxy) /如果如果y课程尚未被代表掉，并且课程尚未被代表掉，并且x学生学生学习学习y课程课程 usedy=1;/y课程标记为被代表了课程标记为被代表了 if(matchyy=-1|find(matchyy) /如果如果y尚未被其他学生代表掉，尚未被其他学生代表掉，/或者代表或者代表y课程的学生课程的学生matchyy可以找可以找到别的课程来做代表到别的课程来做代表 matchyy=x;/课程课程y由学生由学生x代

17、表代表了。这里的了。这里的y匹配了匹配了x。 return 1; return 0; 例题2 Place the Robots（ZOJ1654）问题描述问题描述 有一个有一个N*M(N,M=50)的棋盘，的棋盘，棋盘的每一格是三种类型之一：空棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们多可以放置多少个机器人，使它们不能互相攻击。不能互相攻击。

18、 Wall Grass Empty例题2 Place the Robots（ZOJ）模型一模型一5467832112346578于是，问题转化为求图的最大独立于是，问题转化为求图的最大独立集问题。集问题。在问题的原型中，草地，墙这些信在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的我们很自然想到了下面这种简单的模型：模型：以空地为顶点，有冲突的空地间连以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：边，我们可以得到右边的这个图：我们将每一行，每一列

19、被墙隔开，我们将每一行，每一列被墙隔开，且包含空地的连续区域称作且包含空地的连续区域称作“块块”。显然，在一个块之中，。显然，在一个块之中，最多只能放一个机器人。我们把最多只能放一个机器人。我们把这些块编上号。这些块编上号。同样，把竖直方向的块也编上号。同样，把竖直方向的块也编上号。例题2 Place the Robots（ZOJ）模型二模型二123451234例题2 Place the Robots（ZOJ）模型二模型二123451234把每个横向块看作把每个横向块看作X X部的点，竖向部的点，竖向块看作块看作Y Y部的点，若两个块有公共部的点，若两个块有公共的空地，则在它们之间连边。的空地

20、，则在它们之间连边。于是，问题转化成这样的一个二于是，问题转化成这样的一个二部图：部图：112233445由于每条边表示一个空地，有冲由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配以问题转化为二部图的最大匹配问题。问题。例题2 Place the Robots（ZOJ）模型二模型二123412354112233445由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。例题2 Place the Robots（ZOJ）模型二模型二123412354112233445给定一个二分图给定一个二分图

21、G，在，在G的一个子图的一个子图M中，中，M的边集的边集E中的任意两条边都不依附于中的任意两条边都不依附于同一个顶点，则同一个顶点，则称称M是一个匹配是一个匹配。选择这样的边数最大的子集称为图的选择这样的边数最大的子集称为图的最大最大匹配问题匹配问题(maximal matching problem)比较前面的两个模型：模型一过于简单，没有给问比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充分抓住了问题的内题的求解带来任何便利；模型二则充分抓住了问题的内在联系，巧妙地建立了二部图模型。为什么会产生这种在联系，巧妙地建立了二部图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：截然不同的结果呢？其一是由于对问题分析的角