二分图毕业论文

本科生毕业论文设计题目 二分图的判断、算法及应用 作者姓名 纪晔 指导教师 田子红 所在学院 汇华学院 专 业 数学与应用数学 班级（届） 2012届2班 完成日期 2012 年 05 月 01 日目录中文摘要、关键词II引言11、图及二分图的概念 12、二分图的性质 43、二分图的判断 63.1定义法 63.2着色法 73.3回路判别法 84、二分图匹配算法简介 10 4.1二分图的最大匹配 114.2 HK算法124.3二分图最优匹配 124.4极小覆盖的求法 134.5最短路算法 145、用二分图巧解实际问题 156、结论 20参考文献 21英文摘要、关键词III二分图的算法、判别及应用摘要 在日常生活、生产活动及科学研究中，人们常用点表示事物比如人群、城市、网络等等，用点与点之间是否有连线表示事物之间是否有某种关系，这样构成的图形称为图。本文通过对图、二分图等概念的诠释，归纳出二分图的性质，得到了匈牙利、HK等各种算法，最后总结出二分图的判断方法以及其在实际问题中的应用。 关键词 图，二分图，匹配，HK算法 二分图的算法、判别及应用引言图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，如1736 年欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题，匿门博奕问题，棋盘上马的行走路线问题等。这些古老的难题，当时吸引了很多学者的注意，在这些问题研究的基础上又继续提出了著名的四色猜想，汉密尔顿数学难题。1847 年，克希霍夫 (Kirchhoff) 用图论分析电路网络，这是图论最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。图论在各种物理学科，工程领域，社会科学和经济问题的广泛应用，使它受到数学和工程界的特别重视。对于这样一门应用广泛的学科，在实际生活中的应用也是屡见不鲜。如今孩子们的婚姻成了家长们最关心的话题，随着近几年离婚率的提升，如何选择一个稳定的适合自己的伴侣呢？也许您会问道，这是用了我们数学中的哪部分知识来解决的？这就是组合数学二分图匹配中著名的婚姻稳定问题，它与我们的生活息息相关。那么什么是二分图，二分图又具有哪些性质，如何判断二分图，二分图匹配有哪些具体的算法，以及在生活中有什么应用呢？下面就让我们一起走入二分图的多彩世界！1.图的基本概念图：一个图是指一个有序三元组，其中是非空的顶点集，是不与相交的边集，而是关联函数，它使的每条边对应于的无序顶点对。若是一条边，而和是使得的顶点，则称连接和；顶点和称为的端点。一条边的端点称为与这条边关联。环：端点重合为一点的边称为环。连杆：端点不相同的边称为连杆。例1：这里， 而定义为例2：给出的一个图形，其中就是一个环，的其余边都是连杆。简单图：如果一个图既没有环也没有两条连杆连接同一对顶点，我们就说这样的图是简单图。例3：给出的一个图形图中没有任何环且无任意两条连杆连接同一顶点对，该图就为一个简单图。图的同构：一般来说，两个图和称为同构，如果存在两个一一映射：和：，使得当且仅当；这样一个映射对称为和之间的一个同构。两个图和是恒等的，如果， 。显然两个恒等的图可用同一个图形来表示，差别在于它们的顶点和边有不同的标号。完全图：每一对不同的顶点都有一条边相连的简单图称为完全图。在同构意义下，个顶点的完全图只有一个，记为。二分图：指一个图的顶点集可以分解为两个（非空）子集和，使得每条边都有一个端点在中，另一个端点在中；这样一种分类称为图的一个二分类。完全二分图：是指具有二分类的简单二分图，其中的每个顶点都与的每个顶点相连；若而，则这样的图记为，。例4：由立方体的顶点和边所确定的图图是二分图，图为完全二分图。关于二分图和完全二分图的判断，在下面的判别方法中会做详细阐述。2.二分图的性质为了介绍图的基本性质，我们先引入一些术语和符号。点覆盖：是指从图中找出一个点集，使得图中任意边与点集中某点相关联。 最小点覆盖：设，,若对于，使得与相关联，则称覆盖，并称为的点覆盖集或者点覆盖；顶点个数最少的点覆盖称为最小点覆盖。 匹配：给定简单无向图，若且中任意两条边都不邻接的，则子集称为的一个匹配（或者称之为对集）。完美匹配和最大匹配：如果是的一个匹配，若中的边与结点关联，则称是一饱和的；若中的每个结点都是一饱和的，则称是完全匹配。如果中没有匹配，使，则称是最大匹配。独立集：是指图的顶点集的一个子集，该子集的导出子图不含边。最大独立集：一个图中包含顶点数目最多的独立集称为最大独立集。最大独立数：从个顶点中选出个顶点，使得这个顶点互不相临。那么最大的就是这个图的最大独立数。极大独立集：设是的一个独立集，并且对于中的任一顶点，都不是的独立集，则称是的一个极大独立集。性质：1) 二分图的最小点覆盖数等于该二分图的最大匹配数。2) 二分图的顶点数减去其最大匹配数等于该二分图的最大独立集。3) 对于任何无向图，最大独立数加上最大匹配数等于图的顶点数。4) 设二部图中，中存在到的完备匹配当且仅当中任意个顶点与中个顶点相邻。5） 设二部图中，中每个顶点至少关联条边，而中每个顶点至多关联条边，则中存在到的完备匹配。6） 设为二部图，则。对加以证明，定理的必然性是显然的，下面证明充分性，即证只要满足相异性条件，中最大匹配一定是完备匹配。设为的一个最大匹配，若不是完备匹配，必存在为的非饱和点，且必存在与关联，否则将是孤立点，这与相异性条件矛盾，并且与相邻的顶点都是饱和点。若存在为饱和点，则也是匹配，这显然与为最大匹配矛盾。于是令，由于各条交错路径的两个端点都在中，所以。这说明中个顶点只与中个顶点相邻，这与相异性条件矛盾，因而中不可能存在非饱和点。故是完备匹配。3.二分图的判断3.1定义法根据二分图定义，把握定义要点。可以分解为两个（非空）子集和，使得每条边都有一个端点在中，另一个端点在中。例1：判断下图是否为二分图？abcdefg解：根据二分图定义，我们可以尝试着把顶点分为a，b，d和c，e，f，g两个非空集合。我们可以发现每条边都连接这两个非空集合里的顶点，根据定义可以判定这个图为二分图。3.2“着”色法首先将任意一个顶点赋以红色，然后将其相邻接的顶点赋以蓝色，按照这样的着色方法能否将全部顶点附上颜色，并且相邻接的顶点颜色不同。如果可以我们就可以判定该图为二分图。（只假设红、蓝两种颜色）方法证明：如果假设为二分图，那么它是由和两个互不相交且不为空集的顶点构成的。每一条边都连接着和中的顶点。我们如果对于U中的每个顶点赋以红色，而中的顶点赋以蓝色，那么相邻接的顶点就不会被赋以相同的颜色，从而该方法可以判别。例2：判断下图是否为二分图？bacdef解：为了不失一般性，我们假设a赋以红色，那么必须对b和f赋以蓝色，因为他们每个都与a邻接。同理，我们再赋以c、d和e红色，由于分别与f和d邻接。但是c和d，d和e相邻接并且还赋以了相同的颜色，与我们着色法不相符，所以判定该图不为二分图。问题延伸：那么对于例1中的图，我们也用着色法进行一下判断，是否可行呢？我们假设a点赋以红色，那么与a相邻接的c、e、f和g点我们赋以蓝色；再把与c、e、f、g点相邻接的顶点赋以红色，得出a、b、d为红色。我们可以发现图中所有点都被赋以了颜色，并且相邻接的点的颜色都不相同。所以我们可以判断例1中的图为二分图。3.3回路判别法圈（回路）：称一条途径是闭的，如果它有正的长且起点和终点相同。若一条闭迹的起点和内部顶点互不相同，则它称为圈。奇圈：如果长为的圈且为奇数，称圈为奇圈。定理：一个图是二分图当且仅当中不含奇圈。 abcde我们就可以说a、b、c、d、a就是长度为4的回路。例3判断下图是否为二分图？abcefdgh解：根据我们回路判别法，能否找出图中任何一个回路是由奇数条不同的边构成的。比如a、h、c、d、a是长度为4的回路；a、g、c、d、a也是长度为4的回路；a、f、c、d、a是长度为4的回路；a、e、c、d、a也是长度为4的回路我们会发现所有回路长度均不会为奇数，所以可以判断该图是二分图。问题延伸：如果遇到顶点和边数比较多的图，过程就会过于繁杂，而带来不必要的麻烦，对于例3有没有更简便的解决办法呢？我们再重新看下例3中的图abcefdgha、b、c三点互不相交；d、e、f、g、h也互不相交，并且a、b、c分别与d、e、f、g、h各由一条边连接。具有一定的规律和对称性，跟例1和例2中的图对比起来，优越性要强很多。那么我们就把a、b、c和d、e、f、g、h分别看成是由顶点构成的子集。当且仅当一个顶点属于a、b、c，而另一个顶点属于d、e、f、g、h，从而形成顶点之间的边，那么我们就规定这样的二分图为完全二分图。一个顶点集数为2，一个顶点集数为5，我们就把例3中的完全二分图，记作。以后我们在预见类似例3中的图，就可以直接运用完全二分图的概念来解决问题，从而省去了不必要的麻烦。小结：我们在探讨完二分图判定的三种方法之后，做一简单比较。定义法可以用在各种二分图的判定之中，但是考虑到顶点个数较多，从而可操作性就显得差了一些。“着”色法，利用了我们数学中的反证的思想，只要存在一组不满足相邻顶点着色不同的条件，就可以判断该图不是二分图，从而省去了大量的繁杂的过程，比较简便。而对于回路判别法，它为二分图的判定开辟了一条新的思路，与路径的知识结合在一起，为二分图的判定方法锦上添花，但是考虑的回路条数过多，容易出错，所以此方法也用在顶点数目较少的情况下。4.二分图算法简介二分图匹配算法是二分图的一个重要组成部分，也是我们解决实际问题方面的基础和工具。4.1二分图的最大匹配增广路：令是图中的一个匹配。若存在一个链，它是分别由和中的边交替构成，则称该链是中的一交错链；若一交错链的始节点和终结点都是一不饱和的，则称该链为一增广链（路）。二分图最大匹配的匈牙利算法是由Edmonds提出的，该算法主要中心就是由一个初始匹配不断的寻找增广路，一直到找不到增广路为止。 #define N 202 int useifN; /记录y中节点是否使用 int linkN; /记录当前与y节点相连的x的节点 int matNN; /记录连接x和y的边，如果i和j之间有边则为1，否则为0 int gn,gm; /二分图中x和y中点的数目 int can(int t) int i; for(i=1;i=gm;i+) if(useifi=0 & matti) useifi=1; if(linki=-1 | can(linki) linki=t; return 1; return 0; int MaxMatch() int i,num; num=0; memset(link,0xff,sizeof(link); for(i=1;i=gn;i+) memset(useif,0,sizeof(useif); if(can(i) num+; return num; 算法点拔：该算法的中心就是不停的寻找增广路，匹配的个数同时也得到了增加。增广路也就是说这条由图的边组成的路径，它的第一条边并没有参与匹配的，而第二条边参与了匹配，第三条没有直到最后一条边没有参与匹配，且初始点和终点并没有被选择过。以这样的规律进行下去，显然边的数目为奇数。那么对于这个路径，我们反过思路来考虑，把第一条变改为参与匹配，而第二条没有，以此类推。很容易的就发现这样变动后，匹配仍然成立，但是却增加了一对匹配。这就是匈牙利算法的思路。要点分析： 1每个节点都最多只能成为增广路的一个起点2若一个节点已经被匹配了，那么增广路此时的路径只能是走到该Y节点的匹配4.2 HK-算法算法点拨：HK算法的核心不同于匈牙利算法的是同时寻找多条不相交的最短增广路，且沿着这些最小增广路同时进行，而不是像匈牙利算法只进行一条增广路进行增广。算法：在0（e）的时间复杂度内找到极大最短增广路集，首先从所有X的未盖点进行BFS，BFS之后对每个X节点和Y节点维护距离标号，如果Y节点是未盖点那么就找到了一条最短增广路，BFS完之后就找到了最短增广路集，随后可以直接用DFS对所有允许弧(disty=distx+1)进行类似于匈牙利中寻找增广路的操作，这样就可以做到0（m）的复杂度。4.3二分图最优匹配算法二分图最优分配的经典算法是由Kuhn和Munkres独立提出的。算法点拨：KM算法中关键是可行顶点标号，也就是节点的是函数并且对于任意弧(x,y)满足l(x)+l(y)w(x,y)。如果只包含满足l(xi)+l(yj)=w(xi,yj)的所有弧(xi,yj)，我们就可以说G是一个生成子图，也就是相等的子图。定理：设是的可行顶点标号，若包含完美对集，则 是的最优对集。算法：1从任一可行顶点标号开始，然后绝对，并且在中选取任一对集。若是饱和的，则是完美对集，并且是最优对集；在这种情形下，算法可以终止。否则，令是非饱和顶点，置，。2若，则可以直接跳转到第3步，否则。计算且由若 ，若； 其他情况。给出可行顶点标号。以代替，以代替。3在中选择一个顶点。若是饱和的，并且，则用代替，用代替，再转到第二步否则，设是中的可扩路，并转到第一步。KM的算法主要为了达到完美匹配，而去如何控制可行顶标的一个算法。首先，我们假设一个可行顶标，然后在相等子图中寻找增广路，如果寻找到增广路就继续进行下去，如果没有找到增广路那么就在匈牙利树中的节点，所有现在在匈牙利树中的节点，考察所有一段在S集合，一段在not T集合中的弧，取delta = min l(xi)+l(yj)-w(xi,yj),xi S, yj not T。如果所有集合中l(xi)减少delta之后，肯定会出现至少一条属于(S,not T)的边进入相等子图，然后我们就继续扩展匈牙利树，从而使得属于(S,T)的边不退出相等子图，并且把所有在集合中的点的可行顶标增加delta。随着上述算法的进行，若新加入的节点是未覆盖点，可以找到增广路，如果不可以，我们就把该节点对应的匹配加入其中，看能否找到增广路。4.4极小覆盖的求法算法点拨：对于每个顶点，选择或者选择的所有顶点。为了有效的执行程序，我们利用了代数方法。算法：指令“选择与，或者与”记为。根据法则简化逻辑表达式得最后化简得到的从而得到,是的极小覆盖，取其补集就可以得到的所有极大独立集。极小覆盖的求法在图着色问题中经常用到，后Christofides给出了关于这个程序算法的一些改进。4.5最短路Dijkstra算法算法点拨：该算法是Dijkstra以及Whiting和Hillier各自独立发现的。这个算法不仅找到了最短的路，而且给出了从到的所有其他顶点的最短路。算法：1置，对，且。2对每个，用代替。计算，并把打到这个最小值的一个顶点记为，置。3若，则停止。若，则用代替，并转入第二步。当算法结束时，从到的距离由标号的终值给出。算法总结：虽然最短路的一些问题可以用该算法予以解决，但是在图论中还有许多较为复杂的问题不可以用该算法予以解决。5.二分图的应用通过对二分图定义、判断、算法的介绍，对二分图有了一定的了解，下面介绍二分图在实际生活中的应用。情景一：在我市就业市场双选会上，有个毕业本科生从个工作岗位上选择自己的职业。已经知道每个毕业生至少愿意去（1）个单位工作，并且每个单位至多看中了其中个毕业生，可以从其中选择一个。问最多可以有几个单位可以选择到自己满意的毕业生？试试写出判断过程。情景分析：可以看出这是一个关于二分图运用在招聘用人方面上的实际应用问题。名本科毕业生作为一个子集，用人单位作为另一个子集，运用二分图匹配中著名的“条件”定理可以解决此问题。定理：设二分图中，中每个顶点至少关联（1）条边，而中每个顶点至多关联条边，则中存在到的完全匹配，在性质中已经提到。解：我们首先设为毕业生的集合，为用人单位的集合，集合表示毕业生愿意到单位工作，那么我们就可以把就是为一个二分图。根据我们刚才分析可以知道，对于任何一个毕业生都至少愿意去个单位我们就表示为，并且每个用人单位都至多看中其中的个毕业生，所以我们表示成。我们可以发现该条件正好满足条件定理，所以存在到的的完美匹配，该完美分配。得到最多有个单位找到自己满意的毕业生，所有学生都可以找到自己愿意去的单位。总结：该类计算的要点，是通过题意找到题目中两个集合的度，并且计算是否满足条件定理，找个一个合理的分配方案即可。情景二： 某杂志社发表了7个征求答案的题目，当从读者寄来的解答中挑选出每道题的两个答案准备发表时，编辑发现所有14个挑选出来的解答恰好是7个读者提出的，而且他们每人正好提供了不同题目的两个答案。请说明：编辑可以这样发表每道题的一个答案，使得发表的解答中，这7个读者中每人都有一个解答。情景分析：该问题就是条件定理的一个典型应用问题。解：设，则为一个二分图。满足条件且，故有完美匹配，从而编辑可以这样发表每道题的答案，使得在发表的解答中这7个读者中每人都有一个解答。情景三：有四名老师张、王、李、赵，学校准备分别派他们教四门课程，但是这四名老师提交的简历中，让教务处主任头疼了。张老师可以教外语和数学，王老师可以教语文和政治，李老师可以教语文、数学和外语，赵老师只会教外语。教务处主任应该如何去分配，才能使每个老师都有课程可教，也不会让任何老师去教自己不会的课程？情景分析：这是一个关于解决人员任务的派遣和官职任务的实际问题。可以利用二分图的完全匹配来解决该类问题，把教师看成为一个集合分别用表示张、王、李、赵；把所教课程看作另外一个集合分别用表示语文、数学、英语、政治。定理：若是二部图，并且对于任意或有，则有一个完全匹配。解：令，并且可以得到。于是我们现在的问题就变成了寻找中的一个完全匹配。作图如下：abcdCmep赵老师只会教英语，那么我们表示成；由于英语已经让张老师教了，所以张老师只能去教数学，表示成；因为语文剩下的王老师和李老师都会教，但是政治只有的王老师会教，所以分配王老师教政治，李老师教语文表示为和。那么就得到了一个完全匹配=，即可作为教师任课的分配方案。情景四：在新中国刚成立的时候，敌我双方都展开了间谍大战，我方一举抓获了台湾6名间谍a、b、c、d、e和f，每个间谍都精通多国语言，a会汉语、法语和韩语；b会德语、韩语和俄语；c会英语和法语；d会汉语和西班牙语；e会英语和德语；f会俄语和西班牙语。现在有2间牢房，如何将这6名间谍监禁并且还不让他们互相交流？情景分析：这个是一个二分图在我国侦破间谍上的应用。这一类问题，只要运用二分图的概念就可以解决，题目中要求分别关在2间牢房，并且还不能让间谍间互相交流，我们就尝试着把a、b、c、d、e、f分成2个集合，并且2个集合中的元素不能有邻接，若两人至少会同一中语言则相应的两节点邻接。解：由于a分别与b、c、d邻接，同时f和e都不与b、c、d都不邻接，得到，分别监禁在不同的房间里，可以使得在同一房间里的间谍不能互相交流作图如下afedbc问题延伸：我们已经利用二分图的概念解决了该问题，同样还可以利用“着”色法来解决此问题。为了不失一般性，假设赋以红色，同时、都赋以蓝色；再将与相邻接的点、赋以红色，与相邻接的、赋以红色。检查上述过程，我们发现、被赋以了红色，、赋以了蓝色，从而解决了该问题。 可以发现一个二分图的实际应用问题还可以多个方法来解决。情景五：在一个美丽的村庄里各有5位年轻的男子和女子，每位女孩都喜欢村庄里的某些男子，而每个男子都愿意娶任何一位喜欢他的女子。假如愿意嫁给、；愿意嫁给、；愿意嫁给、；愿意嫁给、；愿意嫁给、。问：找出一个匹配方案，使得每个女子都嫁给了一个她喜欢的人并且要求男孩女孩都有配偶？情景分析：这个就是婚姻稳定问题，在引言中已经提到，类似于刚才提到的教师就职问题，但是不同的是人的感情不稳定，可能在选择之中会有所偏向。解：我们先找出一个匹配，使得每个男女孩都有配偶，在上述情景中已给出解法，直接给出结果， ， ，这样的一个组合。问题延伸：虽然我们已经解决了题目中的问题，但是考虑到男孩可能会有选择性，从而重新产生选择，这就涉及到了稳定组合，现在来一起讨论下这个问题。EJMALBCDKN第一轮：向求婚，同意了。第二轮：向求婚，同意了。第三轮：也向求婚，更喜欢，选择。第四轮：再向求婚，更喜欢，选择第五轮：再向求婚，同意了。第六轮：向求婚被拒绝，向求婚被拒绝，向求婚同意了。第七轮：向求婚被拒绝，向求婚同意。截至到第七轮，我们已经找到了一个稳定组合，。我们只是得到了其中的一个稳定组合，这样的组合还有很多种，由于人与人之间有偏好喜感，这里只做一个组合举例。情景六： 一家化工用品厂制造了种化学制剂，其中一些制剂是互不相容的，如果接触就会发生爆炸。为了预防危险情况的发生，该工厂希望把仓库分成不用的隔间，可以让互不相容的化学制剂储藏在不同的隔间里。问这个仓库至少应该分成几个隔间？情景分析：该类问题是图着色的问题，由于一个图的色数是它的顶点集所能分成的独立集的最小数目，又因为每个独立集都是极大独立集的子集，所以我们只要找出所有极大独立集就可以解决该问题了。解：首先构建一个图，其顶点集为，两个顶点和相连当且仅当化学制剂和互不相容，从而得到仓库的最小间隔数等于的色数。假设一共有7种化学制剂且互不相容如下图根据求极小覆盖算法，得到 与的乘积化简为。因此就得到了的最小点覆盖有， 取其补集就可以得到的所有极大独