哈密顿

问题描述：哈密顿回路是一个经过图中所有顶点的回路，存在哈密顿回路的图称为哈密顿图，判定哈密顿图的问题是著名的NP问题，难以给出有效的算法。 这里考虑另一个问题：如果一个图有哈密顿回路，那么它有多少条不同的哈密顿回路呢？这个问题理论上是和哈密顿图的判定同等困难的，所以也只能对一些特殊情形进行回答，现在考虑一个正则哈密顿图，那么这个正则哈密顿图中是否有至少两条哈密顿回路呢？ 这个问题是今年离散数学期末的一个试题（又被我拿来水文章了2333），原题只询问了是否存在一个满足条件的度数，这里我给了一个更强一点的答案。 问题答案：对于\(d\)是奇数的情形，可以证明任意一个\(d\)正则哈密顿图至少有两条哈密顿回路，而\(d\)是偶数时则很难做判断