施鍵蘭

?

無向圖同構(gòu)的判定研究

施鍵蘭

（福建農(nóng)林大學(xué)東方學(xué)院，福建 福州 350715）

在圖論中，圖同構(gòu)是一個非常重要的問題，是一個N-P問題，在現(xiàn)實(shí)中有非常廣泛的應(yīng)用。根據(jù)許多的研究結(jié)果表明，這類問題應(yīng)該有多項(xiàng)式時間復(fù)雜性的算法。只要其中一個問題能夠解決，其他的問題都能夠迎刃而解。本文針對無向圖，根據(jù)圖和圖之間的關(guān)聯(lián)矩陣，提出了一個實(shí)用的算法。在度數(shù)相同的頂點(diǎn)范圍內(nèi)，利用圖的相鄰頂點(diǎn)的度數(shù)序列，討論其對圖同構(gòu)的影響。該算法降低了時間復(fù)雜性，具有一定的應(yīng)用價值；但也有局限性，在判定的時候有一定的拒絕率。

無向圖；同構(gòu)；圖同構(gòu)；關(guān)聯(lián)矩陣

0 引言

無向圖同構(gòu)是個N-P問題，具有廣泛的應(yīng)用。簡單來說，就是兩個圖的結(jié)構(gòu)完全相同。通常圖同構(gòu)被應(yīng)用在各種模式識別過程之中，比如漢字自動識別中，用來區(qū)分兩個字形很相似的漢字；或者在電路圖識別中，用于識別電路的拓?fù)浣Y(jié)構(gòu)；以及化學(xué)分子結(jié)構(gòu)研究中，用于判斷同分異構(gòu)，等等。類似的問題有300多個，這些問題都是等價的。因此，研究其判定方法具有非常重要的現(xiàn)實(shí)意義[1]。

圖同構(gòu)問題來源于圖論，由于根據(jù)其基本概念進(jìn)行判斷復(fù)雜性非常高，因此，許多人在研究該問題時，都試圖降低其復(fù)雜性，尋找更簡單的判斷方法。根據(jù)許多的研究結(jié)果表明，這類問題，應(yīng)該有多項(xiàng)式時間復(fù)雜性的算法。只要其中一個問題的多項(xiàng)式時間算法能夠解決，其他的問題都能夠迎刃而解。

本文主要討論在無向圖中同構(gòu)的方法判斷，試圖找到一種能降低算法復(fù)雜性的方法[5]。

1 圖的同構(gòu)概念

首先，給出兩圖同構(gòu)的定義：

形象來講，就是兩個表面上看過去相似，或者很不相似的圖，在性質(zhì)上是完全一樣的?？梢詫D看做有彈性的，頂點(diǎn)可以隨意移動位置，在不斷的拉扯變形的過程中，如果一個圖可以變成另一個圖，那么兩個圖就是同構(gòu)的[6-10]。

比如圖1中所示的兩組圖，G1和G1；H1，H2和H3，表面上不同，但實(shí)際上兩圖的頂點(diǎn)之間可以找到一種一一對應(yīng)關(guān)系，使得兩圖的性質(zhì)完全相同。其中H1，H2和H3稱作彼得松（Peterson）圖，它們的頂點(diǎn)對應(yīng)關(guān)系如圖上標(biāo)注的英文字母所示。

圖1 兩組同構(gòu)圖

2 無向圖的關(guān)聯(lián)矩陣表示

為了便于用代數(shù)方法研究圖的性質(zhì)，利用計算機(jī)解決實(shí)際問題，可以將圖用矩陣來表示，將形象的圖數(shù)字化之后存入計算機(jī)，之后利用特定算法對圖進(jìn)行性質(zhì)判定。

在矩陣表示圖之前，需要將圖標(biāo)定頂點(diǎn)和邊的順序，使其成為標(biāo)定圖。比如圖2中所示的這張圖：

圖2 標(biāo)定圖舉例1

圖2是無向圖，用關(guān)聯(lián)矩陣表示為：

其中行為頂點(diǎn)序列，列為邊序列，矩陣中的數(shù)字為該頂點(diǎn)和對應(yīng)邊的關(guān)聯(lián)次數(shù)。該圖有4個頂點(diǎn)5條邊，因此其關(guān)聯(lián)矩陣有4行5列。與其同構(gòu)的圖3：

圖3 標(biāo)定圖舉例2

Fig.3 Example 2 of the calibration diagram

其關(guān)聯(lián)矩陣為：

由圖同構(gòu)的性質(zhì)可以看出，若兩圖的關(guān)聯(lián)矩陣，通過有限次的行列交換之后，能得到相同的矩陣，則兩圖同構(gòu)。因此，通過矩陣表示圖的方法，可以在計算機(jī)中編程實(shí)現(xiàn)圖同構(gòu)的判定。

但由于其中涉及到的行、列交換，在特定的圖的情況下，有可能意味著行和列的全排列，所以，在最壞的情況下，交換的總次數(shù)將達(dá)到n!m!（其中n是圖的頂點(diǎn)總數(shù)，m是圖的邊數(shù)）。因此，在圖的定點(diǎn)數(shù)或邊數(shù)的數(shù)量大一些的時候，這個復(fù)雜度就太高了[1]。

3 具體算法案例

根據(jù)圖同構(gòu)的性質(zhì)，可以得到關(guān)于其同構(gòu)的一些必要性。比如：兩同構(gòu)圖必然頂點(diǎn)數(shù)和邊數(shù)相同，度數(shù)列相同。根據(jù)其必要性，可以在判定的時候，對全排列的比較算法，做一定的改良，增加一些限制條件，僅對于度數(shù)相同的頂點(diǎn)，做相應(yīng)的比較，忽略度數(shù)不同的頂點(diǎn)。這樣可以大大降低運(yùn)算的復(fù)雜性。

見圖4中有G1，G2兩幅圖。這兩幅圖的特點(diǎn)是，都有6個頂點(diǎn)，5條邊。畫出關(guān)聯(lián)矩陣之后，均為6行5列。

首先畫出這兩幅圖的關(guān)聯(lián)矩陣。

G1和G2的關(guān)聯(lián)矩陣如下：

由于每條邊都有兩個頂點(diǎn)，因此關(guān)聯(lián)矩陣的每一列的和都是2。從行的角度分析，每一行的數(shù)字和，等于每一個頂點(diǎn)的度數(shù)。因此，在該矩陣的最前面加一列，用來表示每個頂點(diǎn)對應(yīng)的度數(shù)，方便之后的排列對比。圖G1,和G2改變后的矩陣如下。

對每一條邊的兩個頂點(diǎn)，將其相鄰頂點(diǎn)的度數(shù)，放到矩陣中。稱呼第i行第j列的元素為aij，在G1中，a11=1，其對應(yīng)的相鄰頂點(diǎn)在a21，該頂點(diǎn)是2度，因此，就將數(shù)字2填入第一行第一列中，即a11=2。

按照這種規(guī)律整理完矩陣，得到如下兩個矩陣。

對這兩個矩陣，每行都按照數(shù)字從大到小進(jìn)行排序，可以得到兩個新的矩陣：

在這兩個矩陣之中，對應(yīng)度數(shù)相同的行，逐一進(jìn)行比較。比如G1的第一行，其度數(shù)為1，在G2中找到了第一行為的度數(shù)也為1，比較后發(fā)現(xiàn)兩行是相同的，因此就標(biāo)注G2的第一行為G1的對應(yīng)行，并將G2的第一行所有數(shù)字都改成0。重復(fù)這個過程，繼續(xù)向下比較。G1的第二行是2度，對比G2中2度的頂點(diǎn)，有第2行和第4行。在這兩行中，并沒有和G1的第2行相匹配的行，所以對比結(jié)束，兩圖不同構(gòu)。

之所以提出這種思路，是因?yàn)閷τ谕瑯?gòu)的圖，其對應(yīng)頂點(diǎn)的性質(zhì)應(yīng)該是完全相同的，即每個頂點(diǎn)所關(guān)聯(lián)的邊，其另一個頂點(diǎn)的度數(shù)序列應(yīng)完全相同。通過這種判斷思路，降低了對比次數(shù)，從而提高了算法效率。

歸納這個算法，具體的步驟如下：

步驟1：先做出兩幅圖的關(guān)聯(lián)矩陣。

步驟2：在關(guān)聯(lián)矩陣的每一行前面加上該頂點(diǎn)的度數(shù)作為行標(biāo)。

步驟3：將每一行中頂點(diǎn)的相鄰頂點(diǎn)的度數(shù)記錄到矩陣中。

步驟4：按從大到小排列每行的頂點(diǎn)度數(shù)。

步驟5：對比度數(shù)相同的行，將對比成功的行進(jìn)行標(biāo)注。某兩行對比不成功，則圖不同構(gòu)，退出對比。若成功，則重復(fù)該過程直至所有的行都對比完成。

4 結(jié)論

這個方法可以減少行列交換的重排列次數(shù)，由于采用了排序算法，列的時間復(fù)雜度為O(m2)，低于原本的m!。雖然行的對比次數(shù)，在極端情況下，也就是該圖的每個頂點(diǎn)度數(shù)都接近相同，該圖接近正則圖的情況下，復(fù)雜度還是n!，但從整體來看，時間復(fù)雜度還是有相應(yīng)降低的。

但這個算法也有缺陷，即具有一定的拒絕率，比如對于非同構(gòu)的正則圖，該算法無法判斷出來。經(jīng)過C語言實(shí)驗(yàn)進(jìn)行數(shù)據(jù)測試后，對于不同構(gòu)的兩個圖，頂點(diǎn)個數(shù)越少，運(yùn)行時間越短。圖形中相同度數(shù)的頂點(diǎn)個數(shù)越多，運(yùn)行時間越長[3-4]。

[1] 李鋒, 李曉艷. 圖的同構(gòu)判定算法: 關(guān)聯(lián)度序列法及其應(yīng)用[J]. 復(fù)旦學(xué)報(自然科學(xué)版), 2001.6, 318-325.

[2] 屈婉玲, 耿素云, 張立昂. 離散數(shù)學(xué)[M]. 高等教育出版社, 2015.

[3] 侯愛民, 郝志峰, 胡傳福, 等. 無向圖同構(gòu)的快速算法[J]. 華南理工大學(xué)學(xué)報(自然科學(xué)版), 2011.10, 79-83.

[4] 侯愛民. 求解圖同構(gòu)的判定算法[J]. 計算機(jī)工程與應(yīng)用, 2011, 47(16), 52-57.

[5] 李鋒, 商慧亮. 有向圖的同構(gòu)判定算法: 出入度序列法[J]. 應(yīng)用科學(xué)學(xué)報, 2002.6, 258-262.

[6] 羅笑玲, 黃紹鋒, 歐陽天優(yōu), 等. 基于多分類器集成的圖像文字識別技術(shù)及其應(yīng)用研究[J]. 軟件, 2015, 36(3): 98-102.

[7] 任忠良. 一種基于SIFT特征的快速圖像匹配算法[J]. 軟件, 2015, 36(6): 53-57.

[8] 王琪瑞, 帥天平. 含4-圈且不含3-圈的P4-等可覆蓋圖的刻畫[J]. 軟件, 2015, 36(10): 05-08.

[9] 盧超, 黃蔚, 胡國超. 基于圖形數(shù)據(jù)結(jié)構(gòu)的復(fù)雜對象建模設(shè)計[J]. 軟件, 2015, 36(12): 220-223.

[10] 陳園, 侯贊, 劉軍華, 等. 基于改進(jìn)K-Means聚類醫(yī)學(xué)圖像配準(zhǔn)[J]. 軟件, 2018, 39(01): 75-82.

[11] 胡一然, 宋中山, 孫翀, 等. NVSA: 一種具有可變節(jié)點(diǎn)值的查詢圖搜索算法[J]. 軟件, 2018, 39(3): 16-21.

The Study of Undirected Graph Isomorphism

SHI Jian-lan

(DongFang College, Fujian Agriculture and Forestry University, Fuzhou 350715)

Undirected graph isomorphism is a vary important problem in graph theory. It's an N-P problem. It has a wide range of applications in reality. According to many research results, this kind of problem should have polynomial time complexity algorithm. As long as one problem can be solved, all other problems can be solved. In this paper, a practical algorithm is proposed for undirected graph according to the association matrix between graph and graph. The effect on graph isomorphism is discussed by using the degree sequence of adjacent vertices within the same degree range. The algorithm reduces the time complexity and has certain application value. But also have limitation, have certain rejection rate when judging.

Undirected graph; Isomorphism; Graph isomorphism; Incidence matrix

O157.5

A

10.3969/j.issn.1003-6970.2018.11.015

福建省中青年教師教育科研項(xiàng)目：“圖同構(gòu)算法的研究與實(shí)現(xiàn)”，(閩教科〔2017〕76號，項(xiàng)目編號：JAT170897)

施鍵蘭(1984-)，女，福建福州，講師，研究方向：計算機(jī)算法。

施鍵蘭. 無向圖同構(gòu)的判定研究[J]. 軟件，2018，39（11）：64-67