一種對(duì)稱無(wú)向圖的同構(gòu)判定算法

李正平, 白倩倩

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

圖常用于表達(dá)抽象后的數(shù)據(jù)、信息之間的關(guān)系。在圖論中,圖同構(gòu)是一個(gè)非常重要的課題,也是一個(gè)NP-難問(wèn)題。在計(jì)算機(jī)視覺(jué)、模式識(shí)別等諸多領(lǐng)域中[1],圖同構(gòu)的判定都具有重要意義。例如，化學(xué)中同分異構(gòu)體的判定、相同電路和開關(guān)拓?fù)涞淖R(shí)別、相似漢字的識(shí)別等等都可歸結(jié)為圖同構(gòu)問(wèn)題[2]。

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

對(duì)于大規(guī)模對(duì)稱性較強(qiáng)的圖的同構(gòu)判定問(wèn)題,現(xiàn)有的電路模擬法效果不佳。本文提出的方法基于Dijkstra算法對(duì)原電路模擬法進(jìn)行改進(jìn),適用于含權(quán)對(duì)稱無(wú)向圖的同構(gòu)判定。

1 相關(guān)概念與原理

1.1 圖同構(gòu)的定義

設(shè)G1=(V1,E1)和G2=(V2,E2)是2個(gè)無(wú)向圖,V表示點(diǎn)集,E∈V×V表示邊集。若2個(gè)圖同構(gòu),則存在雙射f:V1→V2，當(dāng)且僅當(dāng)(f(u),f(v))∈E2且(u,v)與(f(u),f(v))的重?cái)?shù)相同[8]。

由定義可知,2個(gè)圖同構(gòu)，即它們的結(jié)構(gòu)完全相同[9],頂點(diǎn)之間存在一一映射的關(guān)系,且在這種對(duì)應(yīng)關(guān)系下，邊與邊也是一一映射的。

1.2 圖的鄰接矩陣

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

1.3 Dijkstra算法

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

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

1.4 圖同構(gòu)的性質(zhì)

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

元素在鄰接矩陣中排列順序是無(wú)關(guān)緊要的。若將一個(gè)圖的鄰接矩陣的行與行、列與列之間進(jìn)行有限次交換后與另一個(gè)圖的鄰接矩陣相同,則兩圖同構(gòu)。實(shí)際上將圖的鄰接矩陣進(jìn)行行交換和列交換就是更改圖中頂點(diǎn)的排列順序。

為了實(shí)現(xiàn)高效的判定,應(yīng)盡可能根據(jù)所得頂點(diǎn)屬性(如頂點(diǎn)度數(shù)、回路數(shù)等)將頂點(diǎn)分割成多個(gè)頂點(diǎn)集,各子集內(nèi)的頂點(diǎn)屬性相同，從而完成對(duì)頂點(diǎn)的分區(qū)。

2 判定算法

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

本文算法具體步驟如下:

輸入:兩圖的鄰接矩陣。

輸出:兩圖是否同構(gòu)。

首先驗(yàn)證兩圖是否滿足同構(gòu)的必要條件,具有相同頂點(diǎn)數(shù)、相同邊數(shù)和相同的重邊數(shù)。

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

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

(3) 將圖轉(zhuǎn)化為伴隨電路,根據(jù)模擬電路法分別求出節(jié)點(diǎn)電壓序列U、U′。

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

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

(6) 若每個(gè)頂點(diǎn)電壓值均為相同值,則無(wú)法確定一組對(duì)應(yīng)頂點(diǎn)。這時(shí),分別在第1、2個(gè)圖中的最小分區(qū)(包含相同電壓值頂點(diǎn)最少的頂點(diǎn)子集)中選取一個(gè)頂點(diǎn)作為源點(diǎn),通過(guò)Dijkstra算法求解最短距離序列。

(7) 根據(jù)最短距離序列得到兩圖頂點(diǎn)映射關(guān)系,根據(jù)頂點(diǎn)映射關(guān)系調(diào)整鄰接矩陣,相同則兩圖同構(gòu),不相同則兩圖異構(gòu)。

3 實(shí)例說(shuō)明

電路模擬法判定兩圖同構(gòu)最壞的情況是對(duì)稱圖,需對(duì)頂點(diǎn)次序進(jìn)行全排列,即鄰接矩陣需做n!次調(diào)整。

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

圖1 對(duì)稱無(wú)向圖同構(gòu)實(shí)例

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

(2) 分別計(jì)算出兩圖的度序列Q=[4,4,4,4,4,4]、Q′=[4,4,4,4,4,4]。度序列相同則可能同構(gòu),將2個(gè)度序列按降序排列均為[4,4,4,4,4,4],因?yàn)閳D1中各頂點(diǎn)度均相同,所以無(wú)法按照度序列對(duì)頂點(diǎn)分區(qū)。

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

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

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) 對(duì)兩圖節(jié)點(diǎn)電壓序列按降序重排均為[0.500 0,0.500 0,0.500 0,0.500 0,0.500 0,0.500 0],無(wú)法根據(jù)電壓值對(duì)頂點(diǎn)分區(qū)。

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

得到新的鄰接矩陣：

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

(7) 重復(fù)排列所有可能的頂點(diǎn)對(duì)應(yīng)關(guān)系,比較對(duì)應(yīng)的鄰接矩陣,直到得到一組映射關(guān)系(v1→v1′,v2→v4′,v3→v3′,v4→v6′,v5→v2′,v6→v5′),使鄰接矩陣相同,圖G、G′同構(gòu)。若根據(jù)所有可能的頂點(diǎn)對(duì)應(yīng)關(guān)系調(diào)整后的鄰接矩陣都不相同,則判定兩圖異構(gòu)。

4 算法對(duì)比分析

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

針對(duì)本例中圖G,通過(guò)需要交換的頂點(diǎn)分區(qū)情況對(duì)幾種方法的搜索范圍進(jìn)行比較:

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

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

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

5 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文算法的效率,分別選取不同頂點(diǎn)(3～160)的對(duì)稱無(wú)向圖進(jìn)行同構(gòu)判定實(shí)現(xiàn),與原電路模擬法進(jìn)行對(duì)比，結(jié)果見(jiàn)表2所列，如圖2所示。測(cè)試環(huán)境如下:CPU為Intel(R) Core(TM) i5-2400 CPU @ 3.10 GHz 3.10 GHz;內(nèi)存為4.00 GB;操作系統(tǒng)為Windows 7;編程語(yǔ)言為Matlab。

表2 不同算法判斷對(duì)稱無(wú)向圖同構(gòu)的運(yùn)行時(shí)間

圖2 對(duì)稱無(wú)向圖同構(gòu)判定不同算法的運(yùn)行時(shí)間比較

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

6 結(jié) 論

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