王 卓 王成紅

圖的同構(gòu)判定在化學(xué)分析、計算機科學(xué)、人工智能以及智能決策與控制等領(lǐng)域有著廣泛的應(yīng)用[1-3].上世紀前半葉,與圖同構(gòu)相關(guān)的問題主要圍繞圖的鄰接矩陣及其性質(zhì)、鄰接矩陣(拉普拉斯矩陣)特征值及其應(yīng)用展開[4],取得了若干重要的理論成果和一大批應(yīng)用成果.

上世紀70 年代,Karp、Garey 和Johnson 等認為圖的同構(gòu)判定問題是少數(shù)幾個既不能歸類為P,也不能歸類為NP的問題[1,3].自此之后,該問題成為理論計算機領(lǐng)域的公開問題并受到廣泛重視.

1982 年,Luks 使用有限群等數(shù)學(xué)工具給出了一個當時最好的兩圖同構(gòu)判定算法,該算法的時間復(fù)雜度是(n為圖的頂點數(shù))[5-6].此后40 年來,圖的同構(gòu)判定問題引起了眾多學(xué)者的關(guān)注,幾百篇這方面的文章得以在不同的學(xué)術(shù)期刊上發(fā)表[1].2015 年,Babai 在Luks 算法的基礎(chǔ)上,利用群作用下軌道間的局部關(guān)系和群的正則分解技術(shù),給出了兩圖同構(gòu)判定問題的擬多項式算法,該算法的時間復(fù)雜度是 e xp((logn)O(1))[5].上述算法的目的在于給出同構(gòu)判定問題的復(fù)雜度上界,并不能直接用于具體圖的同構(gòu)判定[5].Babai 的工作雖然是一個重要進展,但圖的同構(gòu)判定問題是否在多項式時間內(nèi)可解仍然懸而未決[1].

圖的同構(gòu)判定問題的另一研究路徑是設(shè)計可執(zhí)行的具體判定算法,大致可以分為傳統(tǒng)判定算法和非傳統(tǒng)判定算法兩種情況.傳統(tǒng)判定算法有兩類:1)針對一些特殊圖(如樹和極大外平面圖等)[7-8]的同構(gòu)判定算法(如Ullman 算法、Schmidt 算法、Falkenhainer 算法和Messmer 算法等)[9].這些算法主要使用“搜索、標號和回溯”技術(shù)且被證明具有多項式時間復(fù)雜度;2)針對一般簡單圖的判定算法,如一些放在因特網(wǎng)上用于測試兩圖是否同構(gòu)的程序(如Nauty、Saucy、Bliss、Conauto 和Traces等)[3,5].這些程序運行速度很快,但算法的時間復(fù)雜度分析和正確性證明卻沒有公開報道.非傳統(tǒng)判定算法也有兩類: 1)基于遺傳算法、神經(jīng)網(wǎng)絡(luò)和粒子群算法等的智能同構(gòu)判定算法.這些算法將圖的同構(gòu)判定問題轉(zhuǎn)化為一類優(yōu)化求解問題,但其判定結(jié)果并不完全可靠.2)基于生物(DNA)計算[9]和量子計算的判定算法.這類算法雖然高效,但實現(xiàn)比較困難而且也不能回答圖的同構(gòu)判定是P還是NP問題.

本文的主要思路和貢獻是: 1)給出了矩陣同構(gòu)變換和簡單無向圖距離矩陣的定義,將基于鄰接矩陣的同構(gòu)判定條件推廣到簡單無向圖距離矩陣.2)針對簡單無向連通圖的同構(gòu)判定問題,給出了基于距離矩陣特征多項式的同構(gòu)判定條件.因用數(shù)值方法求解特征多項式會產(chǎn)生計算誤差,故該判定條件僅適合中小規(guī)模簡單無向連通圖的同構(gòu)判定[10-11].3)為避免計算誤差對判定結(jié)果的影響,給出了簡單無向連通圖距離矩陣列和向量與圖的距離譜的定義,并進而給出了基于距離矩陣的秩與列和向量的同構(gòu)判定條件.該判定條件不產(chǎn)生計算誤差,因而適合大規(guī)模簡單無向連通圖的同構(gòu)判定.上述兩個判定條件均是充要條件且均具有多項式時間復(fù)雜度,將這些條件用于簡單無向不連通圖的各個連通子圖,就可解決簡單無向不連通圖的同構(gòu)判定問題.

1 相關(guān)概念和預(yù)備知識

1.1 相關(guān)概念

若僅考慮頂點間的鄰接關(guān)系和拓撲結(jié)構(gòu),則圖可視為由若干個頂點和若干條邊連接成的網(wǎng)絡(luò).

定義 1[4,12-13]. 圖G是一個二元組,記作G=〈V,E〉,其中:

1)V={v1,v2,···,vn||V|=n,n≥1},vi∈V稱為G的頂點,V稱為G的頂點集;

2)E={e1,e2,···,em||E|=m,m≥0},ej∈E稱為G的邊,E稱為G的邊集;

3)?ej∈E:ej為無向邊時,稱G為無向圖,ej為有向邊時,稱G為有向圖;

4)連接同一個頂點的邊稱為自環(huán),兩個頂點間的多條無向邊或多條方向相同的有向邊稱為重邊.無自環(huán)和重邊的圖稱為簡單圖,否則稱為復(fù)雜圖.

本文分析和討論的圖均是頂點和邊為有限數(shù)的無向圖.

定義 2[12-14]. 設(shè)G=〈V,E〉 為無向圖,V={v1,v2,···,vn}.若頂點vi和vj(1≤i,j ≤n)之間有k(k≥0 為非負整數(shù))條邊,令aij=k;稱由元素aij構(gòu)成的矩陣A(aij)∈Rn×n為無向圖G的鄰接矩陣.

在定義2 中,k=0 表示無邊,aii=k表示頂點vi有k個自環(huán).如此,定義2 既適合簡單無向圖也適合復(fù)雜無向圖.

定義 3[4,12-14]. 設(shè)G=〈V,E〉 為無向圖,V={v1,v2,···,vn}(n≥2),E={e1,e2,···,em} (m≥1).1)G中頂點與邊的交替序列W=v1e1v2e2···vkekvk+1(k ≤n-1)稱為G的鏈,各邊互異的鏈稱為跡,各頂點互異的鏈稱為路;當W是路時,W中的邊數(shù)k稱為W的長度,記作k=|W|.2)設(shè)vi和vj是V中的任意兩個頂點,當vi和vj之間有s條路Wp(1≤p ≤s)時,稱d(vi,vj)=min{kp=|Wp||1≤p ≤s} 為vi和vj之間的距離;若vi和vj之間無路(G不連通),約定d(vi,vj)=∞.3)稱d(G)=max{d(u,v)|u,v∈V} 為G的直徑.

圖的同構(gòu)問題可以這樣表述: 給定兩個圖,當忽略圖中頂點的標號、頂點間的相對位置、邊的長短和曲直信息時,問這兩個圖是否具有相同的結(jié)構(gòu)? 現(xiàn)有文獻中關(guān)于簡單圖的同構(gòu)定義已有多個[4,13-14],這些定義雖然表述略有不同但彼此等價.下面,我們給出一個既適合簡單圖又適合復(fù)雜圖的同構(gòu)定義.

定義 4[4].設(shè)G1=〈V1,E1〉 和G2=〈V2,E2〉 是兩個無向(有向)圖.若存在一個從V1到V2的一一映射g:?vi,vj∈V1,vi至vj有k條無向(有向)邊,當且僅當g(vi),g(vj)∈V2,且g(vi)至g(vj)也有k條無向(有向)邊,則稱G1和G2同構(gòu),記作G1～=G2.

1.2 預(yù)備知識

定義 5[15]. 設(shè)In∈Rn×n為單位矩陣,交換In的第i行與第j行(或第i列與第j列)所得的矩陣P(i,j)稱為對換矩陣,對換矩陣的乘積稱為置換矩陣.

引理 1[15]. 對換矩陣和置換矩陣具有如下性質(zhì):

由引理1 中的性質(zhì)2)和性質(zhì)6)可知,對換矩陣和In也是置換矩陣.

定義 6.設(shè)A,B ∈Rn×n,??Rn×n為全體n階置換矩陣的集合.若存在置換矩陣Q∈?,使得A=QTBQ,則稱A與B同構(gòu),記作A～=B;此外,稱QTBQ是對B的同構(gòu)變換.

任給一個無向(有向)圖G=〈V,E〉,|V|=n≥2.對V中每個頂點指定一個1～n的標號,可以得到一個標號向量=[σi1σi2··· σin]∈R1×n({σi1,···,σin}是 {1,2,···,n} 的一個置換)和一個鄰接矩陣A∈Rn×n.設(shè)π1和π2是V的任意兩個標號向量,A與B分別是圖G相應(yīng)于π1和π2的鄰接矩陣.當π1=π2時,A=B;當π1≠π2時,A≠B(或A=B).

設(shè)π1≠π2.逐次不重復(fù)地對調(diào)π1中兩個分量的位置(對換兩個頂點的標號),經(jīng)有限次對調(diào)就可將π1變成π2,同時將A變成B.對調(diào)頂點vi與vj的標號,π1將變?yōu)镻(i,j)π1(P(i,j)為對換矩陣),A將變?yōu)镻(i,j)APT(i,j).其中,P(i,j)APT(i,j)是對調(diào)A的第i行和第j行之后,再對調(diào)第i列和第j列所得的矩陣.設(shè)頂點標號經(jīng)m(m≥1)次對調(diào)之后π1變成π2,并且第s(1≤s ≤m)次對調(diào)所對應(yīng)的對換矩陣為Ps,則π2=PmPm-1···P1π1=Qπ1(Q=.由引理1 可知,Q∈? 為置換矩陣.如此,π1=QTπ2,A=QTBQ.

由上述分析和定義6 可知: 任給無向圖G,若A和B是G的兩個鄰接矩陣,則存在置換矩陣Q ∈?,使得A=QTBQ,即同一圖的任意兩個鄰接矩陣彼此同構(gòu);鄰接矩陣的行列同時互換是同構(gòu)變換,鄰接矩陣的同構(gòu)變換還是鄰接矩陣.

引理 2[12]. 設(shè)G1=〈V1,E1〉 和G2= 〈V2,E2〉 是兩個圖,|V1|=|V2|=n,A與B分別是G1和G2的鄰接矩陣.則G1～=G2的充要條件是存在n階置換矩陣Q∈?,使得A=QTBQ,或A=Q-1BQ.

證明.設(shè)存在n階置換矩陣Q∈?,使得A=QTBQ.由定義6 可知,QTBQ是對B的同構(gòu)變換.因鄰接矩陣的同構(gòu)變換還是同一圖的鄰接矩陣,故A=QTBQ是G2的鄰接矩陣.如此,G1和G2有相同的鄰接矩陣A,即G1和G2是同一個圖;換言之,G1～=G2.

設(shè)G1～=G2.當G1和G2同構(gòu)時,B可經(jīng)有限次行列同時互換轉(zhuǎn)化為A,即存在n階置換矩陣Q ∈?,使得A=QTBQ.

引理2 表明,兩個圖同構(gòu)當且僅當該兩圖的鄰接矩陣同構(gòu);若兩個圖有相同的鄰接矩陣,則這兩個圖同構(gòu).容易證明,引理2 中的Q是唯一的.

2 簡單無向圖的同構(gòu)判定方法

由定義3 可知,復(fù)雜無向圖中的自環(huán)和多重邊中的重邊對頂點間的距離沒有影響.為區(qū)分起見,本節(jié)僅討論簡單無向圖.

定義 7.設(shè)G=〈V,E〉 是簡單無向圖,V={v1,v2,···,vn},dij=d(vi,vj)表示頂點vi和vj(1≤i,j ≤n)之間的距離: 當i=j時,令dii=0 ;當i≠j且d(vi,vj)=k(d(vi,vj)=∞)時,令dij=k(dij=∞),其中k≥1 為正整數(shù);稱由元素dij構(gòu)成的矩陣D(dij)∈Rn×n為簡單無向圖G的頂點距離矩陣,簡稱G的距離矩陣.

因i≠j時,d(vi,vj)=d(vj,vi),所以dij=dji,簡單無向圖G的距離矩陣D是對稱矩陣.與鄰接矩陣一樣,頂點標號不同時,G的距離矩陣通常也互不相同.

定理 1.設(shè)G1=〈V1,E1〉 和G2=〈V2,E2〉 是兩個簡單無向圖,|V1|=|V2|=n≥2,D1與D2分別是G1和G2的距離矩陣;則G1～=G2的充要條件是存在n階置換矩陣Q∈?,使得D1=QTD2Q,或D1=Q-1D2Q.

證明.設(shè)存在n階置換矩陣Q∈?,使得D1=QTD2Q.因Q∈?,由定義6 可知,QTD2Q是對D2的同構(gòu)變換.因QTD2Q只改變D2行與列的排列而不改變D2的元素,故QTD2Q=D1也是G2的距離矩陣.同理,D2=QD1QT也是G1的距離矩陣.如此,D1和D2既是G1的距離矩陣也是G2的距離矩陣.設(shè)G1的頂點標號向量為π1,相應(yīng)的距離矩陣和鄰接矩陣分別是D1和A1;G2的頂點標號向量為π2,相應(yīng)的距離矩陣和鄰接矩陣分別是D2和A2.因D1和D2均是G1的距離矩陣,類似第1.2 節(jié)的分析可得,當D1=QTD2Q時,π1=QTπ2,A1=QTA2Q.如此,若存在Q∈?,使得D1=QTD2Q,則A1=QTA2Q.由引理2 可知,G1～=G2.

設(shè)G1～=G2.由引理2 可知,存在Q∈?,使得A1=QTA2Q.同上分析可得,當A1=QTA2Q時,π1=QTπ2,D1=QTD2Q.這表明,若G1～=G2,則存在Q∈?,使得D1=QTD2Q,或D1=Q-1D2Q.

定理1 表明,兩個簡單無向圖同構(gòu)當且僅當這兩個圖的距離矩陣同構(gòu);距離矩陣的同構(gòu)變換還是距離矩陣;距離矩陣的同構(gòu)性與鄰接矩陣的同構(gòu)性保持一致.

不難理解,定理1 即是引理2 在簡單無向圖距離矩陣上的推廣.

設(shè)G=〈V,E〉 是簡單無向連通圖,|V|=n≥2,D(dij)∈Rn×n是G的距離矩陣.由定義7 可知,D是對角線元素均為零而其他元素全為正整數(shù)的對稱矩陣.由定義3 和定義7 可知,G的直徑可由D的元素求取,即d(G)=max{dij|1≤i,j ≤n}.此外,由D的元素還可求出G中各頂點的離心率和G的半徑[4,13].

定義 9.設(shè)T ?Rn×n(n≥2)表示全體n階正交矩陣的集合;?-={-S|S ∈?} 表示全體n階負置換矩陣的集合;Φ=?∪?-表示全體n階置換矩陣和全體n階負置換矩陣的并集;Θ=T-Φ 表示T中除 Φ 之外全體n階正交矩陣的集合.

由定義9 和正交矩陣的性質(zhì)可知: Θ∩Φ=?(?為空集),Θ∪Φ=T;?Q1,Q2∈Φ,Q1Q2∈Φ;?Q ∈Φ,?P ∈Θ,QP,PQ ∈Θ ;?P ∈Θ,?E ∈Φ,?Q ∈T且Q≠EPT,QP,PQ ∈Θ.

引理 3[15]. 設(shè)A∈Rn×n,則A為正交矩陣的充要條件是存在正交矩陣P∈T,使得

其中,Is與It分別是s階和t階單位矩陣,

s+t+2k=n,θj∈R(1≤j ≤k)為實數(shù).

由正交矩陣的定義可知,Pθ和Hθ均是正交矩陣.

定理 2.設(shè)A(aij)∈Rn×n(n≥2)是對角線元素均為1 而其他元素均為正整數(shù)的對稱矩陣,則?P ∈Θ,PTAP不是正整數(shù)矩陣(PTAP的元素不全是正整數(shù)).

其中,a1,a2,a3為正整數(shù),δ=±1,θ∈R.如此,

其中,α1(θ)=a1cosθ-a2sinθ,α2(θ)=a1sinθ+a2cosθ,α3(θ)=a3sin 2θ.當δ=1 且θ≠±2lπ(l=0,1,2,···),或δ=-1 且θ≠±hπ(h為奇數(shù))時,P ∈Θ,PTAP不是正整數(shù)矩陣.類似n=2 時的分析可得,對一切3 階正交矩陣Q∈Θ,QTAQ不是正整數(shù)矩陣.

其中,A11∈Rs×s,A22∈Rt×t,A33∈R2k×2k均是對角線元素為1 而其他元素為正整數(shù)的分塊對稱矩陣,A12,A13,A23均是分塊正整數(shù)矩陣;Pθ和Hθ為形如引理3 中的矩陣,s+t+2k=n,θj∈R(1≤j ≤k)為實數(shù).如此,

引理4[15]. 設(shè)A,B ∈Rn×n為對稱矩陣,則det(λIn-A)=det(λIn-B)的充要條件是存在正交矩陣P∈T,使得A=PTBP=P-1BP.

基于定理1、定理2 和引理4,下面給出兩個簡單無向連通圖是否同構(gòu)的判定條件.

定理 3.設(shè)G1=〈V1,E1〉 和G2=〈V2,E2〉 是兩個簡單無向連通圖,|V1|=|V2|=n≥2,D1與D2分別是G1和G2的距離矩陣,則G1～=G2的充要條件是 det(λIn-D1)=det(λIn-D2).

證明.設(shè) det(λIn-D1)=det(λIn-D2).因D1和D2均是實對稱矩陣,由引理4 可知,當det(λIn-D1)=det(λIn-D2)時,存在n階正交矩陣P∈T,使得D1=PTD2P.下面證明,?n≥2,P∈? (或P=-S,S∈?).假設(shè)存在一個P∈Θ,使得D1=PTD2P,則In+D1=PTP+PTD2P=PT(In+D2)P.因In+D1和In+D2均是正整數(shù)矩陣,故PT(In+D2)P也是正整數(shù)矩陣,這與定理2 的結(jié)論矛盾.如此,P∈/Θ.因 Θ∩Φ=?,Θ∪Φ=T,故當P∈T且P∈/Θ 時,必有P ∈Φ.換言之,?n≥2,當D1和D2均是距離矩陣且det(λIn-D1)=det(λIn-D2)時,一定存在P∈? (或P=-S,S∈?),使得D1=PTD2P.由定理1 可知,G1～=G2.

設(shè)G1～=G2. 由定理1 可知,當G1～=G2時,存在n階置換矩陣P∈?,使得D1=PTD2P.因r(D)和do(D)均是矩陣同構(gòu)變換下的不變量,故當D1=PTD2P時,r(D1)=r(D2)且do(D1)=do(D2).

因距離矩陣D是非負整數(shù)矩陣,故求解r(D)和do(D)均不會產(chǎn)生計算誤差.如此,定理5 為無誤差判定條件.此外,因求解 det(λIn-D)比求解r(D)和do(D)困難得多,故定理5 比定理3 在計算便利性方面更具優(yōu)勢.上述兩個優(yōu)點表明,定理5更適合大規(guī)模簡單無向連通圖的同構(gòu)判定.

有了推論4,兩個無向樹的同構(gòu)判定問題就變?yōu)橐粋€簡單的算術(shù)問題.

不難理解,將定理3 特別是定理5 用于簡單無向不連通圖的各個連通子圖或?qū)⑼普? 用于無向森林的各個無向樹,就可解決任意簡單無向不連通圖的同構(gòu)判定問題.

例 1.試判定下列各對應(yīng)圖(如圖1 所示)是否同構(gòu).

圖1 例1 各對應(yīng)圖Fig.1 Corresponding figures of Example 1

解.1)G1和G2均是無向樹(毛蟲形[4,16,19]),按圖中頂點標號,經(jīng)計算可得G1和G2的距離矩陣分別為

由D1和D2可得,

因ds(D1)≠ds(D2),由推論3 或推論4 均可判定G1和G2不同構(gòu).

此外,G1和G2的鄰接矩陣同譜,即?(G1,λ)=?(G2,λ)=λ10-9λ8+26λ6-27λ4+8λ2.若將鄰接矩陣特征多項式相等作為判據(jù)來判定G1和G2是否同構(gòu)[16,19],就會得出錯誤的結(jié)果.

2)G3和G4均是3 正則無向圖(Wagner 圖[1,20]).按圖中頂點標號,經(jīng)計算可得G3和G4的距離矩陣分別為

另一方面,因r(D3)=r(D4)=8;do(D3)=[1111111111111111],do(D4)=[1111111111111111],do(D3)=do(D4);由定理5 可輕松判定G3～=G4.

3)G5和G6均是3 正則簡單無向連通圖[3].按圖中頂點標號,經(jīng)計算可得G5和G6的距離矩陣分別為

經(jīng)計算可得,det(D5)=0,det(D6)=-4352.因 det(D5)≠det(D6),由定理3 可以判定G5和G6不同構(gòu).

因ds(D5)=ds(D6)=[304020],但r(D5)≠r(D6),故由推論2 或定理5 亦可判定G5和G6不同構(gòu).

4)G7和G8均是3 正則簡單無向連通圖(Petersen 圖[4,13]).按圖中頂點標號,經(jīng)計算可得G7和G8的距離矩陣為

因D7=D8,由定理1、定理3 或定理5 均可判定G7～=G8.

此外,因圖的距離譜不同,故由定理5 可輕松判定G7和G8與G5或G6不同構(gòu).

5)G9和G10均是簡單無向連通圖,按圖中標號可得G9和G10的距離矩陣分別為

3 結(jié)束語

圖的同構(gòu)關(guān)系是一種等價關(guān)系.圖論在自然科學(xué)和社會科學(xué)的諸多領(lǐng)域中有著廣泛的應(yīng)用,凡與圖的結(jié)構(gòu)相關(guān)的分類、聚類、識別與學(xué)習等問題均與圖的同構(gòu)判定問題有關(guān).時至今日,圖的同構(gòu)判定問題仍然具有重要的理論和應(yīng)用價值.

本文給出了簡單無向圖距離矩陣的定義,將基于鄰接矩陣的同構(gòu)判定條件推廣到簡單無向圖距離矩陣.由簡單無向連通圖的距離矩陣很容易求得該圖的直徑(求圖的直徑是圖論中的難題[13])、半徑和離心率等[4],而這些整體性結(jié)構(gòu)參數(shù)不可能由鄰接矩陣得到.此外,距離矩陣是素矩陣而鄰接矩陣一般不是素矩陣.正是利用了這些鄰接矩陣所沒有的整體結(jié)構(gòu)性質(zhì),本文給出了基于距離矩陣特征多項式的同構(gòu)判定條件(定理3).距離矩陣特征多項式不同于鄰接矩陣特征多項式,鄰接矩陣特征多項式相等僅是兩個簡單無向連通圖同構(gòu)的必要條件.就無向樹而言,隨著頂點數(shù)趨于無窮大,幾乎沒有樹可被它的鄰接矩陣特征值唯一確定[4].為避免特征多項式計算誤差對判定結(jié)果的影響,本文率先給出了簡單無向連通圖距離矩陣列和向量與圖的距離譜的定義,并進一步給出了基于距離矩陣的秩與列和向量的同構(gòu)判定條件(定理5).該條件易于驗證且不產(chǎn)生計算誤差,故更適合大規(guī)模簡單無向連通圖的同構(gòu)判定.定理3 和定理5 均是充要條件且均具有多項式時間復(fù)雜度.針對無向樹的同構(gòu)判定問題,本文還給出了基于距離譜的判定條件(推論4).容易理解,將定理3 特別是定理5 用于簡單無向不連通圖的各個連通子圖或?qū)⑼普? 用于無向森林的各個無向樹,就可解決任意簡單無向不連通圖的同構(gòu)判定問題.最后,本文用一些典型例圖說明了定理3、定理5、推論4 及其他相關(guān)結(jié)論的使用方法,其中部分例圖(如Wagner 圖和Petersen 圖)曾被多位學(xué)者深入研究或引用過.

本文的主要創(chuàng)新點和貢獻可概括為: 1)給出了簡單無向圖的同構(gòu)判定條件,這些條件均具有多項式時間復(fù)雜度,間接地證明了簡單無向圖的同構(gòu)判定問題是P問題;2)不同于現(xiàn)有的圖上操作算法(搜索-標號-回溯算法),本文所給的同構(gòu)判定條件均是數(shù)學(xué)方程式,不僅便于分析和應(yīng)用而且便于計算機編程;3)因簡單無向圖是一大類常見的圖且無向樹和極大無向外平面圖均是簡單無向圖的真子集,故本文的主要結(jié)果是現(xiàn)有工作的一個重要進展.需要說明的是,雖然本文在簡單無向圖的同構(gòu)判定問題上有較大進展,但一般(任意)無向或有向圖的同構(gòu)判定是P還是NP問題仍然沒有得到解決.

今后,我們將針對簡單有向強連通圖的同構(gòu)判定問題開展研究,期望得到一些有理論和實用價值的新結(jié)果.