研究这些的原因。
学弟想听，感觉自己在研究冷门的东西，不知道有没有用，可以给点看法吗。
概念
哈密尔顿通路：图 \(G\) 中一条从 \(S\) 到 \(T\) 的路径不重不漏地经过了每个点，那么这条路径称为哈密尔顿通路。
哈密尔顿回路：图 \(G\) 中一条从 \(S\) 到 \(S\) 的路径不重不漏地经过了除 \(S\) 外每个点并且 \(S\) 只经过过两次，那么这条路径称为哈密尔顿回路。
哈密尔顿图：若图 \(G\) 中存在哈密尔顿回路则称 \(G\) 为哈密尔顿图。
求解方法
求解哈密尔顿通路
可以转化成求哈密尔顿回路：
枚举哈密尔顿通路的起点 \(S\) 和终点 \(T\)，在 \(S\) 和 \(T\) 之间加一条边，判断是否存在哈密尔顿通路。
求解哈密尔顿回路
是个NP-完全问题，好像没什么好的求解方法，都是根据一些充分条件/必要条件去构造的鸭子。
必要条件：
\(G\{V,E\}\) 是哈密尔顿图。
那么对于 \(V\) 的任意非空子集 \(V'\) 都有：\(P(G-V') \leq |V'|)\)（其中 \(P(G)\) 表示图 \(G\) 的连通分量个数，\(|V'|\) 表示 \(V'\) 中元素个数，\(G-V'\) 表示从 \(G\) 中删掉 \(V'\) 中的元素后的的到的图）。
证明：
设 \(G\) 中的哈密尔顿回路为 \(C\)，那么 \(P(G-V')\leq P(C-V')\)。因为往 \(C-V'\) 这个图中加边连通分量的数量是不会改变的。
只需要证明 \(P(C-V') \leq |V'|\) 即可。
\(C\) 一定是个环，开始删点，删掉的第一个点使得 \(C\) 不再是一个环，之后每次删点最多增加一个连通分量，也就是最多有 \(|V'|\) 个连通分量。
证毕。
这只是个必要条件，下图满足这个条件但不是哈密尔顿图。
必要条件的推论：
\(G\{V,E\}\) 中有哈密尔顿通路。那么对于 \(V\) 的任意非空子集 \(V'\) 都有：\(P(G-V') \leq |V'| + 1)\)。
证明类似于上面那个证明，不再重复证了。
几个示例：
以下是充分条件
Dirac 定理：
设 G 是有 \(n\) 个点的无向简单图（\(n \geq 3\)），若 \(G\) 中每个节点的度数至少为 \(\left\lceil\frac{n}{2}\right\rceil\)，则 \(G\) 为哈密尔顿图。
Ore 定理：
设 G 是有 \(n\) 个点的无向简单图（\(n \geq 3\)），若 \(G\) 中任意不相邻的两点 \(u,v\) 都满足 \(d(u) + d(v) \geq n\)，则 \(G\) 为哈密尔顿图。
证明鸽了。
\(N(N\geq2)\)阶竞赛图
To Be Continued