欢迎来到人人文库网! | 帮助中心 人人文库renrendoc.com美如初恋!
人人文库网
首页 人人文库网 > 资源分类 > DOC文档下载

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

  • 资源大小:203.00KB        全文页数:11页
  • 资源格式: DOC        下载权限:游客/注册会员/VIP会员    下载费用:8
游客快捷下载 游客一键下载
会员登录下载
下载资源需要8

邮箱/手机号:
您支付成功后,系统会自动为您创建此邮箱/手机号的账号,密码跟您输入的邮箱/手机号一致,以方便您下次登录下载和查看订单。注:支付完成后需要自己下载文件,并不会自动发送文件哦!

支付方式: 微信支付    支付宝   
验证码:   换一换

友情提示
2、本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

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

1毕业论文题目2连通4,2图中的圈以及含有HAMILTON圈的一个充分条件的再证明学院数学与信息科学学院专业数学与应用数学毕业年限2012届学生姓名学号指导教师22连通4,2图中的圈以及含有HAMILTON圈的一个充分条件的再证明摘要图论GRAPHTHEORY的研究开始于200多年前,关于图论的第一篇论文是1736年EULER发表的,他用图论的方法解决了格尼斯堡KONIGSBERG七桥问题图的HAMILTON问题是图论中一个十分重要且又十分活跃的研究课题,1857年,爱尔兰数学家哈密顿提出一个连通图有哈密顿圈的充要条件是什么这样一个问题但是这个问题至今仍未能解决,以HAMILTON问题为出发点发展起了对图的圈性质的研究,这些性质主要包括HAMILTON性、泛圈性、完全圈可扩性等本文的主要内容包括三个部分在第一部分中主要介绍了文章中所涉及的一些概念、术语符号和本文的研究背景及已有的结果;在第二部分中讨论2连通4,2图中的圈;在第三部分中讨论了图中含有HAMILTON圈的一个充分条件关键词S,T图;连通度;S点连通图;完全圈可扩性;最长圈;HAMILTON圈;独立数中图分类号O1575THECYCLESIN2CONNECTED4,2GRAPHSANDANOTHERPROOFOFASUFFICIENTCONDITIONFORTHEGRAPHCONTAININGHAMILTONCYCLESABSTRACTGRAPHTHEORYBEGAN200YEARSAGO,EULERPUBLISHEDTHEFIRSTPAPERONGRAPHTHEORYIN1736,HEUSEDGRAPHTHEORYTOSOLVETHEKONIGSBERGSEVENBRIDGESTHEHAMILTONPROBLEMISAVERYIMPORTANTANDACTIVERESEARCHTOPICINGRAPHTHEORY,IN1857,IRISHMATHEMATICIANHAMILTONPUTFORWARDAPROBLEM“WHATISTHENECESSARYANDSUFFICIENTCONDITIONWHENACONNECTEDGRAPHHASAHAMILTONCYCLE”HOWEVER,ITHASNOTBEENSOLVEDUNTILNOW,ATTHESAMETIMEBASEDONHAMILTONPROBLEM,ARESEARCHONNATURESOFCYCLESINGRAPHHASBEENCARRIEDOUTTHESENATURESAREHAMILTONICITY,PANCYCLICITY,EXTENSIBILITYETCTHEMAINCONTENTOFTHISPAPERCONSISTSOFTHREEPARTSINTHEFIRSTPARTINTRODUCESSOMEOFTHECONCEPTSTERMSSYMBOLSCOVEREDINTHEARTICLE,ANDTHERESEARCHBACKGROUNDANDTHEEXISTINGRESULTS;INTHESECONDPARTWEDISCUSSEDTHECYCLESIN2CONNECTED4,2GRAPHS;INTHETHIRDPARTWEDISCUSSEDASUFFICIENTCONDITIONFORTHEGRAPHCONTAINSHAMILTONCYCLEKEYWORDSS,TGRAPH;CONNECTIVITY;SVERTICESCONNECTEDGRAPH;FULLYCYCLEEXTENSIBILITY;THELONGESTCYCLE;HAMILTONCYCLE;INDEPENDENCENUMBER31预备知识1211符号概念介绍本文考虑的图是有限、无向、简单图,文中所使用的记号和术语约定如下设GVG,EG是一个图,VG、EG分别表示G的顶点集和边集|G||VG|表示G中顶点的数目,称为G的阶,|EG|表示G中边的数目;对顶点集{V1,V2,VM}VG,用GV1,V2,VM表示G中由{V1,V2,VM}导出的子图;对V∈VG及G的子图H,记NHV{U∈VHUV∈EG},NGV简记为NV;DHV|NHV|称图G中点V的度,DGV也简记为DV用Δ,△分别表示图G中顶点的最小度和最大度,即ΔMIN{DVV∈VG},△MAX{DVV∈VG};定义图G的连通度KG为使图G不连通所要删去的顶点的最小数目,对任意的KKG,称G为K连通的;对VG的子集S、T,令ES,T{ST∈EGS∈S,T∈T};设CV1V2VRV1,是G的一个圈,VI,VJ∈VC,用VI1和VI1分别表示C上的点VI1和VI1,VI1和VI1也分别简记成VI和VI;用VICVJ和VIC__VJ1≤IJ≤R分别表示C上的路VIVI1VJ和VIVI1VJ;|C||VC|称为圈C的长度,若C的长度为R,则称C为G的一个R圈;G中经过G的每个顶点恰一次的路叫做G的的HAMILTON路,同样地G中经过G的每个顶点恰一次的圈叫做G的HAMILTON圈;如果一个图G中存在一个HAMILTON圈,则称G为HAMILTON的;如果图G的任意两个顶点之间都有一条HAMILTON路,则称G为HAMILTON连通的;对一个有N个顶点的图G,如果对任意的K3≤K≤N,G都有长度为K的圈,则称G为泛圈图;如果图G满足1G的每一个顶点都在一个3圈上;2对G中任意一个圈C,只要|C||G|,就存在G的圈C,使VCVC且|C||C|1,则称G是完全圈可扩的,同时称C为C的扩圈;如果图G中任意S个点的导出子图至少含有T条边,则称图G为S,T图4如果图G中任意SS≥3个点的导出子图是连通的,且存在S1个点的导出子图是不连通的,则称图G为S点连通图;设S是VG的一个子集,若S中任意两个顶点在G中均不相连则称S是G的一个独立集;G的一个独立集S称为G的最大独立集,如果G不包含满足|S||S|的独立集S,G的最大独立集的顶点数称为G的独立数,记为ΑG22连通4,2图中的圈321关于S,T图有下述性质与结果性质211S,T图必是S,T1图性质212S,T图必是S1,T图性质213S,T图必是S1,T1图定理211设G是4,2图,则AG是连通的当且仅当G同构于K1,3或者G有HAMILTON路BG是2连通的当且仅当G同构于K2,3或者G同构于K1,1,3或者G有HAMILTON圈22主要结果下边的定理221是本文要证明的主要结果,显然定理221要比定理211中B的结果更好定理221设G是2连通4,2图,C是G中满足|VC||VG|的任一圈,则或者G中有|C|1圈,或者G同构于K2,3,K1,1,3,F1,F2,F3,F4,F5其中F1,F2,F3,F4,F5如下图图F1图F2图F35图F4图F523定理221的证明4证明设图G满足定理条件,C是G的一个圈,且|VC||VG|,以下总假定G中不含|C|1圈,取GC的一个分支H,因为G是2连通的,所以|NCH|≥2论断1设U,V∈VC,X∈VH,若XU∈EG,XV∈EG则{XU,XU}EG,{XV,XV}EG,{UV,UV}EG证明若XV∈EG,则G有|C|1圈CVCVXV,矛盾所以XVEG,同理可证XVEG,UV,UV}EG若UV∈EG,则G有|C|1圈CUXVC__UVCU,矛盾同理可证UVEG论断2设G是2连通4,2图,若|C|4则任取X∈VH,有|NCX|1证明若|NCX|≥2,取V1,V2∈NCXV1≠V2,由论断1V1V2EC因为|C|4,所以|V1CV2|,|V2CV1|必有一个≥2不妨设|V2CV1|≥2,考虑GX,V2,V2,V1,由论断1XV1,XV2,XV2,V1V2EC;由G是4,2图,必有V2V2∈EG若V22V1,则G中有|C|1圈CV1XV2V2V2CV1,矛盾所以V22≠V1考虑GX,V22,V2,V1,由论断1XV1,XV2EG,又XV22EG,否则G中有|C|1圈CV22XV2V2V2CV22,矛盾又V1V22EG,否则G中有|C|1圈CV1V22C__V1XV2V2V2CV1,矛盾由G是4,2图必有V22,V2∈EG如此考虑下去可得任意V∈VV1CV2,有VV2∈EG,特别地V1,V2∈EG,这与论断1矛盾论断3设H1,H2是GC的两个分支,则NCH1∩NCH2证明若NCH1∩NCH2≠,取V∈NCH1∩NCH2,则有X1V,X1V∈EG,其中X1∈VH1,X2∈VH2,考虑GX1,X2,V,V,由论断1X1V,X1V,X2V,X2VEG,这与G是4,2图矛盾论断4对G的任一分支H,|H|≥2,则H与C间必有两条独立边6证明此结论显然以下分3种情形完成定理的证明情形1|C|4取GC的一个分支H,由论断2知任取X∈VH,有NCX1,又因为G是2连通的,所以|NCH|≥2,所以H与C间必有两条独立边设X1V1,X2V2∈EVH,VC,其中X1,X2∈VHX1≠X2,V1,V2∈VCV1≠V2,若V1V2EC,由于|C|4,所以|V1CV1|,|V2CV1|必有一个≥2不妨设|V2CV1|≥2考虑GX1,X2,V1,V22,由论断2知X1V1,X1V22,X2V1,X2V22EG,则由G是4,2图知必有X1X2,V1V22∈EG,则G中有|C|1圈CV1V22CV1X1X2V2C__V1,矛盾所以V1V2∈EC考虑GX1,X2,V1,V2,由论断2知X1V1,X1V2,X2V1,X2V2EG,则由G是4,2图知必有X1X2,V1V2∈EG考虑GX1,X2,V12,V22,由上述讨论可得V12V22∈EG如此下去可得V1IV2I∈EG,I1,2,,|C|/21若|C|为奇数,则G中有|C|1圈CX1V1C__V1|C|/21V2|C|/21C__V2X2X1,矛盾若|C|为偶数且|C|≥8,考虑GX1,X2,V1,V13,由论断2知X1V1,X1V13,X2V1,X2V13EG则由G是4,2图知必有X1X2,V1V13∈EG,则G有|C|1圈CX1V1V1V13C__V2X2X1,矛盾若|C|6,考虑GX1,X2,V1,V22,由论断2知X1V1,X1V22,X2V1,X2V22EG,则由G是4,2图知必有X1X2,V1V22∈EG,则G有7圈CX1V1V1V22V2V2X2X1,矛盾情形2|C|3设CV1V2V3V1,GC的分支数≥2,取GC的任意两个分支H1,H2,因为G是2连通的,所以|NCHI|≥2,I1,2又注意到|C|3,可知NCH1∩NCH2≠,这与推论3矛盾因此GC只能有一个分支,设此分支为H,|H|1或2则易见G有4圈,此为矛盾所以|H|≥3;由|C|3及|NCH|≥2知H与C间必有两条独立边取两条这样的独立边,不妨设为X1V1,X2V2∈EVH,VC,其中X1,X2∈VH,且X1≠X2,则X1X2EG①否则G有4圈,对任意的X∈VH,有XV3EG②,若X∈{X1,X2},则结论显然,设X∈{X1,X2},若XV3∈EG,考虑GX,X1,X2,V3,由论断1知X1V3,X2V3EG,由①,有X1X2EG,又X1XEG否则G有4圈,7同理X2XEG,对任意的X∈VH,有XX1,XX2∈EG③,考虑GX,X1,X2,V3,由论断1知X1V3,X2V3EG,又由①②有X1X2,XV3EG,由G是4,2图知必有XX1,XX2∈EG;若|H|≥4,取X3,X4∈VH-{X1,X2},由③知X3,X4均与X1,X2相邻,则G有4圈,此为矛盾由此说明|H|3,即G同构于F1情形3|C|4注意到对G的任一分支H,均有|NCH|≥2且|C|4,结合论断3可知GC至多有2个分支,取GC的一个分支H,若|H|≥2,由论断4知H与C间必有2条独立边,取两条这样的独立边,设X1V1,X2V2∈EVH,VC,其中X1,X2∈VHX1≠X2,V1,V2∈VCV1≠V2,若V1V2EC,考虑GX1,X2,V1,V2,由论断1知X1V1,X1V2,X2V1,X2V2EG,又X1X2EG否则G有5圈,这与G是4,2图矛盾所以V1V2∈EC子情形31|H|≥3取X∈VH-{X1,X2},显然X不能与X1,X2同时相邻,否则G有4圈,不妨设XX2EG,令C-{V1,V2}{V3,V4},即CV1V2V3V4V1,所以有XV3EG,XV4EG④;若XV3∈EG,考虑GX,X1,V2,V4,由论断1知X1V2,X1V4,XV2,XV4EG,XX1EG,这与G是4,2图矛盾若XV4∈EG,考虑GX,X2,V1,V3,由论断1知X2V1,X2V3,XV1,XV3EG,由G是4,2图知XX2,V1V3∈EG,则G有5圈CXX2V2V3V4X,此为矛盾考虑GX,X1,V3,V4,由假设及论断1得XX1,X1V4EG,又因为④及G是4,2图,则X1V3∈EG,若V2V4∈EG则G有5圈CV1X1V3V2V4V1,此为矛盾所以V2V4EG,考虑GX,X1,V2,V4由假设及论断1得XX1,X1V4,X1V2EG,又因为V2V4EG,及④,得到XV4EG,显然这与G是4,2图矛盾注子情形31说明只需再考虑“GC的每个分支至多两个点”的情形子情形32|H|2若|H|2,则X1,X2∈EHA若H是GC的唯一分支,由论断1知X1V2,X1V4,X2V1,X2V3EG若V2V4∈EG,则G有5圈CX1V1V4V2X2X1,此为矛盾若V1V3∈EG,则G有5圈CX1V1V3V2X2X1,此为矛盾若X1V3EG,X2V4EG则G同构于F2,

注意事项

本文(数学与应用数学毕业论文-2-连通[4_2]-图中的圈以及含有Hamilton圈的一个充分条件的再证明.doc)为本站会员(liyun)主动上传,人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知人人文库网(发送邮件至[email protected]或直接QQ联系客服),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

网站客服QQ:2846424093    人人文库上传用户QQ群:460291265   

[email protected] 2016-2018  renrendoc.com 网站版权所有   南天在线技术支持

经营许可证编号:苏ICP备12009002号-5