陳中標

（無錫科技職業(yè)學(xué)院，江蘇 無錫214000）

非正則圖同構(gòu)的算法改進及分析

陳中標

（無錫科技職業(yè)學(xué)院，江蘇 無錫214000）

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

圖同構(gòu);鄰接矩陣;關(guān)聯(lián)度;算法

引言

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

1 圖同構(gòu)的有關(guān)概念

定義1[1]如果兩個圖G1與G2的點之間一一對應(yīng),邊之間一一對應(yīng),而且對應(yīng)點與對應(yīng)邊之間保持相同的關(guān)聯(lián)關(guān)系,那么G1與G2同構(gòu),記作G1≌G2。

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

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

2 圖同構(gòu)的判定方法

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

例1判斷圖1和圖2是否同構(gòu)。

圖1

圖2

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

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

故圖1與圖2是同構(gòu)的。

3 非正則圖同構(gòu)的改進算法

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

3.1 非正則圖同構(gòu)的算法步驟

設(shè)有兩圖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個頂點的度數(shù),表示對相同度的頂點的編號,若i=i+1，則j=j+1，否則置j=1。

第二步:若i=1或兩圖的編號Vij≠V'ij,則兩圖不同構(gòu),退出.否則轉(zhuǎn)第三步.

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

建設(shè)智慧校園旨在推動下一代數(shù)字技術(shù)在智慧校園建設(shè)中的創(chuàng)新應(yīng)用，改造和優(yōu)化現(xiàn)行校園網(wǎng)絡(luò)環(huán)境，構(gòu)建高速泛在、智能靈活、開放共享、安全可靠的校園信息環(huán)境。2015年以來，學(xué)校啟動了智慧校園建設(shè)，并將智慧校園建設(shè)列入學(xué)?！笆濉币?guī)劃重點項目，設(shè)立智慧校園建設(shè)專職系統(tǒng)集成、軟件研發(fā)和推廣團隊，保障智慧校園試點項目順利實施。

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

例2用4.1方法判定例1中兩圖是否同構(gòu)。

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

圖3

圖4

例3給出以下兩圖,圖4、圖5,判斷兩圖是否同構(gòu)。

圖5

圖6

解:以上兩圖的頂點數(shù)有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交換位置,寫出相應(yīng)的新的鄰接矩陣A（D），若A（D）≠A'（D），再交換V31與V32位置重新編號，寫出相應(yīng)的新的鄰接矩陣A（D），若A（D）≠A'（D），根據(jù)算法停止編號,判定圖5與圖6是不同構(gòu)的。

3.2 算法分析

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

4 總結(jié)

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

注釋及參考文獻：

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

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

[3]陳曉紅,王敏麗．關(guān)于圖的同構(gòu)判定方法的探討[J]．大學(xué)數(shù)學(xué),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-)，男，江蘇鹽城人，講師，主要從事計算機科學(xué)教學(xué)研究。