非正則圖同構的算法改進及分析

陳中標

（無錫科技職業學院，江蘇 無錫214000）

非正則圖同構的算法改進及分析

陳中標

（無錫科技職業學院，江蘇 無錫214000）

對于非正則圖的同構問題,給出了新的判定方法,并且對該方法的復雜度進行了簡單的分析,最后用實例證明新方法比以往的方法簡單方便。

圖同構;鄰接矩陣;關聯度;算法

引言

圖的同構判定問題是圖論學科的基本問題之一。所謂圖的同構,簡單地說,就是兩個圖的結構完全相同。以往人們用圖的關聯矩陣相同或鄰接矩陣相同來判定任意兩圖是否同構。但是,若圖的頂點序號標記不同,則其本身就會產生不同個關聯矩陣、鄰接矩陣,此時，當兩圖的頂點數量較多時,要比較該兩圖是否同構,計算起來相當復雜。本文針對非正則圖的同構問題,給出改進的算法步驟并且對其算法進行簡單的分析,最后用實際例子進行驗證,結果表明改進的算法比以往的算法簡單。

1 圖同構的有關概念

定義1[1]如果兩個圖G1與G2的點之間一一對應,邊之間一一對應,而且對應點與對應邊之間保持相同的關聯關系,那么G1與G2同構,記作G1≌G2。

定義2[2]頂點的度全相等的圖稱為正則圖。

定理1[2]圖G1與G2同構當且僅當對某一頂點的順序,它們的鄰接矩陣相同。

2 圖同構的判定方法

以往人們常用以下方法來判斷任意兩圖是否同構[3]:首先寫出兩個圖G1與G2的鄰接矩陣或者關聯矩陣A1與A2;然后分別對A1和A2的行、列進行初等變換,若能使A1=A2,則判定G1≌G2，否則G1不同構與G2。筆者對以上方法進行簡單的分析,若對所有可能的行、列交換意味著行的全排列與列的全排列，所以行、列交換的總次數將達到n！m！（n為圖頂點數，m為邊數）。若n、m都比較大時，計算起來相當復雜。

例1判斷圖1和圖2是否同構。

圖1

圖2

解：分別寫出圖1和圖2的鄰接矩陣,記作A（D）和B（D），則

,雖然A（D）和B（D）含有相同個數的0,相同個數的2,但也不能表明它們就是同構的,因此要對A（D）或B（D）進行初等變換,經變換后看是否有與對方完全相同的矩陣。第一步:A（D）中第一行與第二行交換位置;第二步:第三行與第五行交換位置;第三步:第一列與第二列交換位置;第四步:第三列與第五列交換位置,經過一系列交換得

故圖1與圖2是同構的。

3 非正則圖同構的改進算法

在以往判斷兩圖是否同構的過程中,需要對其生成的矩陣進行行、列交換,然后根據交換后的矩陣是否相同來判定兩圖是否同構。構成算法的復雜是因為兩圖中的頂點的順序不同,即度序列不同,導致重復計算。若能合理的給頂點進行編號,有時直接就可以判斷兩圖是否同構,這樣就可以減少冗余計算,給計算帶來方便。下面給出非正則圖的同構判定的新的算法。

3.1 非正則圖同構的算法步驟

設有兩圖G1與G2,頂點分別為Vij、V'ij（i=0，1，2，…；j=0，1，2，…）,鄰接矩陣分別記為A（D）和A'（D）。

第一步:對兩圖按度序列進行不減排序并且編號,記作Vij、V'ij（i=0，1，2，…；j=0，1，2，…）。i表示第n個頂點的度數,表示對相同度的頂點的編號,若i=i+1，則j=j+1，否則置j=1。

第二步:若i=1或兩圖的編號Vij≠V'ij,則兩圖不同構,退出.否則轉第三步.

第三步:若Vij＝V'ij,則寫出相應的鄰接矩陣,記作A（D）和A'（D），若A（D）＝A'（D）,則兩圖同構。

建設智慧校園旨在推動下一代數字技術在智慧校園建設中的創新應用，改造和優化現行校園網絡環境，構建高速泛在、智能靈活、開放共享、安全可靠的校園信息環境。2015年以來，學校啟動了智慧校園建設，并將智慧校園建設列入學校“十三五”規劃重點項目，設立智慧校園建設專職系統集成、軟件研發和推廣團隊，保障智慧校園試點項目順利實施。

第四步:若A（D）≠A'（D），則對i相同的標號中,交換j的順序,重新編號，并且給出相應的鄰接矩陣,若所有的j都交換順序后A（D）≠A'（D），則兩圖不同構,否則轉第三步.

例2用4.1方法判定例1中兩圖是否同構。

解:按4.1算法對圖1、圖2進行編號,得到以下圖3、圖4,如圖所示,經過編號后的圖3、圖4,不必計算就可以直接判斷兩圖是同構的。

圖3

圖4

例3給出以下兩圖,圖4、圖5,判斷兩圖是否同構。

圖5

圖6

解:以上兩圖的頂點數有6個,如果用以往的算法難度較大,按4.1算法對兩圖分別進行編號,Vij、V'ij（i=0，1，2，…；j=0，1，2，…），然后分別寫出它們的鄰接矩陣A（D）和A'（D），

重新編號,圖5中V11與V12交換位置,如圖7所示。

圖7

寫出新的鄰接矩陣

再重新編號，V21與V22交換位置,寫出相應的新的鄰接矩陣A（D），若A（D）≠A'（D），再交換V31與V32位置重新編號，寫出相應的新的鄰接矩陣A（D），若A（D）≠A'（D），根據算法停止編號,判定圖5與圖6是不同構的。

3.2 算法分析

該非正則圖同構的新算法，主要在于對兩圖編號后,若得到Vij＝V'ij，則說明它們有相同的頂點個數及相同度數的頂點數，該條件已經滿足了圖同構的定理1條件。然后分別寫出兩圖的鄰接矩陣后,不同的地方就在相同度數的頂點的編號順序,因此只要對相同度數頂點的編號進行重新排序即可。若圖有n個頂點m條邊,則只需進行計算m！次,而以往需要n！m！。若n、m都比較大時，計算復雜度的差距是非常大的。在該新算法的使用過程中,若m較小,直接筆算就可得出結論,若m較大時,計算起來還是有一定的難度,此時我們可以借助計算機來實現。

4 總結

以上圖的同構的判定方法只是針對于非正則圖而言的,而對于正則圖的同構的判定還沒有更好的方法，因此如何判斷兩正則圖是否同構是我們繼續要努力的目標！

注釋及參考文獻：

[1]耿素云,屈婉玲,張立昂．離散數學[M]．北京:清華大學出版社,2004:59．

[2]范益政,汪毅,龔世才,等．圖論引導[M]．北京:人民郵電出版社,2007:102．

[3]陳曉紅,王敏麗．關于圖的同構判定方法的探討[J]．大學數學,2006,2(2):75-77．

The Improvement andAnalysis of the Regular Graph IsomorphismAlgorithm

CHEN Zhong-Biao
(Wuxi Technology and Professional College,Wuxi,Jiangsu 214000)

A new decision method for non regular graph isomorphism problem is given in this article which also analysis its complexity.Finally,an example is used to prove this methed is simple and convenient than before.

graph isomorphism;adjacency matrix;correlation;algorithm

0157．5

A

1673-1891（2015）01-0025-03

2014-10-29

陳中標(1981-)，男，江蘇鹽城人，講師，主要從事計算機科學教學研究。