哈密顿路径

假设我计划去一个有七个主要城市的国家度假。我乘坐的航空公司并不是每两座城市之间都有直飞航班，我的飞行里程也很高，所以我只想去每个城市一次。给定一个由航班连接的城市对列表，我可以预订一个完成这个壮举的旅行吗?如果我想在同一个城市开始和结束呢?

这个普遍的问题被称为哈密顿路径问题．(在同一位置开始和结束给出哈密顿循环问题)。它与求欧拉路径或者欧拉电路，在上面的例子中，它将计划每次飞行只需要一次的旅行。虽然在图上存在欧拉路径或欧拉电路有简单的充要条件，但寻找哈密顿路径的问题，或确定哈密顿路径是否存在，通常是相当困难的。事实上，确定一个给定图上是否存在哈密顿路径或循环的问题是非完全多项式．

一个哈密顿路径是a (finite)的遍历图它只接触每个顶点一次。如果路径的开始和结束是邻居(即共享一条公共边)，路径可以扩展为一个称为a的循环哈密顿周期．

正十二面体上的哈密顿循环。

考虑一个包含 $64$的顶点 $8 \乘8$网格，每个顶点对应于棋盘上的一个正方形，当且仅当对应的正方形是一个骑士的移动距离时，两个顶点共享一条边。那么图上的哈密顿循环对应于一个封闭的骑士之旅在棋盘上。棋盘图上哈密顿循环的一个例子。

由于确定是否存在哈密顿路径的问题与其他非常困难的问题是等价的，因此，期望这样一条路径的存在有简单的充要条件就太过分了。直观地说，如果相对于顶点的数量有“足够多”的边，那么就应该存在哈密顿路径，因此许多充分条件给出了边的数量的下界。但它们不是必要的:将会有一些具有哈密顿路径或循环的图的例子，它们位于这些条件的边界之外。

一个简单的图是这样一个图:任意两个不同的顶点之间最多只有一条边，并且没有循环(开始和结束于同一顶点的边)。 $_ \广场$

的关闭一个图的 $n$顶点是这样得到的:找到一对顶点之间没有边，使得它们的度数和至少为 $n$．在它们之间画一条边。继续下去，直到找不到更多这样的对为止。(练习:表明无论以何种顺序选择哪些对，该过程都会产生相同的图形。) $_ \广场$

狄拉克,1952:上的一个简单图(任意顶点对之间没有多条边，且没有以同一顶点开始和结束的边) $n$如果每个顶点至少有度，则顶点具有哈密顿循环 $n / 2$．

矿石,1960:一幅关于 $n$具有任意两个不相邻顶点的度数之和属性的顶点 $通用电气\ n$有一个哈密顿循环。

Bondy-Chvatal, 1972:一个图具有哈密顿循环当且仅当它的闭包具有哈密顿循环。 $_ \广场$

注意邦迪- chvatal暗示了Ore，因为Ore定理中图的闭包是完全图 $K_n$每对顶点都由一条边连接，当然，完整的图形 $N \ge 3$顶点有一个哈密顿循环。

Ore意味着狄拉克，因为如果每个顶点都至少有度 $n / 2$，则任意两个不相邻顶点的度之和为 $通用电气\ n$．

这些定理没有一个适用于，例如，循环 $H$在 $6$顶点，每个顶点都有度数 $2$和关闭 $H$= $H$：