施鍵蘭

?

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

施鍵蘭

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

其中行為頂點(diǎn)序列，列為邊序列，矩陣中的數(shù)字為該頂點(diǎn)和對(duì)應(yīng)邊的關(guān)聯(lián)次數(shù)。該圖有4個(gè)頂點(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)矩陣，通過(guò)有限次的行列交換之后，能得到相同的矩陣，則兩圖同構(gòu)。因此，通過(guò)矩陣表示圖的方法，可以在計(jì)算機(jī)中編程實(shí)現(xiàn)圖同構(gòu)的判定。

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

3 具體算法案例

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

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

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

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

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

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

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

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

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

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

歸納這個(gè)算法，具體的步驟如下：

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

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

[9] 盧超, 黃蔚, 胡國(guó)超. 基于圖形數(shù)據(jù)結(jié)構(gòu)的復(fù)雜對(duì)象建模設(shè)計(jì)[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號(hào)，項(xiàng)目編號(hào)：JAT170897)

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

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