一種對稱無向圖的同構判定算法

李正平, 白倩倩

(安徽大學 電子信息工程學院,安徽 合肥 230601)

圖常用于表達抽象后的數據、信息之間的關系。在圖論中,圖同構是一個非常重要的課題,也是一個NP-難問題。在計算機視覺、模式識別等諸多領域中[1],圖同構的判定都具有重要意義。例如，化學中同分異構體的判定、相同電路和開關拓撲的識別、相似漢字的識別等等都可歸結為圖同構問題[2]。

2015年,芝加哥大學的LászlóBabai教授宣稱發現了一個擬多項式的圖同構算法,但有學者懷疑這種算法的實際應用價值[3]。在已被認可的算法中,某些特定類型的圖存在多項式算法,如樹圖、平面圖、區間圖。然而針對任意圖的同構判定,目前還不存在多項式時間算法,所有的算法在最壞的情況下的時間復雜度都是指數級的。目前所提出的算法主要分為3類:基于神經網絡的判定算法,如基于Hopfield網絡的圖的同構算法[4];基于搜索的判定算法,如Ullmann同構算法[5];基于圖的特征信息的判定算法,如出入度序列法、電路模擬法[6]、特征值和特征向量法[7]等等。其中電路模擬法將圖同構問題轉化為電路問題,對于大多數圖,可以有效快捷地得到頂點對應關系進而判定同構與否。

對于大規模對稱性較強的圖的同構判定問題,現有的電路模擬法效果不佳。本文提出的方法基于Dijkstra算法對原電路模擬法進行改進,適用于含權對稱無向圖的同構判定。

1 相關概念與原理

1.1 圖同構的定義

設G1=(V1,E1)和G2=(V2,E2)是2個無向圖,V表示點集,E∈V×V表示邊集。若2個圖同構,則存在雙射f:V1→V2，當且僅當(f(u),f(v))∈E2且(u,v)與(f(u),f(v))的重數相同[8]。

由定義可知,2個圖同構，即它們的結構完全相同[9],頂點之間存在一一映射的關系,且在這種對應關系下，邊與邊也是一一映射的。

1.2 圖的鄰接矩陣

鄰接矩陣是圖的表示方法之一,將圖的結構特征描述用矩陣表示。設圖G=(V,E)包含n個頂點,圖的鄰接矩陣D為n×n階矩陣,其中元素分布如下:

1.3 Dijkstra算法

Dijkstra算法是一個解決單源最短路徑問題的算法,它是一個迭代過程[10]。其基本思想是以源點為中心,逐步將當前路徑最小的頂點加入到源點所在集合中,直到該集合包含所有頂點為止[11]。Dijkstra算法可以有效地求得圖中一個節點到其他所有節點的最短距離[12],而通過頂點間的最短距離對于對稱圖進行頂點分類,能夠降低需要交換的頂點次數,達到快速搜索的效果。d(s)=[ds1,ds2,…,dsn],dsi是源點到點i(i≠s)之間的距離。d的含義見表1所列。

表1 d的不同值所代表的含義

1.4 圖同構的性質

定理1圖同構的充分必要條件是具有相同的鄰接矩陣[6]。

元素在鄰接矩陣中排列順序是無關緊要的。若將一個圖的鄰接矩陣的行與行、列與列之間進行有限次交換后與另一個圖的鄰接矩陣相同,則兩圖同構。實際上將圖的鄰接矩陣進行行交換和列交換就是更改圖中頂點的排列順序。

為了實現高效的判定,應盡可能根據所得頂點屬性(如頂點度數、回路數等)將頂點分割成多個頂點集,各子集內的頂點屬性相同，從而完成對頂點的分區。

2 判定算法

基于對稱圖的特殊性,利用Dijkstra算法獲得的最短距離來區分頂點是便捷有效的。首先找出一組對應的頂點作為源點(這2個源點必須是已經確定對應關系的一組頂點),通常由度序列和節點電壓值很容易找到一組或多組對應節點,抽取其中一組作為源點,求解其余點到源點的距離,進一步對頂點進行分區。對于中心對稱圖,由度序列和節點電壓值不能確認任何一組頂點的對應關系,可在第1個圖中任意選擇1個頂點作為源點,在第2個圖中遍歷所有頂點找到與第1個圖1源點映射的頂點作為源點。

本文算法具體步驟如下:

輸入:兩圖的鄰接矩陣。

輸出:兩圖是否同構。

首先驗證兩圖是否滿足同構的必要條件,具有相同頂點數、相同邊數和相同的重邊數。

(1) 輸入兩圖G、G′的鄰接矩陣D、D′。

(2) 計算得出度序列Q、Q′,并將鄰接矩陣按Q、Q′降序(升序)重排,相同則判定同構,不相同則繼續判定。

(3) 將圖轉化為伴隨電路,根據模擬電路法分別求出節點電壓序列U、U′。

(4) 將鄰接矩陣按U、U′降序(升序)重排并比較,相同則判定同構,不相同則繼續判定。

(5) 兩圖中若存在電壓值對應相同且異于其余各頂點的一組頂點,可初步判定為對應頂點并選作源點。將鄰接矩陣中數組元素取數組中的最小值替換,值為0的元素替換為∞。根據轉換后的矩陣使用Dijkstra算法得到其余點與源點的最短距離序列,轉到步驟(7)。

(6) 若每個頂點電壓值均為相同值,則無法確定一組對應頂點。這時,分別在第1、2個圖中的最小分區(包含相同電壓值頂點最少的頂點子集)中選取一個頂點作為源點,通過Dijkstra算法求解最短距離序列。

(7) 根據最短距離序列得到兩圖頂點映射關系,根據頂點映射關系調整鄰接矩陣,相同則兩圖同構,不相同則兩圖異構。

3 實例說明

電路模擬法判定兩圖同構最壞的情況是對稱圖,需對頂點次序進行全排列,即鄰接矩陣需做n!次調整。

例1假設要判定的圖為G、G′，如圖1所示。

圖1 對稱無向圖同構實例

(1) 輸入兩圖的鄰接矩陣D、D′。D、D′為：

(2) 分別計算出兩圖的度序列Q=[4,4,4,4,4,4]、Q′=[4,4,4,4,4,4]。度序列相同則可能同構,將2個度序列按降序排列均為[4,4,4,4,4,4],因為圖1中各頂點度均相同,所以無法按照度序列對頂點分區。

(3) 分別求出兩圖的導納矩陣。N、N′為：

增加額外的頂點v7、v7′,并將其作為激勵參考點。利用電路模擬法求出兩圖節點電壓序列：

U=[0.500 0,0.500 0,0.500 0,0.500 0,

0.500 0,0.500 0)],

U′=[0.500 0,0.500 0,0.500 0,0.500 0,

0.500 0,0.500 0]。

(4) 對兩圖節點電壓序列按降序重排均為[0.500 0,0.500 0,0.500 0,0.500 0,0.500 0,0.500 0],無法根據電壓值對頂點分區。

(5) 將兩圖的鄰接矩陣D、D′做以下調整，用于Dijkstra算法運算,即

得到新的鄰接矩陣：

(6) 任取圖G中的一個頂點如v1作為源點,通過Dijkstra算法得出最短距離矩陣d(1)=[0,1,1,2,2,3],矩陣各元素對應頂點(v1,v2,v3,v4,v5,v6)。對于圖G′,任一頂點作為源點的距離矩陣均為d′(i)=[0,1,1,2,2,3] (i=1～6), 各元素對應頂點為(v1′,v3′,v4′,v2′,v6′,v5′)，因此所有頂點均有可能是圖G中v1的對應頂點。依次選取圖G′中的點作為源點與圖G′嘗試匹配，如v1→v1′時的頂點分區及可能對應關系(v2,v3)→(v3′,v4′)、(v4,v5)→(v2′,v6′)、v6→v5′。

(7) 重復排列所有可能的頂點對應關系,比較對應的鄰接矩陣,直到得到一組映射關系(v1→v1′,v2→v4′,v3→v3′,v4→v6′,v5→v2′,v6→v5′),使鄰接矩陣相同,圖G、G′同構。若根據所有可能的頂點對應關系調整后的鄰接矩陣都不相同,則判定兩圖異構。

4 算法對比分析

基于圖同構的性質提出的頂點置換法,其思路是對圖中頂點順序進行全排列,驗證兩圖的所有可能的鄰接矩陣中是否存在相同矩陣。因為隨著圖的規模的增大,交換的次數很龐大,并且判定兩圖異構時需要比較全部的排列可能才能得出結論,所以只適合于小圖的同構判定。而原電路模擬法利用各節點電壓對頂點進行分區,大大減少了頂點映射搜索范圍。但是對于對稱圖,各頂點度數相同且電壓相同,各頂點自身不變屬性相同無法區分頂點。此時該算法優勢消失,時間復雜度幾乎接近頂點置換法。本文提出的算法利用頂點之間的距離關系可有效地對對稱圖頂點進行分區,進而有效提高同構判定的效率,相對于頂點置換法和原電路模擬法,具有更高的效率。

針對本例中圖G,通過需要交換的頂點分區情況對幾種方法的搜索范圍進行比較:

(1) 頂點置換法。需置換所有頂點的排列方式,搜索范圍6!=720。

(2) 度序列法和模擬電壓法。度和節點電壓并未對頂點做出分區,搜索范圍同頂點置換法為6!=720。

(3) 本文算法。加入Dijkstra算法所得距離序列后,搜索范圍為6×2!×2!=24。

5 實驗結果分析

為了驗證本文算法的效率,分別選取不同頂點(3～160)的對稱無向圖進行同構判定實現,與原電路模擬法進行對比，結果見表2所列，如圖2所示。測試環境如下:CPU為Intel(R) Core(TM) i5-2400 CPU @ 3.10 GHz 3.10 GHz;內存為4.00 GB;操作系統為Windows 7;編程語言為Matlab。

表2 不同算法判斷對稱無向圖同構的運行時間

圖2 對稱無向圖同構判定不同算法的運行時間比較

對于強對稱性圖的同構判定,電路模擬法的仿真時間主要消耗在對兩圖鄰接矩陣的轉換和匹配上。而本文算法通過加入距離矩陣減少了搜索范圍。從圖2可以看出,在電路模擬法中加入Dijkstra算法后可以有效地降低算法的時間復雜度,表明該算法對于強對稱無向圖的同構判定是有效的,并且頂點數越大,兩算法的時間復雜度差異越大,即本文算法的優化效果越明顯。

6 結 論

本文提出的對稱無向圖同構判定算法,是基于Dijkstra算法對電路模擬法判定算法的優化。由于對稱無向圖中多個頂點具有相同電壓,局部排列的規模就會變大,此電路模擬法的優勢逐漸削弱。改進算法后,提高了對稱性較高的圖的算法實用性,對于電路模擬法出現故障的情況得以解決。通過Dijkstra算法縮小對應頂點的搜索范圍,減少鄰接矩陣的比較次數,提高了對稱無向圖的判定效率。基于圖的特征信息的同構判定算法的基本思路是一致的,首先對頂點進行分區,然后根據“兩圖同構的充分必要條件是具有相同的鄰接矩陣”來最終判定兩圖是否同構。找到一個簡潔有效的充要條件是該領域未來的一個研究方向。