《二分图毕业论文.doc》由会员分享，可在线阅读，更多相关《二分图毕业论文.doc（25页珍藏版）》请在金锄头文库上搜索。
1、本科生毕业论文设计题目 二分图的判断、算法及应用 作者姓名 纪晔 指导教师 田子红 所在学院 汇华学院 专 业 数学与应用数学 班级（届） 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二分图的算法、判别及应用
2、摘要 在日常生活、生产活动及科学研究中，人们常用点表示事物比如人群、城市、网络等等，用点与点之间是否有连线表示事物之间是否有某种关系，这样构成的图形称为图。本文通过对图、二分图等概念的诠释，归纳出二分图的性质，得到了匈牙利、HK等各种算法，最后总结出二分图的判断方法以及其在实际问题中的应用。 关键词 图，二分图，匹配，HK算法 二分图的算法、判别及应用引言图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，如1736 年欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题，匿门博奕问题，棋盘上马的行走路线问题等。这些古老的难题，当时吸引了很
3、多学者的注意，在这些问题研究的基础上又继续提出了著名的四色猜想，汉密尔顿数学难题。1847 年，克希霍夫 (Kirchhoff) 用图论分析电路网络，这是图论最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。图论在各种物理学科，工程领域，社会科学和经济问题的广泛应用，使它受到数学和工程界的特别重视。对于这样一门应用广泛的学科，在实际生活中的应用也是屡见不鲜。如今孩子们的婚姻成了家长们最关心的话题，随着近几年离婚率的提升，如何选择一个稳定的适合自己的伴侣呢？也许您会问道，这是用了我们数学中的哪部分知识
4、来解决的？这就是组合数学二分图匹配中著名的婚姻稳定问题，它与我们的生活息息相关。那么什么是二分图，二分图又具有哪些性质，如何判断二分图，二分图匹配有哪些具体的算法，以及在生活中有什么应用呢？下面就让我们一起走入二分图的多彩世界！1.图的基本概念图：一个图是指一个有序三元组，其中是非空的顶点集，是不与相交的边集，而是关联函数，它使的每条边对应于的无序顶点对。若是一条边，而和是使得的顶点，则称连接和；顶点和称为的端点。一条边的端点称为与这条边关联。环：端点重合为一点的边称为环。连杆：端点不相同的边称为连杆。例1：这里， 而定义为例2：给出的一个图形，其中就是一个环，的其余边都是连杆。简单图：如果一
5、个图既没有环也没有两条连杆连接同一对顶点，我们就说这样的图是简单图。例3：给出的一个图形图中没有任何环且无任意两条连杆连接同一顶点对，该图就为一个简单图。图的同构：一般来说，两个图和称为同构，如果存在两个一一映射：和：，使得当且仅当；这样一个映射对称为和之间的一个同构。两个图和是恒等的，如果， 。显然两个恒等的图可用同一个图形来表示，差别在于它们的顶点和边有不同的标号。完全图：每一对不同的顶点都有一条边相连的简单图称为完全图。在同构意义下，个顶点的完全图只有一个，记为。二分图：指一个图的顶点集可以分解为两个（非空）子集和，使得每条边都有一个端点在中，另一个端点在中；这样一种分类称为图的一个二分
6、类。完全二分图：是指具有二分类的简单二分图，其中的每个顶点都与的每个顶点相连；若而，则这样的图记为，。例4：由立方体的顶点和边所确定的图图是二分图，图为完全二分图。关于二分图和完全二分图的判断，在下面的判别方法中会做详细阐述。2.二分图的性质为了介绍图的基本性质，我们先引入一些术语和符号。点覆盖：是指从图中找出一个点集，使得图中任意边与点集中某点相关联。 最小点覆盖：设，,若对于，使得与相关联，则称覆盖，并称为的点覆盖集或者点覆盖；顶点个数最少的点覆盖称为最小点覆盖。 匹配：给定简单无向图，若且中任意两条边都不邻接的，则子集称为的一个匹配（或者称之为对集）。完美匹配和最大匹配：如果是的一个匹配
7、，若中的边与结点关联，则称是一饱和的；若中的每个结点都是一饱和的，则称是完全匹配。如果中没有匹配，使，则称是最大匹配。独立集：是指图的顶点集的一个子集，该子集的导出子图不含边。最大独立集：一个图中包含顶点数目最多的独立集称为最大独立集。最大独立数：从个顶点中选出个顶点，使得这个顶点互不相临。那么最大的就是这个图的最大独立数。极大独立集：设是的一个独立集，并且对于中的任一顶点，都不是的独立集，则称是的一个极大独立集。性质：1) 二分图的最小点覆盖数等于该二分图的最大匹配数。2) 二分图的顶点数减去其最大匹配数等于该二分图的最大独立集。3) 对于任何无向图，最大独立数加上最大匹配数等于图的顶点数。
8、4) 设二部图中，中存在到的完备匹配当且仅当中任意个顶点与中个顶点相邻。5） 设二部图中，中每个顶点至少关联条边，而中每个顶点至多关联条边，则中存在到的完备匹配。6） 设为二部图，则。对加以证明，定理的必然性是显然的，下面证明充分性，即证只要满足相异性条件，中最大匹配一定是完备匹配。设为的一个最大匹配，若不是完备匹配，必存在为的非饱和点，且必存在与关联，否则将是孤立点，这与相异性条件矛盾，并且与相邻的顶点都是饱和点。若存在为饱和点，则也是匹配，这显然与为最大匹配矛盾。于是令，由于各条交错路径的两个端点都在中，所以。这说明中个顶点只与中个顶点相邻，这与相异性条件矛盾，因而中不可能存在非饱和点。故
9、是完备匹配。3.二分图的判断3.1定义法根据二分图定义，把握定义要点。可以分解为两个（非空）子集和，使得每条边都有一个端点在中，另一个端点在中。例1：判断下图是否为二分图？abcdefg解：根据二分图定义，我们可以尝试着把顶点分为a，b，d和c，e，f，g两个非空集合。我们可以发现每条边都连接这两个非空集合里的顶点，根据定义可以判定这个图为二分图。3.2“着”色法首先将任意一个顶点赋以红色，然后将其相邻接的顶点赋以蓝色，按照这样的着色方法能否将全部顶点附上颜色，并且相邻接的顶点颜色不同。如果可以我们就可以判定该图为二分图。（只假设红、蓝两种颜色）方法证明：如果假设为二分图，那么它是由和两个互不
10、相交且不为空集的顶点构成的。每一条边都连接着和中的顶点。我们如果对于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、
11、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也
12、是长度为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
13、、e、f、g、h，从而形成顶点之间的边，那么我们就规定这样的二分图为完全二分图。一个顶点集数为2，一个顶点集数为5，我们就把例3中的完全二分图，记作。以后我们在预见类似例3中的图，就可以直接运用完全二分图的概念来解决问题，从而省去了不必要的麻烦。小结：我们在探讨完二分图判定的三种方法之后，做一简单比较。定义法可以用在各种二分图的判定之中，但是考虑到顶点个数较多，从而可操作性就显得差了一些。“着”色法，利用了我们数学中的反证的思想，只要存在一组不满足相邻顶点着色不同的条件，就可以判断该图不是二分图，从而省去了大量的繁杂的过程，比较简便。而对于回路判别法，它为二分图的判定开辟了一条新的思路，与路径的知识结合在一起，为二分图的判定方法锦上添花，但是考虑的回路条数过多，容易出错，所以此
