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

14、|C|4取G-C的一个分支H, 由论断2知任取x V(H), 有NC(x)=1, 又因为G是2-连通的, 所以|NC(H)| 2, 所以H与C间必有两条独立边. 设: x1v1, x2v2 E(V(H), V(C), 其中x1, x2V(H)( x1x2), v1, v2 V(C)(v1v2), 若v1v2 E(C), 由于|C|4, 所以|v1+C v1-|, |v2+C v1-|必有一个2. 不妨设: |v2+C v1-|2考虑Gx1, x2, v1+, v2+2, 由论断2知x1v1+, x1v2+2, x2v1+, x2v2+2E(G), 则由G是4, 2-图知必有x1x2, v1+v

15、2+2 E(G),则G中有(|C|+1)-圈C=v1+v2+2C v1x1 x2v2C(_) v 1-, 矛盾！所以v1v2 E(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

16、)C(_) v2 x2x1, 矛盾！若|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-3 C(_)v2 x2x1, 矛盾！若|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=x1v1 v1-v2+2v2+v2 x2x1, 矛

17、盾！情形 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, x2 V(H), 且x1x2, 则x1x2E(G)(否则G有4-圈),对任意的xV(H), 有xv3 E(G)

18、, 若xx1, x2, 则结论显然, 设xx1, x2, 若xv3 E(G), 考虑Gx, x1, x2, v3, 由论断1知x1v3, x2v3 E(G), 由 , 有x1x2E(G), 又x1x E(G)(否则G有4-圈), 同理x2x E(G), 对任意的xV(H), 有xx1, xx2E(G), 考虑Gx, x1, x2, v3, 由论断1知x1v3, x2v3 E(G), 又由有x1x2, xv3 E(G), 由G是4, 2-图知必有xx1, xx2E(G); 若|H|4, 取x3, x4 V(H)x1, x2, 由知x3, x4均与x1, x2相邻, 则G有4-圈, 此为矛盾！由此

19、说明|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, x2v2 E(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

20、(C)子情形 3.1 |H|3取x V(H)x1, x2, 显然x不能与x1, x2同时相邻, 否则G有4-圈, 不妨设xx2 E(G), 令Cv1, v2=v3, v4, 即C= v1v2v3v4 v1, 所以有xv3E(G), xv4 E(G); 若xv3E(G), 考虑Gx, x1, v2, v4, 由论断1知x1v2, x1v4, xv2, xv4 E(G), xx1 E(G), 这与G是4, 2-图矛盾！若xv4E(G), 考虑Gx, x2, v1, v3, 由论断1知x2v1, x2v3, xv1, xv3E(G), 由G是4, 2-图知xx2, v1v3 E(G), 则G有5-圈

21、C=xx2v2v3v4x, 此为矛盾！考虑Gx, x1, v3, v4, 由假设及论断1得xx1, x1v4 E(G), 又因为及G是4, 2-图, 则x1v3E(G), 若v2v4E(G)则G有5-圈C=v1x1v3 v2v4v1, 此为矛盾！所以v2v4 E(G), 考虑Gx, x1, v2, v4由假设及论断1得xx1, x1v4, x1v2 E(G), 又因为v2v4 E(G), 及, 得到xv4E(G), 显然这与G是4, 2-图矛盾！注 子情形3. 1说明只需再考虑“G-C的每个分支至多两个点”的情形. 子情形3.2 |H|=2若|H|=2, 则x1, x2 E(H)(a) 若H是

22、G-C的唯一分支, 由论断1知x1v2, x1v4, x2v1, x2v3 E(G)若v2v4E(G), 则G有5-圈C= x1v1v4v2x2x1, 此为矛盾！若v1v3E(G), 则G有5-圈C= x1v1v3v2x2x1, 此为矛盾！若x1v3E(G), x2v4E(G)则G同构于F2,若x1v3E(G), x2v4 E(G)之一成立, 则G同构于F3,若x1v3E(G), x2v4 E(G)都成立, 则G同构于F4,(b)若G-C有两个分支, 不妨设H1为G-C的另一分支若|H1|=2, 设V(H1)=y1, y2, 由|NC(H1)|2及论断3得y1v3, y2v4E(G), 考虑:

23、Gx1, y1, v2, v4, 由论断1知x1v4, x1v2, y1v4, y1v2 E(G), 又因为x1y1E(G), 这与G是4, 2-图矛盾！所以|H1|=1. 设: V(H1)=y, 由|NC(H1)|2及论断3得yv3, yv4E(G), 则G有5-圈, 此为矛盾！注 上述两种子情形说明只需再考虑“G-C的每个分支至多一个点”的情形. 子情形3.3 |H| = 1设V(H)=x, 由|NC(H)|2及论断1得: xv1, xv3 E(G)且v2v4E(G), 否则G有5-圈. (a)若H是G-C的唯一分支, 则当v1v3 E(G)时, G同构于K2, 3 ,当v1 v3 E(G

24、)时, G同构于K1, 1, 3; (b)若G-C有两个分支, 不妨设H1为G-C的另一分支, 设V(H1)=y, 由|NC(H1)|2及论断3得yv2, yv4 E(G), 则 v1v3E(G) (否则G有5-圈), 此时G同构于F5 .至此定理2. 2. 1证明全部结束. 3 图G中含有Hamilton圈的一个充分条件引理3.15 若K(G)(G), 则G含有一个Hamilton圈或G=K2 . 引理3.25 设G是一个含有n个点的3-连通图, 若4 n+2K(G), 则G的每一个最长圈都是控制圈. 定理3.1 设G是含有n个点的3-连通图, 若4n+K(G)+(G)1, 则图G是一个Ha

25、milton图. 证明 用反证法证明, 假设G不是Hamilton图, 根据引理3.2, 图G的每个最长圈都是控制圈, 由于图G不是Hamilton图, 根据引理3. 2, 有(G) K(G)+1, 首先证明若T=K(G), 这就表示点v的度为K(G), 则d(y)+d(z)+d(v)+d(x)|C|+n|C|1+K(G)+(G)1= n+K(G)+(G)2, 其中y, z是T中的两个不同点, x是A0中不同于y, z的一个顶点, 这与题目中的条件4n+K(G)+(G)1矛盾！因此|T|K(G)且(G)K(G)2.设V0是G的一个点割集且|V0| = K(G), V1, V2, , Vp是G-

26、V0的全部连通分支设Yi=ViU(0Ip), 并且对于每个Yi有顺序:|Y1|Y2|Yp|, 因为|V0|=K(G)3, 可以找到两个点t2, t3使得t2, t3 Y1t1, 由此得到以下不等式:d(t2)+d(t3)n1|V2|; 另一方面, 对于V2中的每个点u, d(u)满足不等式d(u)|V2|1+K(G), 因此得出:d(t1)+d(t2)+d(t3)+d(u) (G)1+n1|V2|+|V2|1+ K(G)=n+(G)+K(G)3,然而这与条件4 n+K(G)+(G)1矛盾！子情形2.2 |Y1|=2, 不妨设Y1=y1, y2,此时有V0=(v(UY1)且U=T ,对于任何一个

27、顶点x V2和某个1it有不等式:|N(y1)(V(Ci)x)|+| N(y2)(V(Ci)x)|V(Ci)|1, 因此, 可以推断出:d(y1) +d(y2)n1|V2|n2, 任取y3A0y1, y2, 由于y3的度小于(G), 得到矛盾: d(v)+d(y1)+d(y2)+d(y3)K(G)+1+n2+(G)1 = n+(G)+K(G)24, 综上所述, 定理3.1成立. 4 总结图论中有很多著名的问题引发人们的兴趣, 如哈密尔顿问题, 邮寄员问题, 四色问题等等. 图论作为数学的一个分支, 它与数学的其他分支有密切的关系, 事实上图论为任何一个包含二元关系的系统提供了一个数学模型, 利

28、用图直观、漂亮的表现特性可以使人对现实的系统有清晰的了解, 应用图论来解决物理学、化学、生物学、信息与计算机科学以及社会科学等问题已显示出极大的优越性, 本文参考前人的研究, 讨论了2-连通4, 2-图中的圈以及图中含有Hamilton圈的一个充分条件, 得到了一些结果, 但是对于这些问题的研究还远远不够全面, 有待于更进一步的研究, 在此对本文引用文献的作者表示感谢. 参考文献1 王朝瑞. 图论M. 北京: 国防工业出版社, 1985. 2 丹 J. 邦詹森 英G . 古廷 著(姚兵 张忠辅 译). 有向图的理论、算法及应用M. 北京: 科学出版社, 2009. 3 刘春房. 若干图类的哈密尔顿性J. 山东师范大学, 2005. 4 刘晓妍. 2-连通4, 2-图中的圈与高连通度图的完全圈可扩性J. 山东师范大学, 2005. 5 张力. 图论中若干问题探究J. 华中师范大学, 2011. 11