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

陳中標(biāo)

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

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

陳中標(biāo)

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

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

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

引言

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

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

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

定義2[2]頂點(diǎn)的度全相等的圖稱為正則圖。

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

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

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

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

圖1

圖2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3

圖4

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

圖5

圖6

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

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

圖7

寫出新的鄰接矩陣

再重新編號(hào)，V21與V22交換位置,寫出相應(yīng)的新的鄰接矩陣A（D），若A（D）≠A'（D），再交換V31與V32位置重新編號(hào)，寫出相應(yīng)的新的鄰接矩陣A（D），若A（D）≠A'（D），根據(jù)算法停止編號(hào),判定圖5與圖6是不同構(gòu)的。

3.2 算法分析

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

4 總結(jié)

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

注釋及參考文獻(xiàn)：

[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

陳中標(biāo)(1981-)，男，江蘇鹽城人，講師，主要從事計(jì)算機(jī)科學(xué)教學(xué)研究。