有向哈密顿回路问题的一个充分条件及其多项式验证算法

曹卫华，刘富春

(广东工业大学 计算机学院，广东 广州 510006)

本文研究有向哈密顿回路问题，即检验有向图中是否存在哈密顿回路.哈密顿回路是图中每个顶点访问一次且只访问一次的回路，有向哈密顿回路是有向图中的哈密顿回路.有向哈密顿回路问题是一个经典的非确定性多项式完全问题（non-deterministic polynomial complete problem，NP 完全问题）[1]，一般认为不存在多项式算法.由于所有的非确定性多项式问题（non-deterministic polynomial problem，NP 问题）都可以在多项式时间内转化为NP 完全问题，如果存在一个NP 完全问题的多项式算法，则所有的NP 问题都可以在多项式时间内求解，这意味着NP 问题是一个多项式问题（polynomial problem，P 问题），即NP=P.现在有很多关于哈密顿回路的研究，例如，文献[2]研究随机有向图中任意哈密顿回路的填充与计数，文献[3]证明随机有向图是鲁棒哈密顿图，文献[4]研究具有指定跳数的循环有向图中的哈密顿回路，文献[5]给出了哈密顿图和可迹图的一些充分条件.但是需要注意的是哈密顿回路问题仍然没有一个公认的多项式算法.本文提出的多项式算法只是验证了哈密顿回路问题的一个充分条件，不过这个多项式算法是利用自动机的方法提出的，和前面介绍的那些文献采用的方法不同.

本文基于自动机理论，将有向图构造为一个由自动机建模的离散事件系统（discrete event system,DES）.离散事件系统是由异步突发事件驱动的具有离散状态空间的动态系统[6]，已广泛应用于故障诊断[7-9]、故障预测[10-12]、不透明性[13]、可纠错性[14]等领域.值得注意的是，在文献[15-17]中通过同步自动机提出了一些多项式算法.本文中也是通过同步自动机解决有向图中的哈密顿回路问题.

本文将有向图建模为一个自动机，在自动机的基础上定义了一些关于哈密顿图的概念，然后提出了一个多项式复杂度的算法，检验一个自动机标记的语言的子集是否满足真子集的一个充分条件.在该算法的基础上，提出一个多项式复杂度的算法，检验一个有向图是否满足哈密顿图的一个充分条件并找出相应的哈密顿回路，为了证明这个算法的正确性，给出判断有向图是否是哈密顿图的一个充分条件和判断有向图的一个回路是否是哈密顿回路的一个充分条件.

1 离散事件系统

离散事件系统可以建模为确定或者非确定自动机.

定义1[6]一个确定自动机可以定义为G=(X,Σ,δ,x0,Xm)，其中X是状态集合，Σ是事件集合，δ：X×Σ →X是状态转移函数，x0是初始状态，Xm是标记状态集合.

对一个确定自动机G=(X,Σ,δ,x0,Xm)，我们用L(G)表 示G生成的语言，即L(G)={s∈Σ*:(∃x∈X)δ(x0,s)=x}，其中 Σ*表示在Σ上 所有有限长度事件系列的集合，包括表示没有事件的ε，而由G标记的语言定义为Lm(G)={s∈L(G):δ(x0,s)∈Xm}.为了方便起见,状态转移函数通常以递归方式扩展为 δ:X×Σ*→X：对任意的s∈Σ*和σ∈Σ，δ(x,ε)=x，δ(x,sσ)=δ(δ(x,s),σ).

对一个集合X,|X|表示X中元素个数.对任意s∈Σ*，pr(s)表示s的前缀集合.对任意x∈X和σ∈Σ，δ(x,σ)！表示δ(x,σ)有 定义，δ(x,σ)/！表示δ(x,σ)没有定义.

定义2[6]一个非确定自动机可以定义为G=(X,Σ,δ,x0,Xm)，其中X是状态集 合，Σ是事件集合，δ:X×Σ →2X是状态转移函数，x0是初始状态，Xm是标记状态集合.

由非确定自动机G生成的语言定义为L(G)={s∈Σ*:δ(x0,s)≠∅}，而由它标记的语言为Lm(G)={s∈L(G):δ(x0,s)∩Xm≠∅}.

2 哈密顿图

定义3一个有向图可以建模为一个确定自动机G=(X,Σ,δ,x0,Xm,ω)，其中X是状态集合，Σ是事件集合，δ:X×Σ →X是状态转移函数，x0是初始状态，Xm是 标记状态集合，Xm={x0}，ω:X→Σ是一个从状态集到事件集的一一映射，即对任意x∈X和σ∈Σ，ω(x)=σ 当且仅当 ω-1(σ)=x，其中 ω-1是 ω的逆函数.对任意x∈X和 σ∈Σ，如果δ(x,σ)!则δ(x,σ)=ω-1(σ).

定义4在自动机G=(X,Σ,δ,x0,Xm)中 的一条路径P可以用P=(x0,σ1,x1,σ2,···,σn,xn)表示，其中x0,x1,···,xn∈X，σ1,σ2,···,σn∈Σ，n∈N，并且对任意i∈{0,1,···,n-1}，δ(xi,σi+1)=xi+1.

对自动机G中的一条路径P=(x0,σ1,x1,σ2,···,σn,xn)，s=σ1σ2···σn被称为P的轨迹，P为s的一条对应路径，并且|s|=n，其中|s|表 示s的长度，也就是s中事件的个数.相同地，|P|表示P的长度，也就是P中事件的个数，并且|P|=|s|. 对任意 σ∈Σ，σ∈P表 示 σ在P中发生.

定义5在有向图G=(X,Σ,δ,x0,Xm,ω)中的一条路径P=(x0,σ1,x1,σ2,···,σn,xn)被称为一条哈密顿回路，如果它满足如下条件：

(1)|P|=|X|；

(2)x0=xn；

(3)对任意i,j∈{1,2,···,n}，如果i≠j则σi≠σj.

定义6对一个有向图G=(X,Σ,δ,x0,Xm,ω)，如果图中存在哈密顿回路则称为哈密顿图.

例1考虑如图1 所示的有向图G，其中X={0,1,2,3,4}，Σ={a,b,c,d,e}，x0=0，Xm={0}，ω(0)=e，ω(1)=a，ω(2)=b，ω(3)=c，ω(4)=d.在有向图G中存在2 个哈密顿回路，它们是

图1 例1 中的有向图Fig.1 Digraph in example 1

3 真子集验证的一个充分方法

4 有向图中识别哈密顿回路的一个充分方法

定理 3令G=(X,Σ,δ,x0,Xm,ω)为一有向图，G1，···，G9是根据算法2 构造的自动机，对任意s∈L(G)，令P为s在G中 的对应路径，如果s∈Lm(G9)，则P是一条哈密顿回路.

证明因为s∈Lm(G9)，根据G9的结构可知Lm(G9)⊆Lm(G2)，所以s∈Lm(G2)，根据G2的结构可知P满足定义5 的条件(1)和(2)，根据G9的结构也可知Lm(G9)∩Lm(G4)=∅，所以s∉Lm(G4)，根据G4的结构可知P满足定义5 的条件(3)，根据定义5可知P是一条哈密顿回路.证毕.

注 1令|X|和|Σ|分 别为G的状态数和事件数，则|X|=|Σ|.表1 列出算法2 中涉及的各个自动机的最大状态数和转移数,但需要注意我们有时为了简便忽略dead 状态.整个算法的总体复杂度是O(|X|13)，是有向图G的状态数的多项式.

表1 哈密顿回路问题的复杂度Tab.1 Complexity of Hamilton cycle problem

5 示例

例2一个旅行商需要在A,B,C,D,E 5 个城市推销商品，这5 个城市之间有的有汽车可以从一个城市到另一个城市,有的没有，假设它们之间的汽车路线图如图2 所示（用单向箭头连接2 个城市表示可以从箭头起点城市坐汽车到箭头终点城市），旅行商是否能够乘坐汽车从城市A 出发，经过其他城市一次，并最终回到起点城市A? 我们根据5 个城市的交通情况可以构造有向图G如图1 所示，其中状态0,1,2,3,4分别表示城市A,B,C,D,E，事件a,b,c,d,e 分别表示坐汽车到城市B,C,D,E,A，根据算法2 可以构造自动机G1，···，G9如 图3 至图11 所示.从这些自动机可知 ℑ(G6,G7)={(111,b),(321,d),(110,c),(222,c)}和ℜ(G6,G7)={(111,b),(110,c)}，所以 ℑ(G6,G7)≠ℜ(G6,G7)，根据定理2 可知G是 哈密顿图，因为Lm(G9)={acdbe,abcde}，所以G中 至少存在两条哈密顿回路(0,a,1,c,3,d,4,b,2,e,0)和(0,a,1,b,2,c,3,d,4,e,0).这意味着旅行商有至少两条路线可以从城市A 出发，经过其他城市一次，并最终回到城市A，这两条路线就是ABDECA 和ABCDEA.

图2 例2 中的汽车路线图Fig.2 Car route map in example 2

图3 例2 中的G1Fig.3 G 1 in example 2

图4 例2 中的G2Fig.4 G 2 in example 2

图5 例2 中的G3Fig.5 G 3 in example 2

图6 例2 中的G4Fig.6 G 4 in example 2

图7 例2 中的G5Fig.7 G 5 in example 2

图8 例2 中的G6Fig.8 G 6 in example 2

图9 例2 中的G7Fig.9 G 7 in example 2

图10 例2 中的G8Fig.10 G 8 in example 2

图11 例2 中的G9Fig.11 G 9 in example 2

6 总结

本文基于自动机理论提出有向图中哈密顿回路问题的一个充分条件及其多项式复杂度的验证方法，算法的复杂度是O(|X|13)，其中|X|是有向图的状态数（即顶点数）.特别地，给出了判断有向图是否哈密顿图的一个充分条件和判断有向图中的一条回路是否哈密顿回路的一个充分条件.