会员注册 | 登录 | 微信快捷登录 支付宝快捷登录 QQ登录 微博登录 | 帮助中心 人人文库renrendoc.com美如初恋!
站内搜索 百度文库

热门搜索: 直缝焊接机 矿井提升机 循环球式转向器图纸 机器人手爪发展史 管道机器人dwg 动平衡试验台设计

数学与应用数学毕业论文-2-连通[4_2]-图中的圈以及含有Hamilton圈的一个充分条件的再证明.doc数学与应用数学毕业论文-2-连通[4_2]-图中的圈以及含有Hamilton圈的一个充分条件的再证明.doc -- 8 元

宽屏显示 收藏 分享

资源预览需要最新版本的Flash Player支持。
您尚未安装或版本过低,建议您

1毕业论文题目2连通4,2图中的圈以及含有Hamilton圈的一个充分条件的再证明学院数学与信息科学学院专业数学与应用数学毕业年限2012届学生姓名学号指导教师22连通4,2图中的圈以及含有Hamilton圈的一个充分条件的再证明摘要图论GraphTheory的研究开始于200多年前,关于图论的第一篇论文是1736年Euler发表的,他用图论的方法解决了格尼斯堡Konigsberg七桥问题.图的Hamilton问题是图论中一个十分重要且又十分活跃的研究课题,1857年,爱尔兰数学家哈密顿提出一个连通图有哈密顿圈的充要条件是什么这样一个问题.但是这个问题至今仍未能解决,以Hamilton问题为出发点发展起了对图的圈性质的研究,这些性质主要包括Hamilton性、泛圈性、完全圈可扩性等.本文的主要内容包括三个部分在第一部分中主要介绍了文章中所涉及的一些概念、术语符号和本文的研究背景及已有的结果在第二部分中讨论2连通4,2图中的圈在第三部分中讨论了图中含有Hamilton圈的一个充分条件.关键词s,t图连通度s点连通图完全圈可扩性最长圈Hamilton圈独立数中图分类号O157.5TheCyclesin2connected4,2graphsandanotherproofofasufficientconditionforthegraphcontainingHamiltoncyclesAbstractGraphTheorybegan200yearsago,Eulerpublishedthefirstpaperongraphtheoryin1736,heusedgraphtheorytosolvetheKonigsbergSevenBridges.theHamiltonproblemisaveryimportantandactiveresearchtopicingraphtheory,In1857,IrishmathematicianHamiltonputforwardaproblemwhatisthenecessaryandsufficientconditionwhenaconnectedgraphhasaHamiltoncycle.However,ithasnotbeensolveduntilnow,AtthesametimebasedonHamiltonproblem,aresearchonnaturesofcyclesingraphhasbeencarriedout.Thesenaturesarehamiltonicity,pancyclicity,extensibilityetc.Themaincontentofthispaperconsistsofthreepartsinthefirstpartintroducessomeoftheconceptstermssymbolscoveredinthearticle,andtheresearchbackgroundandtheexistingresultsinthesecondpartwediscussedthecyclesin2connected4,2graphsinthethirdpartwediscussedasufficientconditionforthegraphcontainsHamiltoncycle.Keywordss,tgraphconnectivitysverticesconnectedgraphfullycycleextensibilitythelongestcycleHamiltoncycleindependencenumber31预备知识121.1符号概念介绍本文考虑的图是有限、无向、简单图,文中所使用的记号和术语约定如下设GVG,EG是一个图,VG、EG分别表示G的顶点集和边集.|G||VG|表示G中顶点的数目,称为G的阶,|EG|表示G中边的数目对顶点集{V1,V2,Vm}VG,用GV1,V2,Vm表示G中由{V1,V2,Vm}导出的子图对v∈VG及G的子图H,记NHv{u∈VHuv∈EG},NGv简记为NvdHv|NHv|称图G中点v的度,dGv也简记为dv.用δ,△分别表示图G中顶点的最小度和最大度,即δmin{dvv∈VG},△max{dvv∈VG}定义图G的连通度KG为使图G不连通所要删去的顶点的最小数目,对任意的k|S|的独立集S,G的最大独立集的顶点数称为G的独立数,记为αG.22连通4,2图中的圈32.1关于s,t图有下述性质与结果性质2.1.1s,t图必是s,t1图.性质2.1.2s,t图必是s1,t图.性质2.1.3s,t图必是s1,t1图.定理2.1.1设G是4,2图,则aG是连通的当且仅当G同构于K1,3或者G有Hamilton路.bG是2连通的当且仅当G同构于K2,3或者G同构于K1,1,3或者G有Hamilton圈.2.2主要结果下边的定理2.2.1是本文要证明的主要结果,显然定理2.2.1要比定理2.1.1中b的结果更好.定理2.2.1设G是2连通4,2图,C是G中满足|VC|4则任取x∈VH,有|NCx|1.证明若|NCx|≥2,取v1,v2∈NCxv1≠v2,由论断1v1v2EC.因为|C|4,所以|v1Cv2|,|v2Cv1|必有一个≥2.不妨设|v2Cv1|≥2,考虑Gx,v2,v2,v1,由论断1xv1,xv2,xv2,v1v2EC由G是4,2图,必有v2v2∈EG.若v22v1,则G中有|C|1圈C´v1xv2v2v2Cv1,矛盾所以v22≠v1.考虑Gx,v22,v2,v1,由论断1xv1,xv2EG,又xv22EG,否则G中有|C|1圈C´v22xv2v2v2Cv22,矛盾又v1v22EG,否则G中有|C|1圈C´v1v22C__v1xv2v2v2Cv1,矛盾由G是4,2图必有v22,v2∈EG.如此考虑下去可得任意v∈Vv1Cv2,有vv2∈EG,特别地v1,v2∈EG,这与论断1矛盾论断3设H1,H2是GC的两个分支,则NCH1∩NCH2.证明若NCH1∩NCH2≠,取v∈NCH1∩NCH2,则有x1v,x1v∈EG,其中x1∈VH1,x2∈VH2,考虑Gx1,x2,v,v,由论断1x1v,x1v,x2v,x2vEG,这与G是4,2图矛盾论断4对G的任一分支H,|H|≥2,则H与C间必有两条独立边.6证明此结论显然.以下分3种情形完成定理的证明情形1|C|4取GC的一个分支H,由论断2知任取x∈VH,有NCx1,又因为G是2连通的,所以|NCH|≥2,所以H与C间必有两条独立边.设x1v1,x2v2∈EVH,VC,其中x1,x2∈VHx1≠x2,v1,v2∈VCv1≠v2,若v1v2EC,由于|C|4,所以|v1Cv1|,|v2Cv1|必有一个≥2.不妨设|v2Cv1|≥2考虑Gx1,x2,v1,v22,由论断2知x1v1,x1v22,x2v1,x2v22EG,则由G是4,2图知必有x1x2,v1v22∈EG,则G中有|C|1圈C´v1v22Cv1x1x2v2C__v1,矛盾所以v1v2∈EC.考虑Gx1,x2,v1,v2,由论断2知x1v1,x1v2,x2v1,x2v2EG,则由G是4,2图知必有x1x2,v1v2∈EG考虑Gx1,x2,v12,v22,由上述讨论可得v12v22∈EG.如此下去可得v1iv2i∈EG,i1,2,,|C|/21.若|C|为奇数,则G中有|C|1圈C´x1v1C__v1|C|/21v2|C|/21C__v2x2x1,矛盾若|C|为偶数且|C|≥8,考虑Gx1,x2,v1,v13,由论断2知x1v1,x1v13,x2v1,x2v13EG则由G是4,2图知必有x1x2,v1v13∈EG,则G有|C|1圈C´x1v1v1v13C__v2x2x1,矛盾若|C|6,考虑Gx1,x2,v1,v22,由论断2知x1v1,x1v22,x2v1,x2v22EG,则由G是4,2图知必有x1x2,v1v22∈EG,则G有7圈C´x1v1v1v22v2v2x2x1,矛盾情形2|C|3设Cv1v2v3v1,GC的分支数≥2,取GC的任意两个分支H1,H2,因为G是2连通的,所以|NCHi|≥2,i1,2.又注意到|C|3,可知NCH1∩NCH2≠,这与推论3矛盾因此GC只能有一个分支,设此分支为H,|H|1或2.则易见G有4圈,此为矛盾所以|H|≥3由|C|3及|NCH|≥2知H与C间必有两条独立边取两条这样的独立边,不妨设为x1v1,x2v2∈EVH,VC,其中x1,x2∈VH,且x1≠x2,则x1x2EG①否则G有4圈,对任意的x∈VH,有xv3EG②,若x∈{x1,x2},则结论显然,设x∈{x1,x2},若xv3∈EG,考虑Gx,x1,x2,v3,由论断1知x1v3,x2v3EG,由①,有x1x2EG,又x1xEG否则G有4圈,7同理x2xEG,对任意的x∈VH,有xx1,xx2∈EG③,考虑Gx,x1,x2,v3,由论断1知x1v3,x2v3EG,又由①②有x1x2,xv3EG,由G是4,2图知必有xx1,xx2∈EG若|H|≥4,取x3,x4∈VH-{x1,x2},由③知x3,x4均与x1,x2相邻,则G有4圈,此为矛盾由此说明|H|3,即G同构于F1.情形3|C|4注意到对G的任一分支H,均有|NCH|≥2且|C|4,结合论断3可知GC至多有2个分支,取GC的一个分支H,若|H|≥2,由论断4知H与C间必有2条独立边,取两条这样的独立边,设x1v1,x2v2∈EVH,VC,其中x1,x2∈VHx1≠x2,v1,v2∈VCv1≠v2,若v1v2EC,考虑Gx1,x2,v1,v2,由论断1知x1v1,x1v2,x2v1,x2v2EG,又x1x2EG否则G有5圈,这与G是4,2图矛盾所以v1v2∈EC子情形3.1|H|≥3取x∈VH-{x1,x2},显然x不能与x1,x2同时相邻,否则G有4圈,不妨设xx2EG,令C-{v1,v2}{v3,v4},即Cv1v2v3v4v1,所以有xv3EG,xv4EG④若xv3∈EG,考虑Gx,x1,v2,v4,由论断1知x1v2,x1v4,xv2,xv4EG,xx1EG,这与G是4,2图矛盾若xv4∈EG,考虑Gx,x2,v1,v3,由论断1知x2v1,x2v3,xv1,xv3EG,由G是4,2图知xx2,v1v3∈EG,则G有5圈C´xx2v2v3v4x,此为矛盾考虑Gx,x1,v3,v4,由假设及论断1得xx1,x1v4EG,又因为④及G是4,2图,则x1v3∈EG,若v2v4∈EG则G有5圈C´v1x1v3v2v4v1,此为矛盾所以v2v4EG,考虑Gx,x1,v2,v4由假设及论断1得xx1,x1v4,x1v2EG,又因为v2v4EG,及④,得到xv4EG,显然这与G是4,2图矛盾注子情形3.1说明只需再考虑GC的每个分支至多两个点的情形.子情形3.2|H|2若|H|2,则x1,x2∈EHa若H是GC的唯一分支,由论断1知x1v2,x1v4,x2v1,x2v3EG若v2v4∈EG,则G有5圈C´x1v1v4v2x2x1,此为矛盾若v1v3∈EG,则G有5圈C´x1v1v3v2x2x1,此为矛盾若x1v3EG,x2v4EG则G同构于F2,
编号:201311221001441783    大小:203.00KB    格式:DOC    上传时间:2013-11-22
  【编辑】
8
关 键 词:
教育专区 毕业设计 精品文档 数学与应
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
  人人文库网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

当前资源信息

4.0
 
(2人评价)
浏览:19次
liyun上传于2013-11-22

官方联系方式

客服手机:13961746681   
2:不支持迅雷下载,请使用浏览器下载   
3:不支持QQ浏览器下载,请用其他浏览器   
4:下载后的文档和图纸-无水印   
5:文档经过压缩,下载后原文更清晰   

相关资源

相关资源

相关搜索

教育专区   毕业设计   精品文档   数学与应  
关于我们 - 网站声明 - 网站地图 - 友情链接 - 网站客服客服 - 联系我们
copyright@ 2015-2017 人人文库网网站版权所有
苏ICP备12009002号-5