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

《数学与应用数学毕业论文-2-连通[4_2]-图中的圈以及含有hamilton圈的一个充分条件的再证明》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业论文题目：2-连通[4,2]-图中的圈以及含有Hamilton圈的一个充分条件的再证明学院：数学与信息科学学院专业：数学与应用数学毕业年限：2012届学生姓名：……学号：指导教师：……12-连通[4,2]-图中的圈以及含有Hamilton圈的一个充分条件的再证明摘要：图论(GraphTheory)的研究开始于200多年前,关于图论的第一篇论文是1736年Euler发表的,他用图论的方法解决了格尼斯堡(Konigsberg)七桥问题.图的Hamilton问题是图论中一个十分重要且又十分活跃的研究课题,

2、1857年,爱尔兰数学家哈密顿提出:一个连通图有哈密顿圈的充要条件是什么?这样一个问题.但是这个问题至今仍未能解决,以Hamilton问题为出发点发展起了对图的圈性质的研究,这些性质主要包括Hamilton性、泛圈性、完全圈可扩性等.本文的主要内容包括三个部分:在第一部分中主要介绍了文章中所涉及的一些概念、术语符号和本文的研究背景及已有的结果；在第二部分中讨论2-连通[4,2]-图中的圈；在第三部分中讨论了图中含有Hamilton圈的一个充分条件.关键词：[s,t]-图；连通度；s-点连通图；完全圈可扩

3、性；最长圈；Hamilton圈；独立数中图分类号:O157.5TheCyclesin2-connected[4,2]-graphsandanotherproofofasufficientconditionforthegraphcontainingHamiltoncyclesAbstract:GraphTheorybegan200yearsago,Eulerpublishedthefirstpaperongraphtheoryin1736,heusedgraphtheorytosolvetheKonigs

4、bergSevenBridges.theHamiltonproblemisaveryimportantandactiveresearchtopicingraphtheory,In1857,IrishmathematicianHamiltonputforwardaproblem:“whatisthenecessaryandsufficientconditionwhenaconnectedgraphhasaHamiltoncycle.”However,ithasnotbeensolveduntilnow,A

5、tthesametimebasedonHamiltonproblem,aresearchonnaturesofcyclesingraphhasbeencarriedout.Thesenaturesarehamiltonicity,pancyclicity,extensibilityetc.Themaincontentofthispaperconsistsofthreeparts:inthefirstpartintroducessomeoftheconceptstermssymbolscoveredint

6、hearticle,andtheresearchbackgroundandtheexistingresults;inthesecondpartwediscussedthecyclesin2-connected[4,2]-graphs;inthethirdpartwediscussedasufficientconditionforthegraphcontainsHamiltoncycle.Keywords:[s,t]-graph;connectivity;s-verticesconnectedgraph;

7、fullycycleextensibility;thelongestcycle;Hamiltoncycle;independencenumber2[1-2]1预备知识1.1符号概念介绍本文考虑的图是有限、无向、简单图,文中所使用的记号和术语约定如下:设G=(V(G),E(G))是一个图,V(G)、E(G)分别表示G的顶点集和边集.

8、G

9、=

10、V(G)

11、表示G中顶点的数目,称为G的阶,

12、E(G)

13、表示G中边的数目;对顶点集{V1,V2,…Vm}V(G),用G[V1,V2,…Vm]表示G中由{V1,V2,…

14、Vm}导出的子图;对v∈V(G)及G的子图H,记NH(v)={u∈V(H):uv∈E(G)},NG(v)简记为N(v);dH(v)=

15、NH(v)

16、称图G中点v的度,dG(v)也简记为d(v).用δ,△分别表示图G中顶点的最小度和最大度,即:δ=min{d(v):v∈V(G)},△=max{d(v):v∈V(G)};定义图G的连通度K(G)为使图G不连通所要删去的顶点的最小数目,对任意的k