有向哈密頓回路問題的一個充分條件及其多項式驗證算法

曹衛(wèi)華，劉富春

(廣東工業(yè)大學 計算機學院，廣東 廣州 510006)

本文研究有向哈密頓回路問題，即檢驗有向圖中是否存在哈密頓回路.哈密頓回路是圖中每個頂點訪問一次且只訪問一次的回路，有向哈密頓回路是有向圖中的哈密頓回路.有向哈密頓回路問題是一個經(jīng)典的非確定性多項式完全問題（non-deterministic polynomial complete problem，NP 完全問題）[1]，一般認為不存在多項式算法.由于所有的非確定性多項式問題（non-deterministic polynomial problem，NP 問題）都可以在多項式時間內(nèi)轉(zhuǎn)化為NP 完全問題，如果存在一個NP 完全問題的多項式算法，則所有的NP 問題都可以在多項式時間內(nèi)求解，這意味著NP 問題是一個多項式問題（polynomial problem，P 問題），即NP=P.現(xiàn)在有很多關(guān)于哈密頓回路的研究，例如，文獻[2]研究隨機有向圖中任意哈密頓回路的填充與計數(shù)，文獻[3]證明隨機有向圖是魯棒哈密頓圖，文獻[4]研究具有指定跳數(shù)的循環(huán)有向圖中的哈密頓回路，文獻[5]給出了哈密頓圖和可跡圖的一些充分條件.但是需要注意的是哈密頓回路問題仍然沒有一個公認的多項式算法.本文提出的多項式算法只是驗證了哈密頓回路問題的一個充分條件，不過這個多項式算法是利用自動機的方法提出的，和前面介紹的那些文獻采用的方法不同.

本文基于自動機理論，將有向圖構(gòu)造為一個由自動機建模的離散事件系統(tǒng)（discrete event system,DES）.離散事件系統(tǒng)是由異步突發(fā)事件驅(qū)動的具有離散狀態(tài)空間的動態(tài)系統(tǒng)[6]，已廣泛應(yīng)用于故障診斷[7-9]、故障預測[10-12]、不透明性[13]、可糾錯性[14]等領(lǐng)域.值得注意的是，在文獻[15-17]中通過同步自動機提出了一些多項式算法.本文中也是通過同步自動機解決有向圖中的哈密頓回路問題.

本文將有向圖建模為一個自動機，在自動機的基礎(chǔ)上定義了一些關(guān)于哈密頓圖的概念，然后提出了一個多項式復雜度的算法，檢驗一個自動機標記的語言的子集是否滿足真子集的一個充分條件.在該算法的基礎(chǔ)上，提出一個多項式復雜度的算法，檢驗一個有向圖是否滿足哈密頓圖的一個充分條件并找出相應(yīng)的哈密頓回路，為了證明這個算法的正確性，給出判斷有向圖是否是哈密頓圖的一個充分條件和判斷有向圖的一個回路是否是哈密頓回路的一個充分條件.

1 離散事件系統(tǒng)

離散事件系統(tǒng)可以建模為確定或者非確定自動機.

定義1[6]一個確定自動機可以定義為G=(X,Σ,δ,x0,Xm)，其中X是狀態(tài)集合，Σ是事件集合，δ：X×Σ →X是狀態(tài)轉(zhuǎn)移函數(shù)，x0是初始狀態(tài)，Xm是標記狀態(tài)集合.

對一個確定自動機G=(X,Σ,δ,x0,Xm)，我們用L(G)表 示G生成的語言，即L(G)={s∈Σ*:(?x∈X)δ(x0,s)=x}，其中 Σ*表示在Σ上 所有有限長度事件系列的集合，包括表示沒有事件的ε，而由G標記的語言定義為Lm(G)={s∈L(G):δ(x0,s)∈Xm}.為了方便起見,狀態(tài)轉(zhuǎn)移函數(shù)通常以遞歸方式擴展為 δ:X×Σ*→X：對任意的s∈Σ*和σ∈Σ，δ(x,ε)=x，δ(x,sσ)=δ(δ(x,s),σ).

對一個集合X,|X|表示X中元素個數(shù).對任意s∈Σ*，pr(s)表示s的前綴集合.對任意x∈X和σ∈Σ，δ(x,σ)！表示δ(x,σ)有 定義，δ(x,σ)/！表示δ(x,σ)沒有定義.

定義2[6]一個非確定自動機可以定義為G=(X,Σ,δ,x0,Xm)，其中X是狀態(tài)集 合，Σ是事件集合，δ:X×Σ →2X是狀態(tài)轉(zhuǎn)移函數(shù)，x0是初始狀態(tài)，Xm是標記狀態(tài)集合.

由非確定自動機G生成的語言定義為L(G)={s∈Σ*:δ(x0,s)≠?}，而由它標記的語言為Lm(G)={s∈L(G):δ(x0,s)∩Xm≠?}.

2 哈密頓圖

定義3一個有向圖可以建模為一個確定自動機G=(X,Σ,δ,x0,Xm,ω)，其中X是狀態(tài)集合，Σ是事件集合，δ:X×Σ →X是狀態(tài)轉(zhuǎn)移函數(shù)，x0是初始狀態(tài)，Xm是 標記狀態(tài)集合，Xm={x0}，ω:X→Σ是一個從狀態(tài)集到事件集的一一映射，即對任意x∈X和σ∈Σ，ω(x)=σ 當且僅當 ω-1(σ)=x，其中 ω-1是 ω的逆函數(shù).對任意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的一條對應(yīng)路徑，并且|s|=n，其中|s|表 示s的長度，也就是s中事件的個數(shù).相同地，|P|表示P的長度，也就是P中事件的個數(shù)，并且|P|=|s|. 對任意 σ∈Σ，σ∈P表 示 σ在P中發(fā)生.

定義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是根據(jù)算法2 構(gòu)造的自動機，對任意s∈L(G)，令P為s在G中 的對應(yīng)路徑，如果s∈Lm(G9)，則P是一條哈密頓回路.

證明因為s∈Lm(G9)，根據(jù)G9的結(jié)構(gòu)可知Lm(G9)?Lm(G2)，所以s∈Lm(G2)，根據(jù)G2的結(jié)構(gòu)可知P滿足定義5 的條件(1)和(2)，根據(jù)G9的結(jié)構(gòu)也可知Lm(G9)∩Lm(G4)=?，所以s?Lm(G4)，根據(jù)G4的結(jié)構(gòu)可知P滿足定義5 的條件(3)，根據(jù)定義5可知P是一條哈密頓回路.證畢.

注 1令|X|和|Σ|分 別為G的狀態(tài)數(shù)和事件數(shù)，則|X|=|Σ|.表1 列出算法2 中涉及的各個自動機的最大狀態(tài)數(shù)和轉(zhuǎn)移數(shù),但需要注意我們有時為了簡便忽略dead 狀態(tài).整個算法的總體復雜度是O(|X|13)，是有向圖G的狀態(tài)數(shù)的多項式.

表1 哈密頓回路問題的復雜度Tab.1 Complexity of Hamilton cycle problem

5 示例

例2一個旅行商需要在A,B,C,D,E 5 個城市推銷商品，這5 個城市之間有的有汽車可以從一個城市到另一個城市,有的沒有，假設(shè)它們之間的汽車路線圖如圖2 所示（用單向箭頭連接2 個城市表示可以從箭頭起點城市坐汽車到箭頭終點城市），旅行商是否能夠乘坐汽車從城市A 出發(fā)，經(jīng)過其他城市一次，并最終回到起點城市A? 我們根據(jù)5 個城市的交通情況可以構(gòu)造有向圖G如圖1 所示，其中狀態(tài)0,1,2,3,4分別表示城市A,B,C,D,E，事件a,b,c,d,e 分別表示坐汽車到城市B,C,D,E,A，根據(jù)算法2 可以構(gòu)造自動機G1，···，G9如 圖3 至圖11 所示.從這些自動機可知 ?(G6,G7)={(111,b),(321,d),(110,c),(222,c)}和?(G6,G7)={(111,b),(110,c)}，所以 ?(G6,G7)≠?(G6,G7)，根據(jù)定理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 出發(fā)，經(jīng)過其他城市一次，并最終回到城市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 總結(jié)

本文基于自動機理論提出有向圖中哈密頓回路問題的一個充分條件及其多項式復雜度的驗證方法，算法的復雜度是O(|X|13)，其中|X|是有向圖的狀態(tài)數(shù)（即頂點數(shù)）.特別地，給出了判斷有向圖是否哈密頓圖的一個充分條件和判斷有向圖中的一條回路是否哈密頓回路的一個充分條件.