《数学建模二分图匹配》由会员分享，可在线阅读，更多相关《数学建模二分图匹配（31页珍藏版）》请在金锄头文库上搜索。
1、二分图匹配匈牙利算法简介及应用软件学院 周娟回 顾v上一讲：最大网络流问题v 江西省2012年数学建模B题 一等奖，华东交 通大学基础学院周琴、胡媛媛、郭文文同学在 论文中写到：“利用网络流算法的方法，得到最均匀的分 发方法，并且可以使得任何两位教师交叉共同 评阅一份试卷的情况也尽量均匀。”v “计算最大流的Dinic算法去安排阅卷。”v “Dinic算法是网络流的优化算法之一，每一 步对原图进行分层，然后用递归搜索的方式求 增广路，算法的时间复杂度是O(n2m)，n为有 向图的顶点数，m为有向图的边数。” 二分图的概念v二分图又称作二部图，是图论中的一种特 殊模型。v设G=(V,R)是一个无
2、向图。如顶点集V可 分割为两个互不相交的子集，并且图中每 条边依附的两个顶点都分属两个不同的子 集。则称图G为二分图。112233445最大匹配v给定一个二分图G，在G的一个子图M中，M 的边集E中的任意两条边都不依附于同一个 顶点，则称M是一个匹配。 112233445最大匹配v给定一个二分图G，在G的一个子图M中，M 的边集E中的任意两条边都不依附于同一个 顶点，则称M是一个匹配。v选择这样的边数最大的子集称为图的最大匹 配问题(maximal matching problem)v如果一个匹配中，图中的每个顶点都和图中 某条边相关联，则称此匹配为完全匹配，也 称作完备匹配。匈牙利算法v求最
3、大匹配的一种显而易见的算法是：先找 出全部匹配，然后保留匹配数最多的。但是 这个算法的复杂度为边数的指数级函数。因 此，需要寻求一种更加高效的算法。v增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径 ，并且属M的边和不属M的边(即已匹配和待 匹配的边)在P上交替出现，则称P为相对于M 的一条增广路径。匈牙利算法v由增广路的定义可以推出下述三个结论：v1P的路径长度必定为奇数，第一条边和最 后一条边都不属于M。v2P经过取反操作可以得到一个更大的匹配 M。v3M为G的最大匹配当且仅当不存在相对于 M的增广路径。匈牙利算法v用增广路求最大匹配(称作匈牙利算法，匈牙 利数
4、学家Edmonds于1965年提出)v算廓：v(1)置M为空v(2)找出一条增广路径P，通过取反操作获得 更大的匹配M代替Mv(3)重复(2)操作直到找不出增广路径为止算法的核心就是根据一个初始匹配不停 的找增广路，直到没有增广路为止。找增广路的时候既可以采用dfs也可以采 用bfs，两者都可以保证O(nm)的复杂度， 因为每找一条增广路的复杂度是O(m)，而 最多增广n次，dfs在实际实现中更加简短 。匈牙利算法v题目大意：有P门课程，N个学生，一些学生 选了一些课，某个学生可能选1门或多门课程 ，也可以一门也不选。现在从学生中选每门 课的课代表，如果某个学生已经当了某门课 的代表，就不能代
5、表别的课了。一门课也只 能有一个课代表。由这些课代表组成了一个 代表委员会。现在给出学生选课的情况，求 这P门课是否都能够找到学生来做代表。例题1 Courses（hdu1083）v题目大意：有P门课程，N个学生，一些学生选了一些课， 某个学生可能选1门或多门课程，也可以一门也不选。现在 从学生中选每门课的课代表，如果某个学生已经当了某门课 的代表，就不能代表别的课了。一门课也只能有一个课代表 。由这些课代表组成了一个代表委员会。现在给出学生选课 的情况，求这P门课是否都能够找到学生来做代表。例题1 Courses（hdu1083）v解题思路：本题是一道典型的二分图最大匹配题 。采用匈牙利算法
6、。本题的构图是这样的，左右 两边的x和y，分别是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-y1 x2-y2 得到此 匹配， 匹配数 为2.123213X学生Y课程（3）例题1 Courses（hdu1006）123213X学生Y课程（
7、2）连接 x1-y1 x2-y2 得到此 匹配， 匹配数 为2.要使x3找 到匹配， 只能找到 与它相连 的y1,此时 需要删除 x1-y1123213123213X学生Y课程（3）例题1 Courses（hdu1006）X学生Y课程（4）再尝试x1 与其他点 连，尝试 x1-y2,此 时需要删 除x2-y2, 无法找到 与x2连接 的新边,此 尝试失败 。要使x3找 到匹配， 只能找到 与它相连 的y1,此时 需要删除 x1-y1123213123213X学生Y课程（5）例题1 Courses（hdu1006）X学生Y课程（4）再尝试x1 与其他点 连，尝试 x1-y2,此 时需要删 除x2
8、-y2, 无法找到 与x2连接 的新边,此 尝试失败 。再尝试x1-y3, 得到匹配数3 X1-y3, X2-y2, X3-y1123213123213123213例题1 Courses（hdu1006）（4）123213（5）123213123213123213 （2）123213 （3）（1）X学生Y课程while(cases-) scanf(“%d%d“,/课程数 学生数memset(link,0,sizeof(link);for(y=1;y int link303303; int used303,mathy303; using namespace std; int P,N; int f
9、ind(int x) /x学生可以匹配到某课程 么/可以返回1，不可以返回0 int MMG() /计算最大匹配数，调用了find int main( ) int x,y,i,j;int cases;scanf(“%d“,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+; /被代表的课程数加1 return sum; int
10、find(int x) /x学生可以匹配到某课程么for(int y=1;y=P;y+)if(!usedy/y课程标记为被代表了if(matchyy=-1|find(matchyy)/如果y尚未被其他学生代表掉， /或者代表y课程的学生matchyy可以找 到别的课程来做代表matchyy=x;/课程y由学生x代表 了。这里的y匹配了x。return 1; return 0; 例题2 Place the Robots（ZOJ1654）问题描述有一个N*M(N,M=50)的棋盘 ，棋盘的每一格是三种类型之一： 空地、草地、墙。机器人只能放在 空地上。在同一行或同一列的两个 机器人，若它们之间没有
11、墙，则它 们可以互相攻击。问给定的棋盘， 最多可以放置多少个机器人，使它 们不能互相攻击。WallGrassEmpty例题2 Place the Robots（ZOJ）模型一5467832112346578于是，问题转化为求图的最大独立 集问题。在问题的原型中，草地，墙这些信 息不是我们所关心的，我们关心的 只是空地和空地之间的联系。因此 ，我们很自然想到了下面这种简单 的模型：以空地为顶点，有冲突的空地间连 边，我们可以得到右边的这个图：我们将每一行，每一列被墙隔开 ，且包含空地的连续区域称作“ 块”。显然，在一个块之中，最 多只能放一个机器人。我们把这 些块编上号。同样，把竖直方向的块也编
12、上号。例题2 Place the Robots（ZOJ）模型二123 4 51234例题2 Place the Robots（ZOJ）模型二123 4 51234把每个横向块看作X部的点，竖向 块看作Y部的点，若两个块有公共 的空地，则在它们之间连边。于是，问题转化成这样的一个二 部图：112233445由于每条边表示一个空地，有冲 突的空地之间必有公共顶点，所 以问题转化为二部图的最大匹配 问题。例题2 Place the Robots（ZOJ）模型二123412354112233445由于每条边表示一个空地，有冲突的 空地之间必有公共顶点，所以问题转 化为二部图的最大匹配问题。例题2 Pl
13、ace the Robots（ZOJ）模型二123412354112233445给定一个二分图G，在G的一个子图M中 ，M的边集E中的任意两条边都不依附 于同一个顶点，则称M是一个匹配。 选择这样的边数最大的子集称为图的最大 匹配问题(maximal matching problem)比较前面的两个模型：模型一过于简单，没有给问 题的求解带来任何便利；模型二则充分抓住了问题的内 在联系，巧妙地建立了二部图模型。为什么会产生这种 截然不同的结果呢？其一是由于对问题分析的角度不同 ：模型一以空地为点，模型二以空地为边；其二是由于 对原型中要素的选取有差异：模型一对要素的选取不充 分，模型二则保留了
14、原型中“棋盘”这个重要的性质。由 此可见，对要素的选取，是图论建模中至关重要的一步 。例题2 Place the Robots（ZOJ）小结例题3 打猎v猎人要在n*n的格子里打鸟，他可以在某一行 中打一枪，这样此行中的所有鸟都被打掉， 也可以在某一列中打，这样此列中的所有鸟 都打掉。问至少打几枪，才能打光所有的鸟 ？v建图：二分图的X部为每一行，Y部为每一列 ，如果(i,j)有一只鸟，那么连接X部的i与Y部 的j。v该二分图的最大匹配数则是最少要打的枪数 。【学习目标学习目标】1.1.掌握二分图匹配、最大匹配基本概念。掌握二分图匹配、最大匹配基本概念。 2.2.理解匈牙利算法，掌握用其求解二
15、分图最大理解匈牙利算法，掌握用其求解二分图最大 匹配。匹配。 3.3.掌握实际问题的构图，即建立模型。掌握实际问题的构图，即建立模型。【重点和难点重点和难点】因此本章的学习重点在掌握匈牙利算法原理因此本章的学习重点在掌握匈牙利算法原理 ，以便能在应用问题中正确使用，构图是难点，以便能在应用问题中正确使用，构图是难点 。 【知识点知识点】二分图、最大匹配、匈牙利算法二分图、最大匹配、匈牙利算法习题习题1 1、实现、实现 CoursesCourses，hdu1083hdu10832 2、实现、实现 Place the Robots, zoj1654Place the Robots, zoj16543 3、20072007年全国研究生数学建模试题年全国研究生数学建模试题D D题题邮邮 政运输网络中的邮路规划和邮车调度政运输网络中的邮路规划和邮车调度提示：其中涉及到货郎担问题，可以用匈牙提示：其中涉及到货郎担问题，可以用匈牙 利算法、动态规划等模型利算法、动态规划等模型4 4、学习、学习20122012江西省数学建模一等奖周琴论文江西省数学建模一等奖周琴论文下一讲 最小覆盖最小覆盖要求用最少的点（集合或集合的都行）让每条 边都至少和其中一个点关联。可
