大学毕业设计---哈密尔顿图的判定及应用.doc

《大学毕业设计---哈密尔顿图的判定及应用.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国计量学院本科毕业设计（论文）哈密尔顿图的判定及应用JudgementandapplicationofHamiltongraph学生姓名徐杰一村学号0900801110学生专业信息与计算科学班级09信算1班二级学院理学院指导教师陈琴中国计量学院2013年5月郑重声明本人呈交的毕业设计论文，是在导师的指导下，独立进行研究工作所取得的成果，所有数据、图片资料真实可靠。尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中

2、以明确的方式标明。本学位论文的知识产权归属于培养单位。学生签名：日期：分类号：O157密级：公开UDC：62学校代码：10356中国计量学院本科毕业设计（论文）哈密尔顿图的判定及应用JudgementandapplicationofHamiltongraph作者徐杰一村学号0900801110申请学位理学学士指导教师陈琴学科专业信息与计算科学培养单位中国计量学院答辩委员会主席评阅人2013年5月致谢论文的撰写工作已经基本上完成，这段时间也经历了很多的波折。从论文开始到结束，一直是在陈琴老师的指导下完成的，可以

3、说没有老师的悉心指导，就没有这篇论文的诞生，在此，衷心感谢陈琴老师对我的指导。感谢老师不厌其烦的帮我修正论文中的错误，也感谢老师在我失去信心时的谆谆教诲。陈琴老师的严谨教学，用于创新，善于发现的精神不但在学习上为我树立了榜样，也给我未来的生活带来了帮助。再次感谢陈琴老师对我的指导！同时，也感谢理学院老师的辛勤教育，感谢所有给我帮助的同学和朋友们。哈密尔顿图的判定及应用摘要：哈密尔顿图的研究是图论中不可或缺的一部分，这个问题的研究已经应用到了各个领域。合理的利用哈密尔顿图的结论，不仅可以节约大量的时间，更可以降

4、低发展的成本。因此很多学者致力于哈密尔顿图的问题研究，也得到了很多了不起的突破。本文第一章大致叙述了哈密尔顿图的背景发展和相关知识。阐述了哈密尔顿图的研究现状和本文研究方向。第二章总结了五种哈密尔顿图的判定方法,分别介绍了狄拉克定理、奥勒定理、博萨定理和萨瓦达定理，并且补充了一个判定哈密尔顿图的必要条件。第三章着重介绍了货郎担问题的起源和发展，并且补充了一种树的搜索法。关键词：哈密尔顿图；判定方法；货郎担问题中图分类号：O15716JudgementandapplicationofHamiltongraphA

5、bstract:StudyingontheHamiltongraphisanindispensablepartingraphtheory,sincethisproblemiswidelyusedinavarietyoffields.WhentheconclusionsofHamiltiongraphareproperlyused,itnotonlycansavealotoftime,butalsocanreducethecostofdevelopment.Therefore,manyscholarsdedic

6、atedtotheHamiltongraphproblemsandhasmadeanumberofsignificantbreakthrough.ThefirstchapterofthispaperdescribesthebackgroundofHamiltongraphandsomerelatedknowledge,introducestheresearchstatusandresearchdirectionsofHamiltongraph.Thesecondchaptersummarizesfivemet

7、hodsfordeterminingHamiltongraph.ItintroducestheDiracTheorem,OregonTheorem,BossaTheoremandSavadaTheorem,andaddsanecessaryconditionfordeterminingHamiltongraph.Thethirdchaptermainlyintroducestheoriginanddevelopmentofthetravelingsalesmanproblem,andaddsamethodca

8、lledtreesearchalgorithm.Keywords:Hamiltongraph;Judgementmethod;TravelingsalesmanproblemClassification:O15716目次摘要：IAbstract：II目次III1引言11.1哈密尔顿图的起源11.2研究背景和意义21.3哈密尔顿图判定方法的发展21.4本文的研究方向32哈密尔顿图的判定42.1哈密尔顿