图论-哈密尔顿图
定义
注:“哈密尔顿”（Hamiltonian）也可翻译为“哈密顿”，以后者见多。
哈密顿路径
通过图G的每个结点一次，且仅一次的路径，就是哈密顿路径。
哈密顿路径也称作哈密顿链，指在一个图中沿边访问每个顶点恰好一次的路径。哈密顿圈/回路
指包含图的所有顶点的圈。哈密顿圈又叫哈密顿回路。 哈密顿图
存在哈密顿回路（哈密顿圈）的图就是哈密顿图。判断
哈密顿图有很多充分条件，例如：
（1）若图的最小度不小于顶点数的一半，则图是哈密顿图；
（2）若图中每一对不相邻的顶点的度数之和不小于顶点数，则图是哈密顿图。哈密尔顿图与NP问题
一般地，寻找一个图的哈密顿圈问题是 NP 困难的。
寻找一个哈密顿路径是一个典型的NP-完全(NP-complete）问题。
后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP完全的。