哈密尔顿图的判定及应用毕业论文.doc

中国计量学院本科毕业设计（论文）哈密尔顿图的判定及应用Judgement and application of Hamilton graph学生姓名 徐杰一村 学号 0900801110 学生专业信息与计算科学 班级 09信算1班 二级学院 理学院 指导教师 陈琴 中国计量学院2013年5月郑 重 声 明本人呈交的毕业设计论文，是在导师的指导下，独立进行研究工作所取得的成果，所有数据、图片资料真实可靠。尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确的方式标明。本学位论文的知识产权归属于培养单位。学生签名： 日期： 分类号： O157 密 级： 公开 UDC： 62 学校代码： 10356 中国计量学院 本科毕业设计（论文） 哈密尔顿图的判定及应用Judgement and application of Hamilton graph作 者 徐杰一村 学号 0900801110 申请学位 理学学士 指导教师 陈琴 学科专业 信息与计算科学 培养单位 中国计量学院答辩委员会主席 评 阅 人 2013年 5月致谢论文的撰写工作已经基本上完成，这段时间也经历了很多的波折。从论文开始到结束，一直是在陈琴老师的指导下完成的，可以说没有老师的悉心指导，就没有这篇论文的诞生，在此，衷心感谢陈琴老师对我的指导。感谢老师不厌其烦的帮我修正论文中的错误，也感谢老师在我失去信心时的谆谆教诲。陈琴老师的严谨教学，用于创新，善于发现的精神不但在学习上为我树立了榜样，也给我未来的生活带来了帮助。再次感谢陈琴老师对我的指导！ 同时，也感谢理学院老师的辛勤教育，感谢所有给我帮助的同学和朋友们。 哈密尔顿图的判定及应用摘要：哈密尔顿图的研究是图论中不可或缺的一部分，这个问题的研究已经应用到了各个领域。合理的利用哈密尔顿图的结论，不仅可以节约大量的时间，更可以降低发展的成本。因此很多学者致力于哈密尔顿图的问题研究，也得到了很多了不起的突破。本文第一章大致叙述了哈密尔顿图的背景发展和相关知识。阐述了哈密尔顿图的研究现状和本文研究方向。第二章总结了五种哈密尔顿图的判定方法,分别介绍了狄拉克定理、奥勒定理、博萨定理和萨瓦达定理，并且补充了一个判定哈密尔顿图的必要条件。第三章着重介绍了货郎担问题的起源和发展，并且补充了一种树的搜索法。关键词：哈密尔顿图；判定方法；货郎担问题中图分类号：O157Judgement and application of Hamilton graphAbstract: Studying on the Hamilton graph is an indispensable part in graph theory , since this problem is widely used in a variety of fields. When the conclusions of Hamiltion graph are properly used, it not only can save a lot of time, but also can reduce the cost of development. Therefore, many scholars dedicated to the Hamilton graph problems and has made a number of significant breakthrough.The first chapter of this paper describes the background of Hamilton graph and some related knowledge, introduces the research status and research directions of Hamilton graph.The second chapter summarizes five methods for determining Hamilton graph. It introduces the Dirac Theorem, Oregon Theorem, Bossa Theorem and Savada Theorem, and adds a necessary condition for determining Hamilton graph.The third chapter mainly introduces the origin and development of the traveling salesman problem, and adds a method called tree search algorithm.Keywords: Hamilton graph; Judgement method; Traveling salesman problemClassification:O157目 次摘要：IAbstract：II目 次III1引言11.1 哈密尔顿图的起源11.2 研究背景和意义21.3 哈密尔顿图判定方法的发展21.4 本文的研究方向32哈密尔顿图的判定42.1 哈密尔顿图的定义42.2 哈密尔顿图的集中判定方法42.3 实例解析63哈密尔顿图的判定在货郎担问题中的应用83.1货郎担问题的由来和在现实中的应用83.2货郎担问题解决方法83.3树的搜索法94结论13参考文献14作者简历15学位论文数据集1663171 引言在查阅了大量资料后，可以发现哈密尔顿图在数学理论研究和现实应用中都具有重要的地位。哈密尔顿图的研究解决了大量的问题，但是还是有很多的问题还未得到解决。其中较为著名的就是关于货郎担问题的解决方案，至今还没有很好的答案。本文在综合了各种哈密尔顿图的判定方法之后，尝试用多种方法去解决货郎担问题，在比较后，找到一种相对较好的方法，也为将来的继续研究提供研究方向。1.1 哈密尔顿图的起源哈密尔顿（Hamilton）是一位出生在爱尔兰的天文学家和数学家. 他的一生是很丰富多彩的，自从他发现“四元数”后，他又发现了另一种称之为“The Icosian Calculus”的代数系统，这个系统包含有乘法和加法的运算算子，但是乘法并不满足交换律（即xy-yx这个规律）。他发现的这个代数系统是和正则12 面体有关的。于是在1859 年他提出下列周游世界的游戏: 在正十二面体的二十个顶点上依次标记伦敦、巴黎、莫斯科、华盛顿、北京、东京等世界着名大城市; 正十二面体的棱( 边) 表示连接这些城市的路线。问: 能否在图中做一次旅行,从顶点到顶点, 沿着边行走, 经过每个城市恰好一次之后再回到出发点?曾经有很多人不断追寻这个游戏的答案。可以应用拓扑的思想，将这正十二面体“拉平”将会得到一个和它同构的平面图（如图1-1），这样进行就可以将这个游戏转化为：要求必须沿着正十二面体的棱，怎样才能走完正则十二面体上的所有顶点，而且最后又回到起点的问题。 图1-1：哈密尔顿周游世界图从此人们将这类图称作哈密尔顿图，哈密尔顿图的研究也开始慢慢建立起来。1.2 研究背景和意义哈密尔顿图是图论的重要的一部分，随着数学和科学技术的蓬勃发展，它的应用已经渗透到自然科学、社会科学的各个领域。然而其发展的时间并不长，所以还有很多的地方有待改进。其在货郎担问题的研究上，更是进几十年才受到重视，然而他的应用却是非常广泛的，同样的方法，可以用以地震搜救，粮食分派，粮食运输，外出旅游等类似的各个方面。不仅能降低资源浪费，还可以最大化成果，对于受困的群众，多一分钟就可以多一分生存的希望。研究哈密尔顿图的判定不仅仅在数学和科学领域具有很高的的研究价值，在现实应用中更是可以得到有价值的结果。因此，本文的研究方向是很具有现实意义。1.3 哈密尔顿图判定方法的发展1952年英国数学家狄拉克最早提出了判定哈密尔顿图的充分条件， n 阶连通图G, 若, 则G 是哈密尔顿图。为哈密尔顿图的发展奠定了基础。8年后即1960年美国著名的图论专家奥斯坦奥勒推广狄拉克的工作，得到了更为广泛的结果-奥勒定理。：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。1962年，匈牙利的一个叫博萨德的少年发表了仅有一页长的论文，虽然论文很短，只有仅仅一页，但其结果却推广了奥勒定理。有一个的图，它的满足不等式，那么图就是哈密尔顿图。这一结果无疑是非常具有价值的，所以在当时引起了很多的关注.在之后的几年中，很多人都尝试改进他的工作，使其有一个系统清晰的结果，最后终于有一个捷克的青年数学家萨瓦达得到了比他更为完整的结论。有一个的图，而且满足条件对于任何一个小于的正整数i的不等式，最少有一个是成立的那么图就是哈密尔顿图。1995 年赵俊和宋序平只研究了3 连通图( 还遗留2 连通的情况) 的邻域并条件 的哈密尔顿连通图, 得到: 3 连通n 阶图G, 若, 则是哈密尔顿连通图或例外图。2001年2月广西大学计算机与信息工程学院的罗示丰提出了一种判别哈密尔顿图的新方法，在文章中他具体把方法分解为5步：第1 步: ; 第2 步: 找出图 度数最大的顶点; 第3 步: 删去 以及与 关联的所有边; 第4 步: , , ; 第5 步: 若 则停止计算, 否则 转第2 步。这种方法为计算机的判别提供了一个清晰的方向。时至今日，无论国内还是国外都已经发现了哈密尔顿图的巨大作用，很多研究者也把目光放在了哈密尔顿图的判定问题的解决上，相信不久的将来，就会有更加重大的突破。1.4 本文的研究方向从哈密尔顿图的问题出现以来，无数的学者进行了多方面的研究，也发现了无数哈密尔顿图的性质，从而对其进行判定。然而问题的复杂性让我们的研究时间还是显得非常的短暂，哈密尔顿图的判定问题至今也没有一个确定的最好的方法。而根据哈密尔顿图的判定条件的不同，选用的方法也不尽相同。本文主要介绍哈密尔顿图判定的狄拉克定理、奥勒定理、博萨定理、萨瓦达定理。对这些定理进行详细的介绍及实例演示。在这些演示的基础上，再补充定理，以完善这些定理中的缺陷。最后将这些方法应用到著名的货郎担问题上来进行应用。在本文中其他定理及应用由于篇幅原因就不一一赘述了。2 哈密尔顿图的判定2.1 哈密尔顿图的定义设G 是一个图，包含图G中的每个顶点的路就称为哈密尔顿路。通过图G 中每个顶点有且仅有一次的通路就称为哈密尔顿通路。通过图G中的每个顶点有且仅有一次的回路就称为哈密尔顿回路。一个图假如含有哈密尔顿回路，则这个图就是哈密尔顿图。2.2 哈密尔顿图的集中判定方法那么当我们拿到一个图的时候，怎么样去判断它是不是一个哈密尔顿图呢？如果是一个顶点较少的图，那么有时候我们可以通过简单的尝试和错误的方法来判定。但是当顶点较多、通路较复杂的情况下，这种方法就会让我们感到焦头烂额，同时准确率也会大大下降。于是很多数学家开始尝试找到一种判定哈密尔顿的充分必要条件。遗憾的是至今为止还没有一种判定的充分必要条件，事实上，想要找到一个完全充分适用的判定方法几乎是没有可能的。但是数学家们依然没有放弃寻找一种简单的判定哈密尔顿图的方法，这就形成了图论上一个著名的哈密尔顿问题。虽然目前得到的判定方法大多是存在一些充分不必要或者必要不充分的条件，但是对于平时问题的解决和简单的应用来说，在很多时候还是能起到简单判定的作用。下面将解析几种相对好的方法：由于对于任意一个图来说，如果它是哈密尔顿图，它的基础简单图一定是哈密尔顿图，所以在判定的时候我们只要考虑简单图。2.2.1 狄拉克定理和奥勒定理最早提出判定哈密尔顿图的是英国的数学家狄拉克。狄拉克定理需要做的是记录每个顶点X上有多少条通路，记通过顶点X的通路个数为D(X)，当图的每个的顶点的D(X)相当大时，这个图就是哈密尔顿图。定理1（狄拉克定理）：对于任意给定的一个图，如果这个图的顶点数，而且，那么这个图就是哈密尔顿图。狄拉克发现上述定理的八年后，经过不断的尝试和总结，著名的美国图论学家奥斯坦奥勒继续了狄拉克的工作，推广了狄拉克定理，得到了一个判定哈密尔顿图的基础结论，为后面的研究打开了一个方向。定理2（奥勒定理）：对于任意给定的一个图，如果这个图的顶点数，对于任意的两个顶点x、y有，那么这个图一定是哈密尔顿图。2.2.2 博萨定理和萨瓦达定理在奥勒定理被发现以后，一个叫博萨德的匈牙利少年用一篇仅有一页长的论文对奥勒定理进行了推广，得到了一个重要的定理，引起了数学界的广泛关注。为了能更好的理解博萨定理的结论，我们可以引入一些记号：对于任意的一个图G，x1,x2,xn 在这里分别表示图G的所有顶点，且序列数是由小到大排列的，我们用D(G)表示序列（D(x1),D(x2),D(xn)）,即存在关系有D(x1)D(x2) D(xn)。再假设有两个序列其具有相同个数的数字：X=（x1，x2，xn）；Y=（y1，y2，yn）。我们用XY表示当且仅当对于每一个i=1、2、n，j=1、2、n，都满足xiyj。例如：X=（1，2，3，4）； Y=（5，6，7，8）； Z=（6，4，5，3）。 我们可以得到YX,但是ZX却是错误的。 然后我们定义每一个的的整数得到一个序列P(n)：当n是奇数时，我们可以将P(n)定义成整数列：P(n)=（1,2,3,4，），一共包含n个数。当n是偶数时，我们可以将P(n)定义成整数列：P(n)=（1,2,3,4，）一共包含n个数。根据定义我们可以得到：P(3)= （1，2，2）；P(4)= （1，2，2，2）；P(5)= （1，2，2，3，3）；P(6)= （1，2，3，3，3，3）；P(7)= （1，2，3，3，4，4，4）；P(8)= （1，2，3，4，4，4，4，4）；有了上面这些基础说明，我们就能很清楚的阐述博萨德的重要发现了：定理3（博萨定理），任意一个的图，它的D(G)满足关系式有D(G)P(n),那么图G就是哈密尔顿图。博萨定理解决了很大一部分的哈密尔顿图的判定问题，但是依然还存在一定的问题，不满足博萨定理的图不一定不是哈密尔顿图，很多人不断思索如何改进，很多数学家提出了很多种改进方案，但是经过比较之后，捷克的数学家萨瓦达的结论脱颖而出。目前为止，萨瓦达定理依旧是一种较好的哈密尔顿图的判定方法。他的结论如下。定理4（萨瓦达定理）任意一个的图G，且D(G)=（a1,a2,an）满足鞋面的条件：对于每一个小于的整数i的两个不等式a1i+1，an-1n-i，至少有一个是成立的，那么图G就一定是哈密尔顿图。2.2.3补充的一个必要定理 萨瓦达定理对哈密尔顿图的判定做出了很大的改进，让我们又多了一种简单的方法，但是依然存在哈密尔顿图不满足萨瓦达定理。这个时候我们需要用到一个哈密尔顿图的必要条件。这个条件叙述如下：定理5（一个判定的必要条件）：设一个无向图G=(V,E)是一个哈密尔顿图，V1是V的一个非空子集，则有P(G-V1)|V1|。其中P(G-V1)表示从G中删除V1得到的连同分支数。这个条件的必要性可以由一下方法证明：证明：假设C是图G中的一条哈密尔顿回路。若V1当中的顶点是在C上彼此相邻的顶点，那么显然有：P(C-V1)=1|V1|；（2） 若V1中的顶点是在C上存在m个互不相邻，那么就有：P(C-V1)=m|V1|所以无论V1中的顶点在C上是相邻或是不相邻，或者兼有，都可以得到结论P(C-V1)|V1|同时由于C是图G的生成子图，所以可以得到：P(C-V1)P(G-V1) |V1|一般时候定理5可以用来判定一个图是非哈密尔顿图。判定哈密尔顿图的方法还有很多，但是最为常用的就是上述的五种方法，当然，时至今日，不乏有比这五种方法更为准确全面的方法，但是在这里就不一一介绍了。2.3 实例解析为了能够让读者更好的了解前文介绍的几种方法，下面举几个实例来进行验证。图2-1：图G1、G2在上图中的两个图G1、G2可以简单的应用定理1（狄拉克定理）得到，G1中的每个顶点x都有D(x)=3，而n=4，所以有D(x)=34/2=2。同样图G2中，任何一个顶点都有D(x)=4，而n=6，所以有D(x)=36/2=3。由此可以判定图G1、G2是哈密尔顿图。这两个图的判定同样可以应用奥勒定理进行判定，在图G1中任意两点x、y，有D(x)+D(y)=64；在图G2中任意两点x、y，有D(x)+D(y)=86，同样可以判定图G1、G2是哈密尔顿图。图2-2：图G3、G4为了更好的体现博萨定理和萨瓦达定理的优越性，可以使用图G3来进行比较。应用狄拉克定理时，明显n=5且D(x)=25/2=n/2，不能判定它是哈密尔顿图。同样使用奥勒定理时min（D(x)+D(y)）=45/2=n/2，也不能判定。但是简单的观察就可以发现图G3是一个哈密尔顿图。这个时候我们就可以用博萨定理进行判定。根据博萨定理有D(G3)=（2，2，3，3，4），而P(5)=（1，2，2，3，3），根据比较就有D(G3)P(5)，从而可以得到图G3是哈密尔顿图。同样也可以根据萨瓦达定理来进行判定，因为n=5，所以小于n/2的i有i=1、2。当i=1时，a1=22=i+1，成立；当i=2时，an-1=33=n-i，成立；同样可以判定图G3是哈密尔顿图。然而博萨定理和萨瓦达定理同样是不完善的，这一点图G4给我们作出了很好的例子。在应用博萨定理时D(G4)=(3，3，3，3，3，3，3，3)，P(8)= （1，2，3，4，4，4，4，4）；此时我们是不能说D(G4)P(8)的，没办法判定G4是哈密尔顿图。萨瓦达定理也对这个问题表示无能为力，在图G4中n=8，所以小于n/2的正整数i=1、2、3。当i=3时，a1=34=i+1，不成立；an-1=35=n-i，不成立，此时违反萨瓦达定理，所以也不能判定G4是哈密尔顿图。然而简单观察后就可以发现图G4是一个哈密尔顿图，所以博萨定理和萨瓦达定理是有一定的缺陷的。图G4为我们的进一步研究提供了方向，让我们能够不断的深入。相信在不久的将来会有一种简单的方法可以帮助我们得出结论。3 哈密尔顿图的判定在货郎担问题中的应用3.1货郎担问题的由来和在现实中的应用货郎担问题是由德国的著名数学家肯蒙那哥在1932年提出来的，80年来一直是哈密尔顿图的应用中的最典型的例子，无数人对其进行废寝忘食的研究。这个问题可以表述为：假设一个售货员需要在n个城市之间进行销售，现在我们已经知道了这n个城市中任意的两个城市之间的距离，现在售货员需要选择一条路线使得从出发的城市开始，经过其他的城市有且仅有一次，最后回到出发点，问这个售货员应该怎么样选择路线呢。将上述的问题进行数学提炼后所求的问题可以转化为，在一个加附了权值的完全图中，寻找一个权值最小的哈密尔顿回路。看似简单，但实际上却是非常复杂的问题，至今任何一种简化的解决方法都能够带来无法想象的价值。因为生活中需要遇到货郎担问题的地方实在是太多了，例如：（1）当我们外出旅游的时候，提前安排好路程最短的路线，不仅可以节省交通上的成本，还可以得到更多的时间来参观。（2）当地震等天灾发生时，我们需要组建搜救队伍对受灾区域进行救援，在受灾程度相近的情况下，安排合适的搜救路线，不仅可以挽回很多的经济损失，更重要的是可以挽救更多的生命。（3）再假设当我们出差坐飞机时，由于各地的情况不同导致各个地方之间的价格会不一样。我们选择合适的城市顺序，可以让我们得到大幅度的节约成本。为公司创造更多的利润。这类的问题还有很多，而这些问题都可以归结为货郎担问题。所以货郎担问题的研究是与生活直接相关的，是非常具有现实意义的。3.2货郎担问题解决方法那么到底应该怎样去解决货郎担问题呢，遗憾的是直到目前为止，虽然无数人为止奋斗，也得到了一些正确的结论，但是还是没有一种能够简单的解决哈密尔顿图的方法。美国的管理科学中有一篇讨论“货郎担问题”的文章，该文中提到：人类由于他的计算能力的限制，在解决货郎担问题上并不好。所以，现在人们对于这个问题的研究已经开始借助电子计算机来进行实现。1979年11月7日纽约时报上出现了一篇很有影响力的文章，它的标题为苏联的发现震动数学界，这篇文章虽然有一定的夸大成分存在，但是他所说的把货郎担问题的解决和计算机联系起来的思想确实没有错的。2001年广西大学计算机与信息工程学院的罗示丰提出了用计算机判定哈密尔顿图的方法。虽然这个方法还未应用到货郎担问题的解决上，但是却也坚定了很多人继续往这个方向研究的信心，在不久的将来这个问题一定可以获得更大的突破。德国是一个非常严谨的国家，德国的波恩大学的一位数学家很好的发挥了这一特点，当他知道西德有120个有铁路穿过的城市后，就准备找到一个最短路程的回路，应该怎么样去跑。他费尽心血从铁路局找到了准确的城市间铁路的长度，把整个问题变成了一个有7140个变数，120个方程及96个不等式的线性规划问题，人类的大脑已经对这样的问题表示无能为力了，最后不得不用电子计算机去算，才得到了最短的回路是6942公里。结果见图3-1。图3-1：西德120个城市最短路线图3.3树的搜索法那么在一般情况下我们可以借用什么方法来解决货郎担问题呢？在这里介绍一种较为简单的方法-树的搜索法。为了更好的理解这个方法，在这里我们举一个例子加以说明：设共有A、B、C、D、E五个城市，我们需要从A出发经过B、C、D、E四个城市有且仅有一次，最后再回到A。A、B、C、D、E五座城市之间的距离由下表进行表出：表3-1：五个城市之间的距离表ABCDB10C2020D505050E70608030图3-2：五个城市之间的连通情况我们选择从点A出发，先写A（0），0表示最初没有出发路线是的路程长度是0，然后我们可以列出下一步可能到达的城市，分别由B、C、D、E，可以得到四个节点为AB（10）、AC（20）、AD（50）、AE（70）。见图3-3。图3-3：树的搜索法第一步现在我们可以看到由城市B可能到达的城市有C、D、E，把节点AB（10）划掉，我们可以得到三个新的节点ABC（10+20）、ABD（10+50）、ABE（10+60）后面的20、50、60分别表示BC、BD、BE的长度，以此类推我们还可以得到的新节点有ACB(40)、ACD(70)、ACE(100)、ADB(100)、ADC(100)、ADE(80)、AEB(130)、AEC(150)、AED(100)九个节点。见图3-4。图3-4：树的搜索法第二步根据上述法则继续推广，就可以知道，假设是ABC的路径，那么到达C城以后，就只剩下了两种可能路径：ABCDEA和ABCEDA，于是我们划掉节点ABC（30），得到两个新的节点ABCDEA（180）和ABCEDA（190）。以此类推，我们可以得到其他的二十二个节点ABDCEA(260)、ABDECA(190)、ABECDA(250)、ABEDCA(170)、ACBDEA(190)、ACBEDA(180)、ACDBEA(250)、ACDEBA(170)、ACEBDA(260)、ACEDBA(190)、ADBCEA(270)、ADBECA(260)、ADCBEA(250)、ADCEBA(250)、ADEBCA(180)、ADECBA(190)、AEBCDA(250)、AEBDCA(250)、AECBDA(270)、AECDBA(260)、AEDBCA(190)、AEDCBA(180)。见图3-5。图3-5：树的搜索法第三步根据图我们可以发现，在5个城市之间我们一共可以得到二十四条回路，其中最短的两条为ABEDCA(170)和ACDEBA(170)。由此我们得到了在五个城市之间销售的最佳路线。做完这全部的工作后，我们回过头去看这个方法，可以发现在最后一步的计算时，一部分的工作是可以省略的。比如当我们找到第一条回路ABCDEA时，我们可以知道这条路径的长度是180，那么在之后的计算中，一旦发现路径的长度明显大于180，或者上一层的节点的数值已经大于180了，那么我们直接可以用“180”来代替具体的数值。当计算到ABEDCA这条路径时，我们发现数值是170，那么之后的数值如明显大于170，那么久可以用“170”来替代，这样可以节省一定的计算时间，加快得出结果的速度。在上面方法展示的过程中我们可以发现，这样的搜索方法在地点数量较少的时候还比较试用，一旦地点数量达到十个，那么我们的计算量将变的吓人，甚至可以说是超过了人脑的计算能力，我们会感到十分的繁琐。如果十个地点还可以勉强算出来，那么地点数量达到300个或者500个呢？那时候的计算量是我们无法想象的，而这种情况对于像中国这样的大国来说，是非常现实的问题。这个时候我们就不得不借助计算机的力量。计算机到底可以提升多少的计算速度呢？一个例子能够很好的说明问题：在美国工作的华籍数学家Lin Shen及Hong Saman等人在1977年的时候用电子计算器计算得到了一个有关于318个城市的货郎担问题。这个问题一旦化成线性规划问题，那么就要处理有50403个变数的方程式及不等式，人脑对于这样的问题虽然不能说完全不能解决，但是所需要的时间将是难以想象的。而当时的Lin Shen等人借助了一台IBM的370168式的电子计算机后，仅用了28.38分钟就得到了一个最优解，纳闷对于电子技术日新月异的今天，我们可能需要的时间已经不足一分钟。两者互相对比，让我们不得不承认，以后的发展方向将更多的借助计算机技术。4 结论 哈密尔顿图相可以应用的范围已经越来越广阔，从工业铺路到农业灌溉，航空路线到海底勘探，从国家的发展到公司的运输，都可以用到哈密尔顿图的知识。哈密尔顿图的研究已经显得越来越重要，在效率第一的当今社会，恰当的应用哈密尔顿图的研究结果可以可以大大提高工作的效率和节约发展成本，为可持续发展提供不可或缺的支持。本文借鉴总结了大量前人的结论，着重介绍了哈密尔顿图判定上的五种方法和结论，并初步对这五种方法的应用范围进行了分类。在哈密尔顿图的应用方面，着重介绍了货郎担问题的研究。在解决方法上又介绍了树的搜索法，同时也说明了解决方法的未来发展方向。参考文献1 Dir ac G A. Some theor ems on abstr act gr aphs J .Pr oc Londo n Math Soc. 1952, 2: 69 81。2 Faudr ee R J, Go uld R J, Jacobson M S, et al.Neighbor hoo d unio ns and highly Hamilton g r aphs J . Ar s Combinato ria, 1991, 31: 139 148。3 赵俊, 宋序平. 最小度与Hamilton 连通图 J . 扬州大学学报, 1995, 3: 39 45。4 尹家洪, 邻集并与hamiltonian 性 J , 东南大学学报, 1991, 21 。5 陈显强, 吴集林, 论哈密尔顿图的判定问题,科学技术与工程报，2005 年第1 期。6 罗示丰, 判别哈密尔顿图的新方法J, 广西科学院学报,2001年2月第十七卷第1期。7 赵克文, 新的充分条件和哈密尔顿图J, 中国工程科学, 2003 年11 月第5 卷第11 期。8 Fan G H. New sufficient condit ions for cycles ing raphs J . J Combin Theory Ser B 1984, 37: 221227。9于言坤，哈密尔顿图的矩阵判定法，吉林教育学院学报（下旬），2012.910陈德钦、赵克文, 哈密尔顿图的邻域交和邻域并条件, 科学技术与工程, 2006 年4 月第6 卷第8 期。11赵克文, 曾克扬, 一个充分条件和Hamilton 连通图, 应用科学学报,2003 年12 月第21 卷第4 期。12赵克文. 对2 连通n 阶图某些结果的改进 J . 吉林大学自然科学学报, 2001, 1: 39-46。13 Liqun Pua, Hung-Lin Fub, Hao Shenc Maximal sets of Hamilton cycles in Dn J scienceDirect 2008。14 B. Jackson, Long paths and cycles in oriented graphs, J. Graph Theory 5 (1981) 145157。15耿素云, 屈婉玲. 离散数学基础, 北京大学出版社, 1994 年7 月第1 版。16罗示丰. 两图同构的判别准则及其复杂性. 计算机科学, 1997, ( 10) 专辑: 148153。17钱颂迪等,运筹学,清华大学出版社，1990，247249。18魏权龄等, 运筹学通论,中国人民大学出版社，2000，338343。19徐俊明, 图论及其应用,中国科技大学出版社，1998，5253。20王树禾, 图论及其算法,中国科技大学出版社，1990，6465。21李修睦, 图论导引,华中工学院出版社，1982，107108。22 卢开澄等,图论及其应用,清华大学出版社，1995，7077。作者简历徐杰一村，男，出生与1990年4月，浙江省宁波市余姚市人，2009年9月至2013年6月就读于中国计量学院。在校期间，获得社会工作奖学金三次，校军训积极分子，校亮点网优秀部长。关键词*密级*中图分类号*UDC哈密尔顿图；判定方法；货郎担问题公开O15762论文赞助学位授予单位*学位授予单位代码*学位类别*学位级别*中国计量学院10356理学学士论文题名*哈密尔顿图的判定及应用论文语种*并列题名*无简体中文作者姓名*徐杰一村学号*0900801110培养单位名称*培养单位代码*培养单位地址邮编中国计量学院10356浙江省杭州下沙高教园区学源街310018学科专业*研究方向*学制*学位授予年*信息与计算科学4年2013论文提交日期*导师姓名*陈琴职称*讲师评阅人答辩委员会主席*答辩委员会成员电子版论文提交格式 文本（ ）图像（ ）视频（ ）音频（ ）多媒体（ ）其他（ ）推荐格式：application/msword；application/pdf电子版论文出版（发布者）电子版论文出版（发布）地权限声明论文总页数*23注：共33项，其中带“*”为必填数据。1. 基于C8051F单片机直流电动机反馈控制系统的设计与研究2. 基于单片机的嵌入式Web服务器的研究 3. MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究 4. 基于模糊控制的电阻钎焊单片机温度控制系统的研制 5. 基于MCS-51系列单片机的通用控制模块的研究 6. 基于单片机实现的供暖系统最佳启停自校正（STR）调节器7. 单片机控制的二级倒立摆系统的研究8. 基于增强型51系列单片机的TCP/IP协议栈的实现 9. 基于单片机的蓄电池自动监测系统 10. 基于32位嵌入式单片机系统的图像采集与处理技术的研究11. 基于单片机的作物营养诊断专家系统的研究 12. 基于单片机的交流伺服电机运动控制系统研究与开发 13. 基于单片机的泵管内壁硬度测试仪的研制 14. 基于单片机的自动找平控制系统研究 15. 基于C8051F040单片机的嵌入式系统开发 16. 基于单片机的液压动力系统状态监测仪开发 17. 模糊Smith智能控制方法的研究及其单片机实现 18. 一种基于单片机的轴快流CO,2激光器的手持控制面板的研制 19. 基于双单片机冲床数控系统的研究 20. 基于CYGNAL单片机的在线间歇式浊度仪的研制 21. 基于单片机的喷油泵试验台控制器的研制 22. 基于单片机的软起动器的研究和设计 23. 基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究 24. 基于单片机的机电产品控制系统开发 25. 基于PIC单片机的智能手机充电器 26. 基于单片机的实时内核设计及其应用研究 27. 基于单片机的远程抄表系统的设计与研究 28. 基于单片机的烟气二氧化硫浓度检测仪的研制 29. 基于微型光谱仪的单片机系统 30. 单片机系统软件构件开发的技术研究 31. 基于单片机的液体点滴速度自动检测仪的研制32. 基于单片机系统的多功能温度测量仪的研制 33. 基于PIC单片机的电能采集终端的设计和应用 34. 基于单片机的光纤光栅解调仪的研制 35. 气压式线性摩擦焊机单片机控制系统的研制 36. 基于单片机的数字磁通门传感器 37. 基于单片机的旋转变压器-数字转换器的研究 38. 基于单