全文总字数：2895字

1. 研究目的与意义及国内外研究现状

图论是组合数学和离散数学的重要分支，不仅是富有趣味和应用极为广泛的一门学科，而且是研究自然科学、工程技术、经济管理和社会问题的一个重要数学工具。

从理论上，图论用一组点来代表实物，用一组边来联系不同事物，形成一个抽象图形来研究点与边之间的特征。众所周知，第一篇奠基性图论论文是欧拉曾在1736年所解释的著名的哥尼斯堡七桥问题。1936年，世界上的首篇图论论著《有限图和无限图理论》是由著名的图论学家柯尼希发表的。此后，图论越来越受到全世界各界工作者的高度重视，不但将其应用于自然科学的研究，还应用于解决社会科学研究中的一些难题。现如今，图论知识已经广泛地应用于电力网络、交通运输、随机过程、故障诊断、人工智能、地图着色等一系列领域。

哈密尔顿图作为图论中重要的一部分，随着数学与计算机科学技术的蓬勃发展，它被广泛地应用于自然科学、社会科学等各个领域。然而其发展时间相对较短，因此还有很多地方有待改进。由哈密尔顿图推广得出的旅行商问题，更是近几十年才受到重视，它的应用非常广泛。可以用以地震搜救、粮食分派、货物运输、旅游计划等类似的各个方面。不仅能有效降低资源浪费，还可以将收益最大化。尤其对于

2. 研究的基本内容

从哈密尔顿图的问题出现以来，无数的学者进行了多方面的研究，也发现了很多哈密尔顿图的性质，并利用这些性质对一个图进行判定。然而问题的复杂性让投入的研究时间还是显得非常的短暂，哈密尔顿图的判定问题至今也还没有一个最有效的方法。 本文主要介绍了哈密尔顿图判定的狄拉克定理、奥勒定理、博萨定理、萨瓦达定理。对这些定理进行详细的介绍及实例分析。在上述定理的基础上，引入一个必要性判定条件，以完善对一个图的判定过程。最后对由哈密尔顿图衍生出来的旅行商问题尝试给出一种有效的解法。

3. 实施方案、进度安排及预期效果

本文第一部分讨论了图论的发展历程和课题的研究背景.

第二部分介绍了图的相关概念和基本性质.

第三部分总结了五种哈密尔顿图的判定方法，分别介绍了狄拉克定理、奥勒定理、博萨定理和萨瓦达定理，并补充了一个判定哈密尔顿图的必要性条件.

4. 参考文献

[1] dirac g a. some theorems onabstract graphs[j]. proc london math soc,1952(2):69-81.

[2] o.ore, note on hamiltoniancircuits[j]. amer.math.monthly, 1960,55:67.

[3] o.ore, hamilton connectedgraphs.[j]. math.pures.appl,1963,9(42):21-27