無(wú)向圖同構(gòu)的快速算法*

侯愛民 郝志峰 胡傳福 陸海鵬

(華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東廣州510006)

在研究圖論的問題中，經(jīng)常需判斷兩個(gè)圖是否同構(gòu)，即從頂點(diǎn)和邊的拓?fù)浣Y(jié)構(gòu)上來(lái)看，兩個(gè)圖是否有可能以同樣的方式畫出.換句話說(shuō)，當(dāng)兩個(gè)圖同構(gòu)時(shí)，兩個(gè)圖的頂點(diǎn)之間具有保持相鄰關(guān)系的一一對(duì)應(yīng).判斷兩個(gè)圖是否同構(gòu)是一個(gè)NP難問題.

至今為止，國(guó)內(nèi)國(guó)際上公認(rèn)的實(shí)際可行的判斷算法分為兩類:一類是對(duì)頂點(diǎn)編號(hào)進(jìn)行特殊處理［1-2］，另一類是通過不斷刪除頂點(diǎn)來(lái)對(duì)頂點(diǎn)集合的劃分進(jìn)行細(xì)分［3-7］.Babai等［1］使用頂點(diǎn)度數(shù)對(duì)隨機(jī)圖進(jìn)行規(guī)范標(biāo)記，能產(chǎn)生同樣規(guī)范標(biāo)記的兩個(gè)圖是同構(gòu)的，不能產(chǎn)生同樣規(guī)范標(biāo)記的兩個(gè)圖是不同構(gòu)的.該算法的時(shí)間復(fù)雜度為O(n2)，是目前為止運(yùn)算速度最快的著名算法.其缺點(diǎn)是對(duì)于不能進(jìn)行規(guī)范標(biāo)記的兩個(gè)圖，算法失效;而且拒絕率上界為n－1/7.對(duì)其改進(jìn)的算法［2］也具有非零非負(fù)的拒絕率，即雖然它們的平均運(yùn)行時(shí)間非?？?，也不能處理所有類型的圖.頂點(diǎn)集合劃分是判斷圖同構(gòu)的一種有效方法，可以有效減小同構(gòu)函數(shù)候選集.這一思想也是目前許多常見的圖同構(gòu)判斷算法［3-7］的基本思想.但這些算法不可避免地都要進(jìn)行回溯，也就是要構(gòu)造一棵搜索樹，不斷進(jìn)行試探和剪枝，算法的時(shí)間復(fù)雜度取決于回溯的深度和次數(shù).

文獻(xiàn)［8］中提出了判斷無(wú)向圖同構(gòu)的一個(gè)高效的必要條件，使用這個(gè)條件，可以更細(xì)地對(duì)頂點(diǎn)集合進(jìn)行劃分.文獻(xiàn)［9］中提出了判斷無(wú)向圖同構(gòu)的一個(gè)充分必要條件，使用這個(gè)條件，可以判斷同構(gòu)的兩個(gè)圖在新增頂點(diǎn)和關(guān)聯(lián)邊后構(gòu)成的新圖是否同構(gòu).因?yàn)樾聢D是否同構(gòu)取決于舊圖的同構(gòu)函數(shù)，所以利用必要條件篩選舊圖的同構(gòu)函數(shù)候選集，可以降低時(shí)間開銷.文中采用基于子圖同構(gòu)判斷父圖同構(gòu)的策略，提出一種新的無(wú)需回溯的快速算法，用于降低時(shí)間開銷，保證正確判斷.通過理論論證、實(shí)際案例測(cè)試，驗(yàn)證了該算法的有效性.

1 無(wú)向圖同構(gòu)的相關(guān)理論

使用必要條件可以對(duì)頂點(diǎn)集合V(G)進(jìn)行劃分.針對(duì)某種劃分{cell1，cell2，…，cellk}，(celli?V(G)，1≤i≤k)，同構(gòu)函數(shù)候選集的大小為.必要條件不同，導(dǎo)致頂點(diǎn)集合劃分的細(xì)分程度不同.細(xì)分程度越細(xì)(即k越大，且越小)，同構(gòu)函數(shù)候選集越小，從而導(dǎo)致需檢驗(yàn)的頂點(diǎn)對(duì)應(yīng)關(guān)系越少，越能有效地降低判斷算法的時(shí)間開銷.文獻(xiàn)［8］中提出一個(gè)必要條件，其細(xì)分程度比“頂點(diǎn)度”必要條件和“頂點(diǎn)的鄰接點(diǎn)的度序列”必要條件更細(xì)，也比文獻(xiàn)［3］中提出的必要條件更細(xì).

本算法核心思想使用文獻(xiàn)［9］中提出的充分必要條件進(jìn)行判斷，既可以保證完備性和收斂性，又可以避免回溯.

定義1［8］設(shè)無(wú)向圖G=(V，E)，在其鄰接矩陣AG=(aij)n×n中，第i行與第j行的行碼距異或距離定義為第i行與第j行對(duì)應(yīng)列上取不同值(即一個(gè)取0，另一個(gè)取1或k)的諸列上各元素之和，記為xord(i，j).如果 i≠j，則令 byij=xord(i，j);否則令byij=aii.稱矩陣BYG=(byij)n×n為圖 G 的行碼距異或矩陣.

定義2［8］設(shè)無(wú)向圖G=(V，E)，在其鄰接矩陣AG=(aij)n×n中，第i行與第j行的行碼距同或距離定義為第i行與第j行對(duì)應(yīng)列上取相同值(即一個(gè)取1或k，另一個(gè)也取1或k)的諸列上各元素之和，記為aord(i，j).對(duì)于所有的 i和 j，令 btij=aord(i，j).稱矩陣BTG=(btij)n×n為圖G的行碼距同或矩陣.

定義3［8］設(shè)兩個(gè)矩陣 A=(aij)n×n和 B=(bij)n×n，A 中的行編號(hào)為 u1，u2，…，un，B 中的行編號(hào)為 v1，v2，…，vn.如果存在一個(gè)置換［u1? v'1，u2?v'2，…，un? v'n］，其中(v'1，v'2，…，v'n)是(v1，v2，…，vn)的一種排列，使得A中編號(hào)為ui的行與B中編號(hào)為v'i的行具有元素一樣的特征(不考慮元素的位置次序)，則稱［u1?v'1，u2?v'2，…，un?v'n］為矩陣 A 和 B的行－行置換.

定理1［8］設(shè)兩個(gè)無(wú)向圖G和H同構(gòu)，則圖G的鄰接矩陣、行碼距異或矩陣、行碼距同或矩陣分別與圖H的鄰接矩陣、行碼距異或矩陣、行碼距同或矩陣具有同一的行－行置換.

定理2［8］設(shè)兩個(gè)無(wú)向圖G和H同構(gòu)，則一定存在圖G的一個(gè)子圖Gi和圖H的一個(gè)子圖Hj同構(gòu).對(duì)于任意一對(duì)同構(gòu)的子圖Gi和Hj，必有圖Gi的鄰接矩陣、行碼距異或矩陣、行碼距同或矩陣分別與圖Hj的鄰接矩陣、行碼距異或矩陣、行碼距同或矩陣具有同一的行－行置換.這種關(guān)系一直保持到Gi和Hj只有兩個(gè)頂點(diǎn).

定理3［9］同構(gòu)的兩個(gè)無(wú)向圖G和H，各自增加一個(gè)頂點(diǎn)unew和vnew，以及與新增頂點(diǎn)關(guān)聯(lián)的若干條邊，形成兩個(gè)新圖G+unew和H+vnew.新圖G+unew和H+vnew同構(gòu)，當(dāng)且僅當(dāng)存在G?H的一個(gè)同構(gòu)函數(shù)f，使得新頂點(diǎn)的所有鄰接點(diǎn)在同構(gòu)函數(shù)f的作用下，在G和H中保持同構(gòu)關(guān)系.

2 無(wú)向圖同構(gòu)的快速判斷算法

步驟1 根據(jù)圖G和H的鄰接矩陣AG和AH，分別計(jì)算圖G和H的行碼距異或矩陣BYG和BYH，以及行碼距同或矩陣BTG和BTH.

步驟2 根據(jù)圖G的行碼距異或矩陣BYG，依次考慮每個(gè)頂點(diǎn)ui(1≤i≤n)所在的行.對(duì)于每個(gè)頂點(diǎn)ui所在的行，在圖H的行碼距異或矩陣BYH中尋找保持元素一樣的對(duì)應(yīng)行，構(gòu)成頂點(diǎn)ui的一個(gè)匹配集S_ui.如果某個(gè)頂點(diǎn)不存在匹配集，則可以判斷圖G和H不同構(gòu)，算法結(jié)束;如果所有匹配集的并集沒有n個(gè)元素，則可以判斷圖G和H不同構(gòu)，算法結(jié)束;否則，在鄰接矩陣AG和AH、行碼距同或矩陣BTG和BTH中，檢查這些匹配集是否依然成立.如果不成立，則可以判斷圖G和H不同構(gòu)，算法結(jié)束;否則，根據(jù)匹配集，生成若干個(gè)行－行置換.

步驟3 考慮圖G的任意一個(gè)頂點(diǎn)ui.對(duì)于vj∈S_ui，依據(jù)步驟1和步驟2的方法，判斷子圖G－ui和H－vj是否同構(gòu).如果存在某個(gè)頂點(diǎn)ui，使得對(duì)于vj∈S_ui，都有子圖G －ui和H －vj不同構(gòu)，則可以判斷圖G和H不同構(gòu).算法結(jié)束.

步驟4 考慮圖G的具有相同最小度數(shù)的每個(gè)頂點(diǎn)ui.對(duì)于vj∈S_ui，分別判斷子圖G －ui和H －vj是否為完全圖.若是，則可以判斷圖G和H同構(gòu).算法結(jié)束.此時(shí)，G－ui?H－vj的任何同構(gòu)函數(shù)f，補(bǔ)充對(duì)應(yīng)關(guān)系vj=f(ui)后，都將構(gòu)成G?H的同構(gòu)函數(shù).

步驟5 考慮圖G的具有相同最小度數(shù)的每個(gè)頂點(diǎn)ui.對(duì)于vj∈S_ui，檢查ui的所有鄰接點(diǎn)和vj的所有鄰接點(diǎn)在子圖G－ui和H－vj中是否保持同構(gòu)關(guān)系.具體做法如下根據(jù)子圖G－ui和H－vj的頂點(diǎn)匹配集，檢查ui的所有鄰接點(diǎn)和vj的所有鄰接點(diǎn)是否滿足這些匹配關(guān)系;在滿足的前提下，根據(jù)排列組合生成若干個(gè)行－行置換，這些行－行置換構(gòu)成一個(gè)潛在的同構(gòu)函數(shù)候選集;檢查每一個(gè)行－行置換是否是子圖G－ui和H－vj的同構(gòu)函數(shù);如果有一個(gè)行－行置換是子圖G－ui和H－vj的同構(gòu)函數(shù)f，則可以判斷圖G和H同構(gòu).算法結(jié)束.此時(shí)，對(duì)這個(gè)同構(gòu)函數(shù)f補(bǔ)充對(duì)應(yīng)關(guān)系vj=f(ui)后，將構(gòu)成G?H的同構(gòu)函數(shù).否則，所有的行－行置換都不是子圖G－ui和H－vj的同構(gòu)函數(shù)，可以判斷圖G和H不同構(gòu)，算法結(jié)束.

3 實(shí)驗(yàn)及案例分析

文中給出了一些典型案例(見圖1)來(lái)說(shuō)明上述算法的可行性，同時(shí)給出了與其它必要條件/算法的對(duì)比分析，以說(shuō)明上述算法的有效性.

圖1 一些典型案例Fig.1 Some typical cases

如圖1(a)所示，案例1中，原始圖G和H的行碼距異或矩陣BYG和BYH之間不存在同一的行－行置換，因?yàn)锽YG中存在一行(04644464)，在BYH中不存在對(duì)應(yīng)行.相反，使用“頂點(diǎn)度”必要條件和“頂點(diǎn)的鄰接點(diǎn)的度序列”必要條件，以及文獻(xiàn)［3］中提出的必要條件，都不能直接判斷出G和H不同構(gòu).此外，文獻(xiàn)［1］中提出的算法不能對(duì)圖1(a)案例進(jìn)行規(guī)范標(biāo)記，從而無(wú)法判斷是否同構(gòu).

如圖1(b)所示案例2中，原始圖G和H的行碼距異或矩陣BYG和BYH之間存在同一的行－行置換，但是子圖G－u1的行碼距異或矩陣BYG－u1和子圖 H－vj(1≤j≤10)的行碼距異或矩陣BYH－vj之間不存在同一的行－行置換.使用“頂點(diǎn)的鄰接點(diǎn)的度序列”必要條件，能直接判斷出G－u1和H－vj(1≤j≤10)不同構(gòu).但使用“頂點(diǎn)度”必要條件和文獻(xiàn)［3］中提出的必要條件，都不能直接判斷出G－u1和H－vj(1≤j≤10)不同構(gòu).另一方面，在處理圖1(b)案例時(shí)，文獻(xiàn)［3-7］中算法需要進(jìn)行多次回溯操作.此外，文獻(xiàn)［1］中提出的算法不能對(duì)圖1(b)案例進(jìn)行規(guī)范標(biāo)記，從而無(wú)法進(jìn)行判斷.

此外，文獻(xiàn)［1-2］是目前為止平均時(shí)間開銷最少的判斷算法，其缺點(diǎn)是具有非零非負(fù)的拒絕率.也就是說(shuō)，這類算法不能處理所有類型的圖.例如，文獻(xiàn)［1］中的拒絕率上界為n－1/7.針對(duì)頂點(diǎn)個(gè)數(shù)n=128的兩個(gè)無(wú)向圖，最壞情況下將有50%的圖不能進(jìn)行判斷，而文中算法可以處理所有類型的圖.

事實(shí)上，對(duì)隨機(jī)生成的無(wú)向正則圖和無(wú)向非正則圖、無(wú)向強(qiáng)正則圖、無(wú)向偽圖等進(jìn)行案例驗(yàn)證，都能證明了文中算法的正確性和有效性.限于篇幅所限，不再贅述.

使用C語(yǔ)言編程實(shí)現(xiàn)上述圖同構(gòu)判斷算法，對(duì)隨機(jī)生成的一對(duì)隨機(jī)圖(包括正則圖和非正則圖)，以及圖數(shù)據(jù)庫(kù)［10］中的11900個(gè)樣本進(jìn)行程序判定.這些樣本共分5大類，根據(jù)頂點(diǎn)個(gè)數(shù)和其它參數(shù)，每個(gè)大類又分為若干子類.每個(gè)子類測(cè)試了100個(gè)樣本，即50個(gè)配對(duì)圖.所有實(shí)驗(yàn)均在AMD Athlon(tm)64×2 Dual Core Processor 3600Hz/1GB內(nèi)存的計(jì)算機(jī)上進(jìn)行，結(jié)果如表1所示.測(cè)試結(jié)果表明，無(wú)一例外，對(duì)于同構(gòu)的兩個(gè)圖，文中算法均能正確判斷，并給出同構(gòu)函數(shù);對(duì)于不同構(gòu)的兩個(gè)圖，也能正確判斷，且用時(shí)合理.

表1 圖同構(gòu)判斷算法對(duì)5種典型類型圖的測(cè)試結(jié)果Table 1 Test results of the five categories by the proposed graph isomorphism algorithm

程序運(yùn)行的實(shí)驗(yàn)數(shù)據(jù)表明:對(duì)于同構(gòu)的兩個(gè)圖，可以在100s之內(nèi)判斷同構(gòu)，找到一個(gè)同構(gòu)函數(shù).對(duì)于不同構(gòu)的兩個(gè)圖，運(yùn)行時(shí)間取決于頂點(diǎn)個(gè)數(shù)和正則性.在頂點(diǎn)個(gè)數(shù)相同的情況下，非正則圖的運(yùn)行時(shí)間少于正則圖的運(yùn)行時(shí)間.頂點(diǎn)個(gè)數(shù)越多，運(yùn)行時(shí)間越長(zhǎng).強(qiáng)正則圖的運(yùn)行時(shí)間最長(zhǎng).這些結(jié)論與實(shí)際案例驗(yàn)證的結(jié)果一致.

4 結(jié)論

無(wú)向圖同構(gòu)的判斷問題至今沒有完全解決.規(guī)范標(biāo)記算法具有O(n2)的時(shí)間復(fù)雜度，但是不完備，不能處理所有類型的圖.頂點(diǎn)劃分算法需要不斷地回溯和試探，從而造成最壞情況下指數(shù)階時(shí)間復(fù)雜度.為了避免回溯，同時(shí)保證完備性，文中提出一種基于充要條件的快速判斷算法.為了進(jìn)一步降低時(shí)間開銷，采用基于子圖同構(gòu)判斷父圖同構(gòu)的策略，使用一種高效的必要條件篩選同構(gòu)函數(shù)候選集的范圍.最后通過理論論證、實(shí)際案例測(cè)試，驗(yàn)證了該算法的有效性.

［1］Babai L，Erds P，Selkow S M.Random graph isomorphism［J］.SIAM Journal of Computing，1980，9(3):628-635.

［2］Czajka Tomek，Pandurangan Gopal.Improved random graph isomorphism ［J］.Journal of Discrete Algorithms，2008，6(1):85-92.

［3］Ullmann J R.An algorithm for subgraph isomorphism［J］.Journal of the Association for Computer Machinery，1976，23(1):31-42.

［4］Schmidt D C，Druffel L E.A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices［J］.Journal of the Association for Computer Machinery，1976，23(3):433-445.

［5］McKay B D.Practical graph isomorphism［J］.Congressus Numberantium，1981，30:45-87.

［6］Cordella L P，F(xiàn)oggia P，Sansone C，et al.An improved algorithm for matching large graphs［C］∥Proceedings of International Workshop on Graph-based Representation in Pattern Re-cognition.Ischia:［s.n.］，2001:149-159.

［7］Cordella L P，F(xiàn)oggia P，Sansone C，et al.Subgraph transformations for the inexact matching of attributed relational graphs［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(10):1367-1372.

［8］侯愛民.圖同構(gòu)的矩陣初等變換判定及算法設(shè)計(jì)［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42(20):51-54.Hou Ai-min.Elementary operations on a matrix to determine the isomorphism of graphs［J］.Journal of Computer Engineering and Applications，2006，42(20):51-54.

［9］侯愛民.圖同構(gòu)的一個(gè)充分必要條件［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(30):57-61.Hou Ai-min.Necessary and sufficient condition of graphic isomorphism ［J］.Journal of Computer Engineering and Applications，2009，45(30):57-61.

［10］Foggia P，Sansone C，Vento M.A Database of graphs for isomorphism and sub-graph isomorphism benchmarking［C］∥Proceeding of the 3rd IAPR-TC15 International Workshop on Graph-based Representions.Berlin:Springer，Italy，2001:176-187.