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

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

2、问题. 但是这个问题至今仍未能解决, 以hamilton问题为出发点发展起了对图的圈性质的研究, 这些性质主要包括hamilton性、泛圈性、完全圈可扩性等. 本文的主要内容包括三个部分: 在第一部分中主要介绍了文章中所涉及的一些概念、术语符号和本文的研究背景及已有的结果；在第二部分中讨论2-连通4,2-图中的圈；在第三部分中讨论了图中含有hamilton圈的一个充分条件.关键词：s, t-图；连通度；s-点连通图；完全圈可扩性；最长圈；hamilton圈；独立数中图分类号: o 157. 5the cycles in 2-connected4,2-graphs and another pro

3、of of a sufficient condition 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

4、graph theory, in 1857, 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

5、 been carried out. these 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 par

6、t we discussed the cycles 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

7、.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的度, d g(v)也简记为d(v). 用, 分别表示图g中顶点的最小度和最大度, 即: = mind

8、(v):vv(g), =maxd(v):v 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和vivj (1ij r)分别表示c上的路vivi+1vj和vi vi-1vj. ;|c|=|v(c)|称为圈c的长度, 若c的长度为r, 则称c为g的一个r-圈

9、;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|s|的独立集s, g的最大独立集的顶点数称为g的独立数, 记为(g). 2 2-连通4,2-图中的圈3 2.1 关于s,t

10、-图有下述性质与结果:性质2.1.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

11、(c)|v(g)|的任一圈, 则或者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-,

12、v2+, v1-,由论断1: x 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-2 v1x v2v2-v2+c v1-, 矛盾！由g是 4, 2-图:必有v2-

13、2, v2+e(g). 如此考虑下去可得: 任意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种情形

14、完成定理的证明:情形 1 |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-图

15、知必有x1x2, v1+v2+2 e(g),则g中有(|c|+1)-圈c=v1+v2+2c v1x1 x2v2 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= x1v1v1-(|c|/2-1)v2+(|c

16、|/2-1) 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 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(c)

20、子情形 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-圈c=x

21、x2v2v3v4x, 此为矛盾！考虑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是g-c

22、的唯一分支, 由论断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), 考虑:gx1

23、, 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是一个hamil

25、ton图. 证明 用反证法证明, 假设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-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