哈密顿图的研究与应用.doc

摘要:哈密顿链或路径本身就是简单链或路径，尽管哈密顿链或路径等概念与相应的欧拉链和路径的概念相似，但是我们很难知道一个图或有向图是否存在这样的现象。本论文研究的问题是在完全图中研究的，所以是肯定存在哈密顿回路，而且目的是获得权值最小的哈密顿回路。由于当顶点过多时，计算所有哈密顿回路的路径长短无疑是一个繁杂的过程。我在这篇论文中用C++编写代码以实现哈密顿回路的路径的长度的计算以及比较。最后得出最佳路线。

此外，本文中还提及了哈密顿图，哈密顿通路，哈密顿回路，以及它们的定义，并且了解图存在哈密顿回路的充分条件。

在算法中，我运用邻接矩阵和递归算法去求解该问题，并用冒泡排序对最后路径大小做比较，最后得出最佳路线。

关键词：哈密顿图 C++ 递归算法  lingo

目录

摘要

Abstract

1 绪论-1

1.1图的介绍-1

1.2哈密顿图的由来-1

1.3与哈密顿图有关的故事-1

1.4哈密顿图在实际生活中的应用-2

2 哈密顿图的相关概念，定理及其证明-2

2.1哈密顿图的概念-2

2.2哈密顿的定义-3

2.3图存在哈密顿回路的充分条件-3

3 实际问题中求解权值最小的哈密顿回路-4

3.1问题-4

3.2问题分析-5

3.3算法思路-6

3.4具体实现过程-6

3.5验证算法-10

3.6求解问题-11

4用其他方法求解该题-12

4.1 lingo介绍-12

4.2问题分析-12

4.3约束条件-12

4.4模型建立-13

4.5结果-13

5 结 论-15

6 附录-15

参考文献-17

致谢-18