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

1、 1毕 业 论 文题 目：2-连通4, 2-图中的圈以及含有Hamilton 圈的一个充分条件的再证明学 院：数学与信息科学学院专 业：数学与应用数学毕业年限：2012 届学生姓名： 2学 号：2008指导教师：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-connecte

3、d4,2-graphs and another proof of a sufficient condition for the graph containing Hamilton cycles3Abstract: 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 a

4、nd active research topic in 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 na

5、tures of cycles in graph has 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 existin

6、g results; in the second part 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; i

7、ndependence number1 预备知识 1-21.1 符号概念介绍本文考虑的图是有限、无向、简单图, 文中所使用的记号和术语约定如下:设 G=(V(G), E(G)是一个图, V(G)、E(G)分别表示 G 的顶点集和边集. |G|=|V(G)|表示 G 中顶点的数目 , 称为 G 的阶, |E(G)|表示 G 中边的数目;对顶点集V 1,V2, Vm V(G), 用 GV1,V2, Vm表示 G 中由V 1, V2 , Vm导出的子图;对 vV(G) 及 G 的子图 H, 记 NH(v)=uV(H): uvE(G), NG(v)简记为N(v);dH(v)=|NH(v)|称图 G 中

8、点 v 的度, d G(v)也简记为 d(v). 用 , 分别表示图G 中顶点的最小度和最大度, 即: = mind(v):vV(G), =maxd(v):v V(G);定义图 G 的连通度 K(G)为使图 G 不连通所要删去的顶点的最小数目, 对任意的 k|S|的独立集 S, G 的最大独立集的顶点数称为 G 的独立数, 记为 (G). 2 2-连通4,2-图中的圈 32.1 关于s,t-图有下述性质与结果:性质 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

9、设 G 是4, 2-图, 则:(a) G 是连通的当且仅当 G 同构于 K1, 3 或者 G 有 Hamilton 路. (b) G 是 2-连通的当且仅当 G 同构于 K2, 3 或者 G 同构于 K1, 1, 3 或者 G 有Hamilton 圈. 2.2 主要结果5下边的定理 2. 2. 1 是本文要证明的主要结果, 显然定理 2. 2. 1 要比定理 2. 1. 1 中(b)的结果更好 . 定理 2.2.1 设 G 是 2-连通4, 2-图, C 是 G 中满足|V(C)|4 则任取 xV(H), 有|N C(x)|=1.证明 若|N C(x)|2, 取 v1, v2N C(x)(v1

10、v2), 由论断 1:v1v2 E(C). 因为|C|4, 6所以|v 1+Cv2-|, |v2+Cv1-|必有一个2.不妨设: |v2+Cv1-|2, 考虑 Gx, v2-, 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-2 E(G), 否则 G 中有(|C|+

11、1)-圈 C= v2-2xv2v2-v2+Cv2-2, 矛盾！又 v1-v2-2 E(G), 否则 G 中有(|C|+1)-圈C=v1-v2-2Error! v1x v2v2-v2+C v1-, 矛盾！由 G 是 4, 2-图:必有 v2-2, v2+E(G). 如此考虑下去可得: 任意 vV(v 1+C v2-), 有 v v2+E(G), 特别地 v1+, v2+E(G), 这与论断 1 矛盾！论断 3 设 H1, H2 是 G-C 的两个分支, 则 NC(H1)NC(H2) = .证明 若 NC(H1)NC(H2) , 取 vN C(H1)NC(H2), 则有 x1v, x1vE(G),

12、 其中 x1V(H 1), 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 间必有两条独立边. 设: x1v1, x2v2 E(V(H), V(C), 其中 x1, x

13、2V(H)( x1x2), v1, v2 V(C)(v 1v2), 若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+2 E(G), 则由 G 是4, 2-图知必有 x1x2, v1+v2+2 E(G),则 G 中有(|C|+1)-圈C=v1+v2+2C v1x1 x2v2Error! v 1-, 矛盾！所以 v1v2 E(C). 考虑 Gx1, x2, v1-, v2+, 由论断 2 知 x1

14、v1-, 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+i E(G), i=1, 2, , (|C|/2)-1. 若|C|为奇数, 则 G 中有(|C|+1)- 圈C= x1v1Error!v1-(|C|/2-1)v2+(|C|/2-1)Error! v2 x2x1, 矛盾！若|C|为偶数且|C|8, 7考虑 Gx1, x2, v1-, v1-3, 由论断 2 知: x1v1-, x1v1-3, x2v

15、1-, x2v1-3 E(G)则由 G 是4, 2-图知必有 x1x2, v1-v1-3E(G), 则 G 有(|C|+1)-圈 C=x1v1v1-v1-3 Error!v2 x2x1, 矛盾！若|C|=6, 考虑 Gx1, x2, v1-, v2+2, 由论断 2 知 x1v1-, x1v2+2, x2v1-, x2v2+2 E(G),则由 G 是4, 2-图知必有 x1x2, v1-v2+2E(G), 则 G 有 7-圈 C=x1v1 v1-v2+2v2+v2 x2x1, 矛盾！情形 2 |C| =3设 C=v1v2v3v1, G-C 的分支数2, 取 G-C 的任意两个分支 H1, H2

16、, 因为 G 是2-连通的 , 所以|N C(Hi)|2, i=1 , 2. 又注意到|C|=3,可知 NCH1NCH2 , 这与推论 3 矛盾！因此 G-C 只能有一个分支, 设此分支为 H, |H|=1 或 2. 则易见 G 有4-圈, 此为矛盾！所以 |H|3; 由|C| =3 及|N C(H)|2 知 H 与 C 间必有两条独立边取两条这样的独立边, 不妨设为 x1v1, x2v2E(V(H), V(C), 其中 x1, x2 V(H), 且 x1x2, 则 x1x2 E(G) (否则 G 有 4-圈),对任意的 xV(H), 有 xv3 E(G), 若 xx 1, x2, 则结论显然

17、 , 设 xx 1, x2, 若 xv3 E(G), 考虑 Gx, x1, x2, v3, 由论断 1 知 x1v3, x2v3 E(G), 由 , 有 x1x2 E(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 相邻, 则

18、 G 有 4-圈, 此为矛盾！由此说明|H|=3, 即 G 同构于 F1.情形 3 |C| =4注意到对 G 的任一分支 H, 均有|N C(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), 若 v1v2 E(C), 考虑 Gx1, x2, v1-, v2-, 由论断 1 知x1v1-, x1v2-, x2v1-, x2

19、v2- E(G), 又 x1x2 E(G)(否则 G 有 5-圈), 这与 G 是4, 2-图矛盾！所以 v1v2E(C)子情形 3.1 |H|3取 x V(H)x 1, x2, 显然 x 不能与 x1, x2 同时相邻, 否则 G 有 4-圈, 不妨8设 xx2 E(G), 令 Cv 1, v2=v3, v4, 即 C= v1v2v3v4 v1, 所以有xv3 E(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),

20、考虑Gx, x2, v1, v3, 由论断 1 知 x2v1, x2v3, xv1, xv3 E(G), 由 G 是4, 2-图知 xx2, v1v3 E(G), 则 G 有 5-圈 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

21、(G), 及, 得到xv4 E(G), 显然这与 G 是4, 2- 图矛盾！注 子情形 3. 1 说明只需再考虑“G-C 的每个分支至多两个点”的情形. 子情形 3.2 |H|=2若|H|=2, 则 x1, x2 E(H)(a) 若 H 是 G-C 的唯一分支, 由论断 1 知 x1v2, x1v4, x2v1, x2v3 E(G)若 v2v4E(G), 则 G 有 5-圈 C= x1v1v4v2x2x1, 此为矛盾！若 v1v3E(G), 则 G 有 5-圈 C= x1v1v3v2x2x1, 此为矛盾！若 x1v3 E(G), x2v4 E(G)则 G 同构于 F2,若 x1v3E(G),

22、x 2v4 E(G)之一成立, 则 G 同构于 F3,若 x1v3E(G), x 2v4 E(G)都成立, 则 G 同构于 F4,(b)若 G-C 有两个分支 , 不妨设 H1 为 G-C 的另一分支若|H 1|=2, 设 V(H1)=y1, y2, 由|N C(H1)|2 及论断 3 得 y1v3, y2v4E(G), 考虑:Gx1, y1, v2, v4, 由论断 1 知 x1v4, x1v2, y1v4, y1v2 E(G), 又因为 x1y1 E(G), 这与 G 是4, 2-图矛盾！所以 |H1|=1. 设: V(H 1)=y, 由|N C(H1)|2 及论断 3 得yv3, yv4

23、E(G), 则 G 有 5-圈, 此为矛盾！注 上述两种子情形说明只需再考虑“G-C 的每个分支至多一个点”的情形. 子情形 3.3 |H| = 1设 V(H)=x, 由|N C(H)|2 及论断 1 得: xv1, xv3 E(G)且 v2v4 E(G), 否则G 有 5-圈. (a) 若 H 是 G-C 的唯一分支, 则当 v1v3 E(G)时, G 同构于 K2, 3 ,当9v1 v3 E(G)时, G 同构于 K1, 1, 3; (b)若 G-C 有两个分支, 不妨设 H1 为 G-C 的另一分支, 设 V(H1)=y, 由|N C(H1)|2 及论断 3 得 yv2, yv4 E(G

24、), 则 v1v3 E(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 是一个 Hamilton 图. 证明 用反证法证明, 假设 G 不是 Hamilton 图, 根据引理 3.2

25、, 图 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 的一个点割集且|V 0| = K(G), V1, V2, , Vp 是 G-V0 的全部连通分支设 Yi=

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

27、=T ,对于任何一个顶点 x V 2 和某个 1it 有不等式:|N(y1)(V(Ci)x)|+| N(y2)(V(Ci)x)|V(C i)|1, 因此, 可以推断出:d(y1) +d(y2)n1|V 2|n2, 任取 y3A 0y 1, y2, 由于 y3 的度小于 (G), 得到矛盾: d(v)+d(y1)+d(y2)+d(y3)K(G)+1+n2+(G)1 = n+(G)+K(G)2 4, 综上所述, 定理 3.1 成立. 4 总结图论中有很多著名的问题引发人们的兴趣, 如哈密尔顿问题, 邮寄员问题, 四色问题等等. 图论作为数学的一个分支, 它与数学的其他分支有密切的关系, 事实上图论为任何一个包含二元关系的系统提供了一个数学模型, 利用图直观、漂亮的表现特性可以使人对现实的系统有清晰的了解, 应用图论来解决物理学、化学、生物学、信息与计算机科学以及社会科学等问题已显示出极大的优越性, 本文参考前人的研究, 讨论了 2-连通4, 2-图中的圈以及图中含有 Hamilton 圈