数学与应用数学毕业论文-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.5TheCyclesin2-connected4,2-graphsandanotherproofofasufficientconditionforthegraphcontainingHamiltoncyclesAbstract:GraphTheorybegan200yearsago,Eulerpublishedthefirstpaperongraphtheoryin1736,heusedgraphtheorytosolvetheKonigsbergSevenBridges.theHamiltonproblemisaveryimportantandactiveresearchtopicingraphtheory,In1857,IrishmathematicianHamiltonputforwardaproblem:“whatisthenecessaryandsufficientconditionwhenaconnectedgraphhasaHamiltoncycle.”However,ithasnotbeensolveduntilnow,AtthesametimebasedonHamiltonproblem,aresearchonnaturesofcyclesingraphhasbeencarriedout.Thesenaturesarehamiltonicity,pancyclicity,extensibilityetc.Themaincontentofthispaperconsistsofthreeparts:inthefirstpartintroducessomeoftheconceptstermssymbolscoveredinthearticle,andtheresearchbackgroundandtheexistingresults；inthesecondpartwediscussedthecyclesin2-connected4,2-graphs；inthethirdpartwediscussedasufficientconditionforthegraphcontainsHamiltoncycle.Keywords:s,t-graph；connectivity；s-verticesconnectedgraph；fullycycleextensibility；thelongestcycle；Hamiltoncycle；independencenumber31预备知识1-21.1符号概念介绍本文考虑的图是有限、无向、简单图,文中所使用的记号和术语约定如下:设G=(V(G),E(G)是一个图,V(G)、E(G)分别表示G的顶点集和边集.|G|=|V(G)|表示G中顶点的数目,称为G的阶,|E(G)|表示G中边的数目；对顶点集V1,V2,VmV(G),用GV1,V2,Vm表示G中由V1,V2,Vm导出的子图；对vV(G)及G的子图H,记NH(v)=uV(H):uvE(G),NG(v)简记为N(v)；dH(v)=|NH(v)|称图G中点v的度,dG(v)也简记为d(v).用,分别表示图G中顶点的最小度和最大度,即:=mind(v):vV(G),=maxd(v):vV(G)；定义图G的连通度K(G)为使图G不连通所要删去的顶点的最小数目,对任意的k<K(G),称G为k-连通的；对V(G)的子集S、T,令E(S,T)=stE(G):sS,tT；设C=V1V2VrV1,是G的一个圈,Vi,VjV(C),用Vi-1和Vi+1分别表示C上的点Vi-1和Vi+1,Vi-1和Vi+1也分别简记成Vi-和Vi+；用ViCVj和ViC_Vj(1I<jr)分别表示C上的路ViVi+1Vj和ViVi-1Vj.；|C|=|V(C)|称为圈C的长度,若C的长度为r,则称C为G的一个r-圈；G中经过G的每个顶点恰一次的路叫做G的的Hamilton路,同样地G中经过G的每个顶点恰一次的圈叫做G的Hamilton圈；如果一个图G中存在一个Hamilton圈,则称G为Hamilton的；如果图G的任意两个顶点之间都有一条Hamilton路,则称G为Hamilton连通的；对一个有n个顶点的图G,如果对任意的k(3kn),G都有长度为k的圈,则称G为泛圈图；如果图G满足:(1)G的每一个顶点都在一个3-圈上；(2)对G中任意一个圈C,只要|C|<|G|,就存在G的圈C´,使V(C)V(C´)且|C´|=|C|+1,则称G是完全圈可扩的,同时称C´为C的扩圈；如果图G中任意s个点的导出子图至少含有t条边,则称图G为s,t-图.4如果图G中任意s(s3)个点的导出子图是连通的,且存在s-1个点的导出子图是不连通的,则称图G为s-点连通图；设S是V(G)的一个子集,若S中任意两个顶点在G中均不相连则称S是G的一个独立集；G的一个独立集S称为G的最大独立集,如果G不包含满足|S|>|S|的独立集S,G的最大独立集的顶点数称为G的独立数,记为(G).22-连通4,2-图中的圈32.1关于s,t-图有下述性质与结果:性质2.1.1s,t-图必是s,t-1-图.性质2.1.2s,t-图必是s+1,t-图.性质2.1.3s,t-图必是s+1,t+1-图.定理2.1.1设G是4,2-图,则:(a)G是连通的当且仅当G同构于K1,3或者G有Hamilton路.(b)G是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中满足|V(C)|<|V(G)|的任一圈,则或者G中有(|C|+1)-圈,或者G同构于K2,3,K1,1,3,F1,F2,F3,F4,F5.其中F1,F2,F3,F4,F5如下图:图F1图F2图F35图F4图F52.3定理2.2.1的证明4证明设图G满足定理条件,C是G的一个圈,且|V(C)|<|V(G)|,以下总假定G中不含(|C|+1)-圈,取G-C的一个分支H,因为G是2-连通的,所以|NC(H)|2.论断1设u,vV(C),xV(H),若xuE(G),xvE(G)则:xu-,xu+E(G),xv-,xv+E(G),u-v-,u+v+E(G).证明若xv-E(G),则G有(|C|+1)-圈C´=vCv-xv,矛盾！所以xv-E(G),同理可证xv+E(G),u-v-,u+v+E(G).若u+v+E(G),则G有(|C|+1)-圈C´=uxvC_u+v+Cu,矛盾！同理可证u-v-E(G).论断2设G是2-连通4,2-图,若|C|>4则任取xV(H),有|NC(x)|=1.证明若|NC(x)|2,取v1,v2NC(x)(v1v2),由论断1:v1v2E(C).因为|C|>4,所以|v1+Cv2-|,|v2+Cv1-|必有一个2.不妨设:|v2+Cv1-|2,考虑Gx,v2-,v2+,v1-,由论断1:xv1-,xv2-,xv2+,v1-v2-E(C)；由G是4,2-图,必有v2-v2+E(G).若v2-2=v1,则G中有(|C|+1)-圈C´=v1xv2v2-v2+Cv1,矛盾！所以v2-2v1.考虑Gx,v2-2,v2+,v1-,由论断1:xv1-,xv2+E(G),又xv2-2E(G),否则G中有(|C|+1)-圈C´=v2-2xv2v2-v2+Cv2-2,矛盾！又v1-v2-2E(G),否则G中有(|C|+1)-圈C´=v1-v2-2C_v1xv2v2-v2+Cv1-,矛盾！由G是4,2-图:必有v2-2,v2+E(G).如此考虑下去可得:任意vV(v1+Cv2-),有vv2+E(G),特别地v1+,v2+E(G),这与论断1矛盾！论断3设H1,H2是G-C的两个分支,则NC(H1)NC(H2)=.证明若NC(H1)NC(H2),取vNC(H1)NC(H2),则有x1v,x1vE(G),其中x1V(H1),x2V(H2),考虑Gx1,x2,v-,v+,由论断1:x1v-,x1v+,x2v-,x2v+E(G),这与G是4,2-图矛盾！论断4对G的任一分支H,|H|2,则H与C间必有两条独立边.6证明此结论显然.以下分3种情形完成定理的证明:情形1|C|>4取G-C的一个分支H,由论断2知任取xV(H),有NC(x)=1,又因为G是2-连通的,所以|NC(H)|2,所以H与C间必有两条独立边.设:x1v1,x2v2E(V(H),V(C),其中x1,x2V(H)(x1x2),v1,v2V(C)(v1v2),若v1v2E(C),由于|C|>4,所以|v1+Cv1-|,|v2+Cv1-|必有一个2.不妨设:|v2+Cv1-|2考虑Gx1,x2,v1+,v2+2,由论断2知x1v1+,x1v2+2,x2v1+,x2v2+2E(G),则由G是4,2-图知必有x1x2,v1+v2+2E(G),则G中有(|C|+1)-圈C´=v1+v2+2Cv1x1x2v2C_v1-,矛盾！所以v1v2E(C).考虑Gx1,x2,v1-,v2+,由论断2知x1v1-,x1v2+,x2v1-,x2v2+E(G),则由G是4,2-图知必有x1x2,v1-v2+E(G)考虑Gx1,x2,v1-2,v2+2,由上述讨论可得v1-2v2+2E(G).如此下去可得:v1-iv2+iE(G),i=1,2,(|C|/2)-1.若|C|为奇数,则G中有(|C|+1)-圈C´=x1v1C_v1-(|C|/2-1)v2+(|C|/2-1)C_v2x2x1,矛盾！若|C|为偶数且|C|8,考虑Gx1,x2,v1-,v1-3,由论断2知:x1v1-,x1v1-3,x2v1-,x2v1-3E(G)则由G是4,2-图知必有x1x2,v1-v1-3E(G),则G有(|C|+1)-圈C´=x1v1v1-v1-3C_v2x2x1,矛盾！若|C|=6,考虑Gx1,x2,v1-,v2+2,由论断2知x1v1-,x1v2+2,x2v1-,x2v2+2E(G),则由G是4,2-图知必有x1x2,v1-v2+2E(G),则G有7-圈C´=x1v1v1-v2+2v2+v2x2x1,矛盾！情形2|C|=3设C=v1v2v3v1,G-C的分支数2,取G-C的任意两个分支H1,H2,因为G是2-连通的,所以|NC(Hi)|2,i=1,2.又注意到|C|=3,可知NCH1NCH2,这与推论3矛盾！因此G-C只能有一个分支,设此分支为H,|H|=1或2.则易见G有4-圈,此为矛盾！所以|H|3；由|C|=3及|NC(H)|2知H与C间必有两条独立边取两条这样的独立边,不妨设为x1v1,x2v2E(V(H),V(C),其中x1,x2V(H),且x1x2,则x1x2E(G)(否则G有4-圈),对任意的xV(H),有xv3E(G),若xx1,x2,则结论显然,设xx1,x2,若xv3E(G),考虑Gx,x1,x2,v3,由论断1知x1v3,x2v3E(G),由,有x1x2E(G),又x1xE(G)(否则G有4-圈),7同理x2xE(G),对任意的xV(H),有xx1,xx2E(G),考虑Gx,x1,x2,v3,由论断1知x1v3,x2v3E(G),又由有x1x2,xv3E(G),由G是4,2-图知必有xx1,xx2E(G)；若|H|4,取x3,x4V(H)x1,x2,由知x3,x4均与x1,x2相邻,则G有4-圈,此为矛盾！由此说明|H|=3,即G同构于F1.情形3|C|=4注意到对G的任一分支H,均有|NC(H)|2且|C|=4,结合论断3可知G-C至多有2个分支,取G-C的一个分支H,若|H|2,由论断4知H与C间必有2条独立边,取两条这样的独立边,设x1v1,x2v2E(V(H),V(C),其中x1,x2V(H)(x1x2),v1,v2V(C)(v1v2),若v1v2E(C),考虑Gx1,x2,v1-,v2-,由论断1知x1v1-,x1v2-,x2v1-,x2v2-E(G),又x1x2E(G)(否则G有5-圈),这与G是4,2-图矛盾！所以v1v2E(C)子情形3.1|H|3取xV(H)x1,x2,显然x不能与x1,x2同时相邻,否则G有4-圈,不妨设xx2E(G),令Cv1,v2=v3,v4,即C=v1v2v3v4v1,所以有xv3E(G),xv4E(G)；若xv3E(G),考虑Gx,x1,v2,v4,由论断1知x1v2,x1v4,xv2,xv4E(G),xx1E(G),这与G是4,2-图矛盾！若xv4E(G),考虑Gx,x2,v1,v3,由论断1知x2v1,x2v3,xv1,xv3E(G),由G是4,2-图知xx2,v1v3E(G),则G有5-圈C´=xx2v2v3v4x,此为矛盾！考虑Gx,x1,v3,v4,由假设及论断1得xx1,x1v4E(G),又因为及G是4,2-图,则x1v3E(G),若v2v4E(G)则G有5-圈C´=v1x1v3v2v4v1,此为矛盾！所以v2v4E(G),考虑Gx,x1,v2,v4由假设及论断1得xx1,x1v4,x1v2E(G),又因为v2v4E(G),及,得到xv4E(G),显然这与G是4,2-图矛盾！注子情形3.1说明只需再考虑“G-C的每个分支至多两个点”的情形.子情形3.2|H|=2若|H|=2,则x1,x2E(H)(a)若H是G-C的唯一分支,由论断1知x1v2,x1v4,x2v1,x2v3E(G)若v2v4E(G),则G有5-圈C´=x1v1v4v2x2x1,此为矛盾！若v1v3E(G),则G有5-圈C´=x1v1v3v2x2x1,此为矛盾！若x1v3E(G),x2v4E(G)则G同构于F2,