正则哈密顿图是否有第二条哈密顿回路

问题描述:哈密顿回路是一个经过图中所有顶点的回路,存在哈密顿回路的图称为哈密顿图,判定哈密顿图的问题是著名的NP问题,难以给出有效的算法。

这里考虑另一个问题:如果一个图有哈密顿回路,那么它有多少条不同的哈密顿回路呢?这个问题理论上是和哈密顿图的判定同等困难的,所以也只能对一些特殊情形进行回答,现在考虑一个正则哈密顿图,那么这个正则哈密顿图中是否有至少两条哈密顿回路呢?

这个问题是今年离散数学期末的一个试题(又被我拿来水文章了2333),原题只询问了是否存在一个满足条件的度数,这里我给了一个更强一点的答案。

问题答案:对于\(d\)是奇数的情形,可以证明任意一个\(d\)正则哈密顿图至少有两条哈密顿回路,而\(d\)是偶数时则很难做判断。

Solution

设\(G\)是哈密顿图,构造一个新的图\(H\),\(H\)中的顶点是\(G\)中从\(v_1\)出发的所有哈密顿路,由于\(G\)中有哈密顿回路,所以必然存在哈密顿路,即\(H\)非空。

设\(P=\{v_1,v_2,\cdots,v_n\}\)和\(Q=\{v_1,u_2,\cdots,u_n\}\)是\(G\)中两条从\(v_1\)出发的哈密顿路,如果存在一个\(k\),使得对于所有的\(2\leq i\leq k\)有\(v_i=u_i\)且对于所有的\(k+1\leq j\leq n\)有\(v_i=u_{n+k+1-j}\),则令\(P\)和\(Q\)在图\(H\)中有边相连。

考虑\(H\)中的一个顶点\(P=\{v_1,v_2,\cdots,v_n\}\),对于每个\(2\leq i\leq n-2\),如果\(v_i\)和\(v_n\)在\(G\)中有边相连,我们都可以通过先走这条边到\(v_n\)、再沿着哈密顿路\(P\)倒着走回\(v_{i+1}\)来得到一个新的哈密顿路\(Q=\{v_1,v_2\cdots,v_i,v_n,v_{n-1},\cdots,v_{i+1}\}\),而根据我们的构造\(P\)和\(Q\)在\(H\)中是相邻的。

如果\(v_1\)和\(v_n\)之间没有边,注意到哈密顿路已经包含了原图中的所有顶点,所以依此法我们可以得知在\(H\)中\(P\)的度数\(deg(P)=deg(v_n)-1\)(因为还要去掉\(v_{n-1}\)和\(v_n\)之间的边),而如果\(v_1\)和\(v_n\)之间有边,则有\(deg(P)=deg(v_n)-2\),且\(v_1\)和\(v_n\)有边的情形下,哈密顿路\(P\)恰好能对应\(G\)中一条哈密顿回路。

现在设题目中的\(d\)是奇数,则对于图\(H\)中的顶点\(P=\{v_1,v_2,\cdots,v_n\}\),如果\(v_1\)和\(v_n\)之间没有边,则\(deg(P)=deg(v_n)-1\)是偶数,如果\(v_1\)和\(v_n\)有边即\(P\)对应哈密顿回路,则\(deg(P)=deg(v_n)-2\)是奇数,根据握手定理,一个图中度数为奇数的点只能是偶数个,而由于\(G\)是哈密顿图,所以\(H\)中至少存在一个顶点\(P\)对应哈密顿回路,这个顶点的度数是奇数,所以\(H\)中至少有两个顶点度数是奇数,即至少有两条哈密顿路对应哈密顿回路。

综上所述,当\(d\)是奇数时,任意一个\(d\)正则哈密顿图至少有两条哈密顿回路。

当\(d\)不是奇数时,问题变得困难起来,事实上能够证明当\(d\)足够大时都满足\(d\)正则哈密顿图至少有两条哈密顿回路,不过具体的情况里目前只能证明\(d=22\)的偶数情形,这方面最有名的猜想是这个结论对\(d=4\)能够成立,但证明举步维艰。说到底对于哈密顿图,各种问题始终困难,只期待能有朝一日能有更好的工具去理解它。

发表评论

电子邮件地址不会被公开。 必填项已用*标注