2连通[4,2]图中的圈以及含有Hamilton圈的一个充分条件的再证明毕业论文.doc

《2连通[4,2]图中的圈以及含有Hamilton圈的一个充分条件的再证明毕业论文.doc》由会员分享，可在线阅读，更多相关《2连通[4,2]图中的圈以及含有Hamilton圈的一个充分条件的再证明毕业论文.doc（11页珍藏版）》请在优知文库上搜索。

1、毕 业 论 文题 目：2-连通4, 2-图中的圈以及含有Hamilton圈的一个充分条件的再证明学 院：专 业：毕业年限：学生姓名：学 号：指导教师：2-连通4,2-图中的圈以及含有Hamilton圈的一个充分条件的再证明摘要：图论(Graph Theory)的研究开始于200多年前, 关于图论的第一篇论文是1736年Euler发表的, 他用图论的方法解决了格尼斯堡(Konigsberg)七桥问题. 图的Hamilton问题是图论中一个十分重要且又十分活跃的研究课题, 1857年, 爱尔兰数学家哈密顿提出:一个连通图有哈密顿圈的充要条件是什么?这样一个问题. 但是这个问题至今仍未能解决, 以H

2、amilton问题为出发点发展起了对图的圈性质的研究, 这些性质主要包括Hamilton性、泛圈性、完全圈可扩性等. 本文的主要内容包括三个部分: 在第一部分中主要介绍了文章中所涉及的一些概念、术语符号和本文的研究背景及已有的结果；在第二部分中讨论2-连通4,2-图中的圈；在第三部分中讨论了图中含有Hamilton圈的一个充分条件.关键词：s, t-图；连通度；s-点连通图；完全圈可扩性；最长圈；Hamilton圈；独立数中图分类号: O 157. 5The Cycles in 2-connected4,2-graphs and another proof of a sufficient co

3、ndition for the graph containing Hamilton cyclesAbstract: Graph Theory began 200 years ago, Euler published the first paper on graph theory in 1736, he used graph theory to solve the Konigsberg Seven Bridges. the Hamilton problem is a very important and active research topic in graph theory, In 1857

4、, Irish mathematician Hamilton put forward a problem: “what is the necessary and sufficient condition when a connected graph has a Hamilton cycle.” However, it has not been solved until now, At the same time based on Hamilton problem, a research on natures of cycles in graph has been carried out. Th

5、ese natures are hamiltonicity, pancyclicity, extensibility etc. The main content of this paper consists of three parts: in the first part introduces some of the concepts terms symbols covered in the article, and the research background and the existing results; in the second part we discussed the cy

6、cles in 2-connected4, 2-graphs; in the third part we discussed a sufficient condition for the graph contains Hamilton cycle.Key words: s,t-graph; connectivity; s-vertices connected graph; fully cycle extensibility; the longest cycle; Hamilton cycle; independence number1 预备知识1-21.1 符号概念介绍本文考虑的图是有限、无向

7、、简单图, 文中所使用的记号和术语约定如下:设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的度, d G(v)也简记为d(v). 用, 分别表示图G中顶点的最小度和最大度, 即: = mind(v):vV(G), =maxd(v):v

8、 V(G);定义图G的连通度K(G)为使图G不连通所要删去的顶点的最小数目, 对任意的kK(G), 称G为k-连通的;对V(G)的子集S、T, 令E(S, T)= st E(G):s S, t T; 设C= V1 V2 Vr V1, 是G的一个圈, Vi , V j V(C), 用Vi-1和Vi+1分别表示C上的点Vi-1和Vi+1, Vi-1和Vi+1也分别简记成Vi-和Vi+;用ViCVj和ViC(_)Vj (1Ij r)分别表示C上的路ViVi+1Vj和Vi Vi-1Vj. ;|C|=|V(C)|称为圈C的长度, 若C的长度为r, 则称C为G的一个r-圈;G中经过G的每个顶点恰一次的路叫

9、做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|S|的独立集S, G的最大独立集的顶点数称为G的独立数, 记为(G). 2 2-连通4,2-图中的圈3 2.1 关于s,t-图有下述性质与结果:性质2.1.

10、1 s, t-图必是s, t-1-图. 性质2.1.2 s, t-图必是s+1, t-图. 性质2.1.3 s, 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)|的任一圈, 则或

11、者G中有(|C|+1)-圈, 或者G同构于K2, 3, K1, 1, 3, F1, F2, F3, F4, F5. 其中F1, F2, F3, F4, F5如下图: 图F1 图F2 图F3 图F4 图F5 2.3 定理2.2.1的证明4证明 设图G满足定理条件, C是G的一个圈, 且|V(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: x

12、v1-, x v2-, x v2+, 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(_) v1x v2v2-v2+C v1-, 矛盾！由G是 4, 2-图:必有v2-2, v2+E(G). 如

13、此考虑下去可得: 任意vV(v1+C v2-), 有v v2+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), 考虑G x1, x2, v-, v+, 由论断1:x1v-, x1v+, x2v-, x2v+E(G), 这与G是4, 2-图矛盾！论断4 对G的任一分支H, |H|2, 则H与C间必有两条独立边.证明 此结论显然.以下分3种情形完成定理的证明:情形 1 |C|4取G-C的一个分支H, 由论断2知任取x V(H), 有NC(x)=1, 又因为G是2-连通的, 所以|NC(H)| 2, 所以H与C间必有两条独立