無向圖同構的判定研究

施鍵蘭

?

無向圖同構的判定研究

施鍵蘭

（福建農林大學東方學院，福建 福州 350715）

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

無向圖；同構；圖同構；關聯(lián)矩陣

0 引言

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

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

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

1 圖的同構概念

首先，給出兩圖同構的定義：

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

比如圖1中所示的兩組圖，G1和G1；H1，H2和H3，表面上不同，但實際上兩圖的頂點之間可以找到一種一一對應關系，使得兩圖的性質完全相同。其中H1，H2和H3稱作彼得松（Peterson）圖，它們的頂點對應關系如圖上標注的英文字母所示。

圖1 兩組同構圖

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

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

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

圖2 標定圖舉例1

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

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

圖3 標定圖舉例2

Fig.3 Example 2 of the calibration diagram

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

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

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

3 具體算法案例

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

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

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

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

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

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

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

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

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

之所以提出這種思路，是因為對于同構的圖，其對應頂點的性質應該是完全相同的，即每個頂點所關聯(lián)的邊，其另一個頂點的度數(shù)序列應完全相同。通過這種判斷思路，降低了對比次數(shù)，從而提高了算法效率。

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

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

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

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

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

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

4 結論

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

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

[1] 李鋒, 李曉艷. 圖的同構判定算法: 關聯(lián)度序列法及其應用[J]. 復旦學報(自然科學版), 2001.6, 318-325.

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

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

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

[5] 李鋒, 商慧亮. 有向圖的同構判定算法: 出入度序列法[J]. 應用科學學報, 2002.6, 258-262.

[6] 羅笑玲, 黃紹鋒, 歐陽天優(yōu), 等. 基于多分類器集成的圖像文字識別技術及其應用研究[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ù)結構的復雜對象建模設計[J]. 軟件, 2015, 36(12): 220-223.

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

[11] 胡一然, 宋中山, 孫翀, 等. NVSA: 一種具有可變節(jié)點值的查詢圖搜索算法[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àn)”，(閩教科〔2017〕76號，項目編號：JAT170897)

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

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