正文之前
本次我们要介绍与欧拉图相对应的哈密顿图的有关内容：
- 哈密顿回路(Hamiltonian cycle)
- 哈密顿图(Hamiltonian Path)
- 旅行推销员问题简介(Travelling salesman problem)
正文
哈密顿回路
1. 定义：
在一个回路中，除了经过初始结点两次以外，恰好经过每个结点一次，则称此回路为哈密顿回路，哈密顿回路中每个结点都为偶结点
2. 证明
- 由于现在还没有判断一个图中是否存在哈密顿回路的定理，所以我们只能根据自己的经验来判断，下文分别以一个简单的图和一个复杂的图来证明
简单的图
在上图中，共有5个结点，可想而知，如果存在哈密顿回路，就必须有5条边，且每个结点都为偶结点。
所以我们尝试删去某一些边来达到目的，v1和v3为奇结点，我们从此下手，分别去掉一条与v1和v3相关联的边，那么只剩下4条边，不符合条件，所以此图中不存在哈密顿回路。
复杂的图
在上图中，假设有一个哈密顿回路，由于v1和v3是度数为2的结点，所以v1和v3所关联的边(v1,v8)、(v1,v2)、(v2,v3)、(v3,v4)一定在回路中。
结点v2，v7，v5度数不为2，所以我们删去边(v2,v7)和(v2,v5)
结点v5，v6，v7的度数为2，所以现在形成了一个回路(v1,v2,v3,v4,v5,v6,v7,v8)
图中还存在结点v9，将v9加入回路中就势必会增加某些点的度数，所以使得某些点的度数大于2
通过上述几点，可得出上图中不存在哈密顿回路
哈密顿图
定义：在图G中，若含有哈密顿回路，则称图G为哈密顿图
- 上图中，存在哈密顿回路(v1,v2,v5,v3,v4,v1)，所以上图可称为哈密顿图
旅行推销员问题简介
问题内容
给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。 ——Wikipedia
这个问题是基于寻找哈密顿回路的基础上，只不过所对应的图是加权无向图，在接下来。
这一篇的内容就到此为止了，接下来会有一篇文章专门介绍旅行推销员问题问题，谢谢大家！
