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

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

   首页 人人文库网 > 资源分类 > DOC文档下载

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

  • 资源星级:
  • 资源大小:203.00KB   全文页数:11页
  • 资源格式: DOC        下载权限:注册会员/VIP会员
您还没有登陆,请先登录。登陆后即可下载此文档。
  合作网站登录: 微信快捷登录 支付宝快捷登录   QQ登录   微博登录
友情提示
2:本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3:本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

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

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,

注意事项

本文(数学与应用数学毕业论文-2-连通[4_2]-图中的圈以及含有Hamilton圈的一个充分条件的再证明.doc)为本站会员(liyun)主动上传,人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知人人文库网([email protected]),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。

copyright@ 2015-2017 人人文库网网站版权所有
苏ICP备12009002号-5