哈密顿图(Hamiltonian graph) 是指图中存在一条路径,称为 哈密顿路径,这条路径经过每个顶点恰好一次。 如果这条路径的起点和终点是同一个顶点,那么它就构成了 哈密顿回路(或称哈密顿环)。 与欧拉图不同,判断一个图是否是哈密顿图通常没有像欧拉图那样的简单判定标准。而是需要通过具体的算法来寻找哈密顿路径或回路。 因此,哈密顿图问题是 NP 完全问题,意味着没有已知的多项式时间算法来解决这个问题。