二分图毕业论文.docx
- 文档编号:14835414
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:23
- 大小:251.36KB
二分图毕业论文.docx
《二分图毕业论文.docx》由会员分享,可在线阅读,更多相关《二分图毕业论文.docx(23页珍藏版)》请在冰点文库上搜索。
二分图毕业论文
本科生毕业论文设计
题目二分图的判断、算法及应用
作者姓名纪晔
指导教师田子红
所在学院汇华学院
专业数学与应用数学
班级(届)2012届2班
完成日期2012年05月01日
中文摘要、关键词II
引言1
1、图及二分图的概念1
2、二分图的性质4
3、二分图的判断6
3.1定义法6
3.2着色法7
3.3回路判别法8
4、二分图匹配算法简介10
4.1二分图的最大匹配11
4.2HK算法12
4.3二分图最优匹配12
4.4极小覆盖的求法13
4.5最短路算法14
5、用二分图巧解实际问题15
6、结论20
参考文献21
英文摘要、关键词III
二分图的算法、判别及应用
摘要在日常生活、生产活动及科学研究中,人们常用点表示事物比如人群、城市、网络等等,用点与点之间是否有连线表示事物之间是否有某种关系,这样构成的图形称为图。
本文通过对图、二分图等概念的诠释,归纳出二分图的性质,得到了匈牙利、HK等各种算法,最后总结出二分图的判断方法以及其在实际问题中的应用。
关键词图,二分图,匹配,HK算法
二分图的算法、判别及应用
引言
图论是近年来发展迅速而又应用广泛的一门新兴学科。
它最早起源于一些数学游戏的难题研究,如1736年欧拉所解决的哥尼斯堡七桥问题,以及在民间广泛流传的一些游戏难题,如迷宫问题,匿门博奕问题,棋盘上马的行走路线问题等。
这些古老的难题,当时吸引了很多学者的注意,在这些问题研究的基础上又继续提出了著名的四色猜想,汉密尔顿数学难题。
1847年,克希霍夫(Kirchhoff)用图论分析电路网络,这是图论最早应用
于工程科学,以后随着科学的发展,图论在解决运筹学,网络理论,信息论,控制论,博奕论以及计算机科学等各个领域的问题时,显示出越来越大的效果。
图
论在各种物理学科,工程领域,社会科学和经济问题的广泛应用,使它受到数学和工程界的特别重视。
对于这样一门应用广泛的学科,在实际生活中的应用也是屡见不鲜。
如今孩子们的婚姻成了家长们最关心的话题,随着近几年离婚率的提升,如何选择一个稳定的适合自己的伴侣呢?
也许您会问道,这是用了我们数学中的哪
部分知识来解决的?
这就是《组合数学》二分图匹配中著名的婚姻稳定问题,它与我们的生活息息相关。
那么什么是二分图,二分图又具有哪些性质,如何判断二分图,二分图匹配有哪些具体的算法,以及在生活中有什么应用呢?
下面就让我们一起走入二分图的多彩世界!
1.图的基本概念
图:
一个图G是指一个有序三元组VG,EG,其中VG是非空的顶点集,EG是不与VG相交的边集,而g是关联函数,它使G的每条边对应于G的无序顶点对。
若e是一条边,而u和v是使得:
ge=uv的顶点,则称e连接u和v;顶点u和v称为e的端点。
一条边的端点称为与这条边关联。
环:
端点重合为一点的边称为环连杆:
端点不相同的边称为连杆。
例1:
G二VG,EG,g
这里,VG]={u,v,w,x,y}
eg=abcdefgh
而;:
G定义为
gai;=uv,gb]=uu
gc二vw,gd二wx
ge二vx,gf二wx
gg二uxjgh二xy
例2:
给出G的一个图形,
其中e3就是一个环,G的其余边都是连杆。
简单图:
如果一个图既没有环也没有两条连杆连接同一对顶点,我们就说这样的
图是简单图。
例3:
给出G的一个图形
图中没有任何环且无任意两条连杆连接同一顶点对,该图就为一个简单图。
图的同构:
一般来说,两个图G和H称为同构,如果存在两个映射v
VG>VH和':
EG>EH,使得gu当且仅当;he-九勺这样一个映射对叮称为G和H之间的一个同构。
两个图G和H是恒等的,如果VG二VH,EG二EH,:
g」h。
显然两个恒等的图可用同一个图形来表示,差别在于它们的顶点和边有不同的标号。
完全图:
每一对不同的顶点都有一条边相连的简单图称为完全图。
在同构意义下,
n个顶点的完全图只有一个,记为Kn。
二分图:
指一个图的顶点集可以分解为两个(非空)子集X和丫,使得每条边都有一个端点在X中,另一个端点在丫中;这样一种分类X,Y称为图的一个二分类。
完全二分图:
是指具有二分类X,Y的简单二分图,其中X的每个顶点都与丫的
每个顶点相连;若|X|=m而Y=n,则这样的图记为Km,n,E(Km,nj=m,n
例4:
由立方体的顶点和边所确定的图
图a是二分图,图b为完全二分图。
关于二分图和完全二分图的判断,在下面的判别方法中会做详细阐述。
2.二分图的性质
为了介绍图的基本性质,我们先引入一些术语和符号。
点覆盖:
是指从图中找出一个点集v,使得图中任意边与点集中某点相关联。
最小点覆盖:
设G=:
:
V,E;,ME,若对于-eE,vM,使得v与e相关联,则称v覆盖e,并称M为G的点覆盖集或者点覆盖;顶点个数最少的点覆盖称为最小点覆盖。
匹配:
给定简单无向图GfV,E〔,若M5E且M中任意两条边都不邻接的,则子集M称为G的一个匹配(或者称之为对集)。
完美匹配和最大匹配:
如果M是G的一个匹配,若M中的边与结点v关联,则称v是M—饱和的;若G中的每个结点v都是M—饱和的,则称M是完全匹配。
如果G中没有匹配Mi,使|Mj>M,则称M是最大匹配。
独立集:
是指图的顶点集的一个子集,该子集的导出子图不含边。
最大独立集:
一个图中包含顶点数目最多的独立集称为最大独立集。
最大独立数:
从V个顶点中选出k个顶点,使得这k个顶点互不相临。
那么最大的k就是这个图的最大独立数。
极大独立集:
设K是G的一个独立集,并且对于VK中的任一顶点v,Kv都不是G的独立集,则称K是G的一个极大独立集。
性质:
1)二分图的最小点覆盖数等于该二分图的最大匹配数。
2)二分图的顶点数减去其最大匹配数等于该二分图的最大独立集。
3)对于任何无向图,最大独立数加上最大匹配数等于图的顶点数。
4)(Hall定理)设二部图G=(Vi,V2,E中,Ml乞也,G中存在V到5的完备匹
配当且仅当Vi中任意k个顶点与V2中k个顶点相邻。
5)设二部图G"Vi,V2,E;中,Vi中每个顶点至少关联tt-1条边,而V2中每个顶点至多关联t条边,则G中存在Vi到V的完备匹配。
6)设G「Vi,V2,E:
为二部图,则xG=2。
对Hall定理加以证明,
定理的必然性是显然的,下面证明充分性,即证只要满足相异性条件,G中最大匹配一定是完备匹配。
设M为G的一个最大匹配,若M不是完备匹配,必存在匕Vi为M的非饱和点,且必存在Ei二E-M与vx关联,否则vx将是孤立点,这与相异性条件矛盾,并且V2与vx相邻的顶点都是M-饱和点。
若存在7八2为饱和点,则M、MVx,Vy也是匹配,这显然与M为最大匹配矛盾。
于是令S={vv€V|且v在从Vx出发的交错路径上},
T={vv^V2且v在从vx出发的交错路径上},由于各条交错路径的两个端点都在S中,所以|S=T+1。
这说明Vi中T+1个顶点只与V2中T个顶点相邻,这与相异性条件矛盾,因而Vi中不可能存在M-非饱和点。
故M是完备匹配。
3•二分图的判断
3.1定义法
根据二分图定义,把握定义要点。
可以分解为两个(非空)子集X和丫,使得每条边都有一个端点在X中,另一个端点在丫中。
例1:
判断下图是否为二分图?
解:
根据二分图定义,我们可以尝试着把顶点分为{a,b,4}和{c,e,f,g}两个非空集合。
我们可以发现每条边都连接这两个非空集合里的顶点,根据定义可以判定这个图为二分图。
3.2“着”色法
首先将任意一个顶点赋以红色,然后将其相邻接的顶点赋以蓝色,按照这样的着色方法能否将全部顶点附上颜色,并且相邻接的顶点颜色不同。
如果可以我们就可以判定该图为二分图。
(只假设红、蓝两种颜色)
方法证明:
如果假设G为二分图,那么它是由U和V两个互不相交且不为空集的顶点构成的。
每一条边都连接着U和V中的顶点。
我们如果对于U中的每个顶点赋以红色,而V中的顶点赋以蓝色,那么相邻接的顶点就不会被赋以相同的颜色,从而该方法可以判别。
例2:
判断下图是否为二分图?
解:
为了不失一般性,我们假设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回路判别法
圈(回路):
称一条途径是闭的,如果它有正的长且起点和终点相同。
若一条闭迹的起点和内部顶点互不相同,贝U它称为圈。
奇圈:
如果长为k的圈且k为奇数,称k圈为奇圈。
定理:
一个图G是二分图当且仅当G中不含奇圈。
我们就可以说a、b、c、d、a就是长度为4的回路
例3判断下图是否为二分图?
解:
根据我们回路判别法,能否找出图中任何一个回路是由奇数条不同的边构成的。
比如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中的图
a、b、c三点互不相交;d、e、f、g、h也互不相交,并且a、b、c分别与d、e、f、g、h各由一条边连接。
具有一定的规律和对称性,跟例1和例2中的图对比起来,优越性要强很多。
那么我们就把{a、b、坯和{d、e、f、g、h}分别看成是由顶点构成的子集。
当且仅当一个顶点属于{a、b、c},而另一个顶点属于{d、e、f、g、h},从而形成顶点之间的边,那么我们就规定这样的二分图为完全二分图。
一个顶点集数为2,一个顶点集数为5,我们就把例3中的完全二分图,记作K3,5。
以后我们在预见类似例3中的图,就可以直接运用完全二分图的概念来解决问题,从而省去了不必要的麻烦。
小结:
我们在探讨完二分图判定的三种方法之后,做一简单比较。
定义法可以用在各种二分图的判定之中,但是考虑到顶点个数较多,从而可操作性就显得差了一些。
“着”色法,利用了我们数学中的反证的思想,只要存在一组不满足相邻顶点着色不同的条件,就可以判断该图不是二分图,从而省去了大量的繁杂的过程,比较简便。
而对于回路判别法,它为二分图的判定开辟了一条新的思路,与路径的知识结合在一起,为二分图的判定方法锦上添花,但是考虑的回路条数过多,容易出错,所以此方法也用在顶点数目较少的情况下。
4.二分图算法简介
二分图匹配算法是二分图的一个重要组成部分,也是我们解决实际问题方面的基础和工具
4.1二分图的最大匹配
增广路:
令M是图G=7,E中的一个匹配。
若存在一个链,它是分别由E—M和M中的边交替构成,则称该链是G中的M—交错链;若M—交错链的始节点和终结点都是M—不饱和的,则称该链为M—增广链(路)。
二分图最大匹配的匈牙利算法是由Edmonds提出的,该算法主要中心就是
由一个初始匹配不断的寻找增广路,一直到找不到增广路为止。
#defineN202intuseif[N];//记录y中节点是否使用
intlink[N];//记录当前与y节点相连的x的节点
intmat[N][N];//记录连接x和y的边,如果i和j之间有边则为1,否则为0
intgn,gm;//二分图中x和y中点的数目
intcan(intt)
{inti;for(i=1;i<=gm;i++)
{if(useif[i]==0&&mat[t][i])
{useif[i]=1;if(link[i]==-1||can(link[i]))
{link[i]=t;return1;}
}
}
return0;}
intMaxMatch()
{inti,num;num=0;memset(link,0xff,sizeof(link));for(i=1;i<=gn;i++)
{memset(useif,0,sizeof(useif));if(can(i))num++;}
returnnum;}
算法点拔:
该算法的中心就是不停的寻找增广路,匹配的个数同时也得到了增加。
增广
路也就是说这条由图的边组成的路径,它的第一条边并没有参与匹配的,而第二
条边参与了匹配,第三条没有…直到最后一条边没有参与匹配,且初始点和终点并没有被选择过。
以这样的规律进行下去,显然边的数目为奇数。
那么对于这个路径,我们反过思路来考虑,把第一条变改为参与匹配,而第二条没有,以此类推。
很容易的就发现这样变动后,匹配仍然成立,但是却增加了一对匹配。
这就
是匈牙利算法的思路要点分析:
1.每个X节点都最多只能成为增广路的一个起点
2.若一个丫节点已经被匹配了,那么增广路此时的路径只能是走到该丫节
点的匹配
4.2HK-算法
算法点拨:
HK算法的核心不同于匈牙利算法的是同时寻找多条不相交的最短增广路,且沿着这些最小增广路同时进行,而不是像匈牙利算法只进行一条增广路进行增广。
算法:
在0(e)的时间复杂度内找到极大最短增广路集,首先从所有X的未盖点
进行BFS,BFS之后对每个X节点和丫节点维护距离标号,如果丫节点是未盖点那么就找到了一条最短增广路,BFS完之后就找到了最短增广路集,随后可以直接用DFS对所有允许弧(dist[y]=dist[x]+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是一个生成子图,也就是相等的子图。
定理:
设l是G的可行顶点标号,若Gi包含完美对集M*,则M*是G的最优对集。
算法:
1.从任一可行顶点标号I开始,然后绝对Gi,并且在Gi中选取任一对集M。
若X是饱和的,则M是完美对集,并且M是最优对集;在这种情形下,算法可以终止。
否则,令u是M非饱和顶点,置S={u},T=i_。
2.若Nq(S)二T,贝U可以直接跳转到第3步,否则Ng(S)=T。
计算
aimin{丨x:
:
:
ly[「wxy}且由Iv=1v?
「ai若vSIv=Ivai,若
x申,y註
v・T;lv其他情况。
给出可行顶点标号I。
以代替I,以G代替Gi。
3.在Ng丨ST中选择一个顶点y。
若y是M饱和的,并且yzM,则用sU{z}代替S,用TU{y}代替T,再转到第二步否则,设p是Gi中的M可扩u,y路,并转到第一步。
KM的算法主要为了达到完美匹配,而去如何控制可行顶标的一个算法。
首先,我们假设一个可行顶标,然后在相等子图中寻找增广路,如果寻找到增广路就继续进行下去,如果没有找到增广路那么就在匈牙利树中的X节点,所有现
在在匈牙利树中的丫节点,考察所有一段在S集合,一段在notT集合中的弧,取deita=min{l(xi)+l(yj)-w(xi,yj),xi€S,yj€notT}。
如果所有集合中l(xi)减少delta之后,肯定会出现至少一条属于(S,notT)的边进入相等子图,然后我们就继续扩展匈牙利树,从而使得属于(S,T)的边不退出相等子图,并且把所有在T集合中的点的可行顶标增加delta。
随着上述算法的进行,若新加入的丫节点是未覆盖点,可以找到增广路,如果不可以,我们就把该节点对应的X匹配加入其中,看能否找到增广路。
4.4极小覆盖的求法
算法点拨:
对于每个顶点v,选择v或者选择v的所有顶点。
为了有效的执行程序,我们利用了代数方法。
算法:
指令“选择U与V,或者v与w”记为uvvw。
根据法则简化逻辑表达式得
uvvwuvx二uvuuvvxvwuvwvx最后化简得至U的
uvvwuvx=uvvwx从而得到{u、v},{v、w、x}是G的极小覆盖,取其补集就可以得到G的所有极大独立集。
极小覆盖的求法在图着色问题中经常用到,后Christofides给出了关于这
个程序算法的一些改进。
4.5最短路Dijkstra算法
算法点拨:
该算法是Dijkstra以及Whiting和Hillier各自独立发现的。
这个算法不仅找
到了最短的u0,v。
路,而且给出了从u。
到G的所有其他顶点的最短路。
算法:
1•置Iu。
=0,对v=u。
lv=:
S。
二{u。
}且i=0
>i
2.对每个v,用min{lv,IuiSi
把打到这个最小值的一个顶点记为Ui1,置S1二Si一.{Ui1}。
3.若i=v-1,贝M亭止。
若i:
:
:
v-1,则用i1代替i,并转入第二步。
当算法结束时,从uo到v的距离由标号Iv的终值给出。
算法总结:
虽然最短路的一些问题可以用该算法予以解决,但是在图论中还有许
多较为复杂的问题不可以用该算法予以解决。
5.二分图的应用
通过对二分图定义、判断、算法的介绍,对二分图有了一定的了解,下面介绍二分图在实际生活中的应用。
在我市就业市场双选会上,有n个毕业本科生从m个工作岗位上选择自己的职业。
已经知道每个毕业生至少愿意去r(1空r空m)个单位工作,并且每个单位至多看中了其中r-1个毕业生,可以从其中选择一个。
问最多可以有几个单位可以选择到自己满意的毕业生?
试试写出判断过程。
情景分析:
可以看出这是一个关于二分图运用在招聘用人方面上的实际应用问题。
n名本科毕业生作为一个子集,用人单位m作为另一个子集,运用二分图匹配中著名的“t条件”定理可以解决此问题。
定理:
设二分图G=;Vi,V2,E:
中,Vi中每个顶点至少关联t(t_1)条边,而V中
每个顶点至多关联t条边,则G中存在Vi到V2的完全匹配,在性质中已经提到。
解:
我们首先设V为毕业生的集合,U为用人单位的集合,集合E表示毕业生愿意到单位工作,那么我们就可以把G=;V,U,E]就是为一个二分图。
根据我们刚才分析可以知道,对于任何一个毕业生都至少愿意去r个单位我们就表示为dv-r,并且每个用人单位都至多看中其中的r-1个毕业生,所以我们表示成du乞r-1乞r。
我们可以发现该条件正好满足t条件定理,所以存在V到U的的完美匹配,该完美分配M|=n。
得到最多有n个单位找到自己满意的毕业生,所有学生都可以找到自己愿意去的单位。
总结:
该类计算的要点,是通过题意找到题目中两个集合的度,并且计算是否满
足t条件定理,找个一个合理的分配方案即可。
某杂志社发表了7个征求答案的题目,当从读者寄来的解答中挑选出每道题的两个答案准备发表时,编辑发现所有14个挑选出来的解答恰好是7个读者提出的,而且他们每人正好提供了不同题目的两个答案。
请说明:
编辑可以这样发表每道题的一个答案,使得发表的解答中,这7个读者中每人都有一个解答。
情景分析:
该问题就是t条件定理的一个典型应用问题。
解:
设V,={uu为读者},V2={vv为题目},E={(u,v|u提供了v的答案},则
G=MN2,E为一个二分图。
满足t条件且t=2,故有完美匹配,从而编辑可以这样发表每道题的答案,使得在发表的解答中这7个读者中每人都有一个解答。
情景三:
有四名老师张、王、李、赵,学校准备分别派他们教四门课程,但是这四名老师提交的简历中,让教务处主任头疼了。
张老师可以教外语和数学,王老师可以教语文和政治,李老师可以教语文、数学和外语,赵老师只会教外语。
教务处主任应该如何去分配,才能使每个老师都有课程可教,也不会让任何老师去教自己不会的课程?
情景分析:
这是一个关于解决人员任务的派遣和官职任务的实际问题。
可以利用二分图的完全匹配来解决该类问题,把教师看成为一个集合分别用ab、c、d表示张、王、李、赵;把所教课程看作另外一个集合分别用C、m、ep表示语文、数学、英语、政治。
定理:
若Gh;M,V2,E:
是二部图,并且对于任意vV,或V2有dv=k0,则G有一个完全匹配。
解:
令U={a、b、c、d},V二{C、m、ep},并且xUyVx可以得
到l-x,y\E。
于是我们现在的问题就变成了寻找G中的一个完全匹配M。
作图如下:
P
赵老师只会教英语,那么我们表示成Ld,e1;由于英语已经让张老师教了,所以
张老师只能去教数学,表示成la,m1;因为语文剩下的王老师和李老师都会教,
但是政治只有的王老师会教,所以分配王老师教政治,李老师教语文表示为lb,p1和lc,C]。
那么就得到了一个完全匹配M={〔d,el,La,m1,〔b,pl,Lc,C1}即可作为教师任课的分配方案。
情景四:
在新中国刚成立的时候,敌我双方都展开了间谍大战,我方一举抓获了台湾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都不邻接,得到U={a、f、e},V二{b、c、d}分别监禁在不同的房间里,可以使得在同一房间里的间谍不能互相交流
作图如下
问题延伸:
我们已经利用二分图的概念解决了该问题,同样还可以利用“着”色
法来解决此问题。
为了不失一般性,假设a赋以红色,同时b、c、d都赋以蓝色;再将与b相邻接的点a、f、e赋以红色,与c相邻接的a、e赋以红色。
检查上述过程,我们发现a、f、e被赋以
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二分 毕业论文