2-连通[4,2]-图中的圈以及含有Hamilton圈的一个充分条件的再证明 毕业论文.doc
《2-连通[4,2]-图中的圈以及含有Hamilton圈的一个充分条件的再证明 毕业论文.doc》由会员分享,可在线阅读,更多相关《2-连通[4,2]-图中的圈以及含有Hamilton圈的一个充分条件的再证明 毕业论文.doc(10页珍藏版)》请在三一文库上搜索。
1、 1 2-连通4,2-图中的圈以及含有 Hamilton 圈的一个充分条件的再证明 摘要:图论(Graph Theory)的研究开始于 200 多年前, 关于图论的第一篇论文是 1736 年 Euler 发表的, 他用图论的方法解决了格尼斯堡(Konigsberg)七桥问题. 图的 Hamilton 问 题是图论中一个十分重要且又十分活跃的研究课题, 1857 年, 爱尔兰数学家哈密顿提出: 一个连通图有哈密顿圈的充要条件是什么?这样一个问题. 但是这个问题至今仍未能解决, 以 Hamilton 问题为出发点发展起了对图的圈性质的研究, 这些性质主要包括 Hamilton 性、 泛圈性、完全圈
2、可扩性等. 本文的主要内容包括三个部分: 在第一部分中主要介绍了文章 中所涉及的一些概念、术语符号和本文的研究背景及已有的结果;在第二部分中讨论 2-连 通 4,2-图中的圈;在第三部分中讨论了图中含有 Hamilton 圈的一个充分条件. 关键词:s, t-图;连通度;s-点连通图;完全圈可扩性;最长圈;Hamilton 圈;独立 数 中图分类号: O 157. 5 The Cycles in 2-connected4,2-graphs and another proof of a sufficient condition for the graph containing Hamilton
3、cycles Abstract: 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, Irish mathematician Hamilton put forwar
4、d 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. These natures are hamiltonicity, pancyclici
5、ty, 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 cycles in 2- connected4, 2-graphs; in the t
6、hird part we discussed a sufficient condition for the graph contains Hamilton cycle. 2 Key words: s,t-graph; connectivity; s-vertices connected graph; fully cycle extensibility; the longest cycle; Hamilton cycle; independence number 1 预备知识 1-2 1.1 符号概念介绍 本文考虑的图是有限、无向、简单图, 文中所使用的记号和术语约定如下: 设 G=(V(G),
7、 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 中点 v 的度, d G(v)也简记为 d(v). 用 , 分别表示图 G 中顶点的最小度和最大度, 即: = mind(v):vV(G), =maxd(v)
8、:v V(G); 定义图 G 的连通度 K(G)为使图 G 不连通所要删去的顶点的最小数目, 对任 意的 k|S|的独立 集 S, G 的最大独立集的顶点数称为 G 的独立数, 记为 (G). 2 2-连通4,2-图中的圈 3 2.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 设 G 是4, 2-图, 则: (a) G 是连通的当且仅当 G 同构于 K1, 3 或者 G 有 Hamilton 路. (b) G 是 2-
9、连通的当且仅当 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)|4 则任取 xV(H), 有|N C(x)|=1. 证明 若|N C(x)|2, 取 v1, v2N C(x)(v1v2), 由论断 1:v1v2 E(C). 因为|C|4, 所以|v 1+Cv2-|, |v2+Cv1-|必有一个2.不妨设: |v2+C
10、v1-|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|+1)-圈 C= v2-2xv2v2-v2+Cv2-2, 矛盾!又 v1-v2-2 E(G), 否则 G 中有(|C|+1)-圈 C=v
11、1-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), 其中 x1V(H 1), x2V( H2), 考虑 G x1, x2, v-, v+, 由论断 1:x1v-, x1v+, x
12、2v-, x2v+ 5 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, x2V(H)( x1x2), v1, v2 V(C)(v 1v2), 若 v1v2 E(C), 由于|C|4, 所
13、以|v 1+C v1-|, |v2+C v1-|必有一个2. 不妨设: |v 2+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 知 x1v1-, x1v2+, x2v1-, x2v2+ E(G), 则由 G 是4, 2-图知必有 x1x2
14、, 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, 考虑 Gx1, x2, v1-, v1-3, 由论断 2 知: x1v1-, x1v1-3, x2v1-, x2v1-3 E(G)则由 G 是 4, 2-图知必有 x1x2, v1-v1-3E(G)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2-连通4 2-图中的圈以及含有Hamilton圈的一个充分条件的再证明 毕业论文 连通 中的 以及 含有 Hamilton 一个 充分 条件 证明
链接地址:https://www.31doc.com/p-25860.html