羅賢海，李 濤

（景德鎮(zhèn)陶瓷學院機電學院，江西 景德鎮(zhèn) 333403）

賦權(quán)混合圖的拓撲轉(zhuǎn)化與同構(gòu)判別

羅賢海，李 濤

（景德鎮(zhèn)陶瓷學院機電學院，江西 景德鎮(zhèn) 333403）

提出一種賦權(quán)混合圖的拓撲轉(zhuǎn)化方法，將混合圖的頂點度、權(quán)值、無向邊和有向邊用不同素數(shù)進行區(qū)分，用素數(shù)構(gòu)建一個描述混合圖邊方向的非對稱矩陣S，將用素數(shù)描述的權(quán)值矩陣的元素與S矩陣元素進行相乘，將該乘積與素數(shù)重新映射，該映射下的素數(shù)反映了賦權(quán)和混合圖邊方向的綜合信息，從而將賦權(quán)混合圖轉(zhuǎn)化為賦權(quán)無向圖，最后對鄰接矩陣動態(tài)修改法進行推廣以適用于賦權(quán)混合圖的同構(gòu)判別，判別實例表明該方法的有效性和可靠性。

賦權(quán)混合圖；無向邊；有向邊；拓撲轉(zhuǎn)化；同構(gòu)判別

0 引 言

圖的同構(gòu)判別是圖論中重要的理論問題之一，在相關領域的研究中均面臨圖的同構(gòu)判別，例如運動鏈綜合、化學中的同分異構(gòu)、模式識別、網(wǎng)絡分析等等。在應用中一般是先將實際問題用拓撲圖表示，然后根據(jù)圖論理論對拓撲圖進行分析。如何將實際問題轉(zhuǎn)化為拓撲圖，并用圖論方法描述拓撲結(jié)構(gòu)，是對拓撲圖同構(gòu)判別前首先要處理的問題。賦權(quán)混合圖是包含無向邊、有向邊和權(quán)值的圖，包含的信息比單純的無向圖、有向圖更多。對無向圖的同構(gòu)判別已有許多有價值的判別方法，相比之下對有向圖特別是混合圖的同構(gòu)判別的研究則較少。在圖的同構(gòu)判別中，利用出度和入度序列的有向圖同構(gòu)判別法[1]，考慮無向邊和有向邊的混合圖同構(gòu)判別的度序列法[2]?；旌蠄D同構(gòu)判別的電路模擬法[3]。利用頂點間具有一定長度的路徑數(shù)信息定義頂點不變量，提出了優(yōu)于常規(guī)的頂點同構(gòu)細分方法[4]。通過新增頂點并使用高效的必要條件提出一種無需回溯的同構(gòu)判別算法[5]。將每個頂點進行標記，通過一個權(quán)函數(shù)得到各個標簽的權(quán)數(shù)，利用權(quán)數(shù)序列進行同構(gòu)判別[6]。神經(jīng)網(wǎng)絡的圖同構(gòu)判別方法[7]。同構(gòu)判別的離散量子漫步法[8]。計算頂點間最小色差和最短路徑的同構(gòu)判別方法[9]。利用出入度序列或圖的其它恒量序列判別圖同構(gòu)，當兩圖同構(gòu)且恒量序列中有較多相同元素時，判別運算量是指數(shù)級復雜度，另一個問題是異構(gòu)的兩個圖也可能存在相同的恒量序列，因此利用恒量序列的同構(gòu)判別法往往失效或誤判，頂點細分法、電路模擬法、加強同構(gòu)的必要條件的同構(gòu)判別法仍然存在以上問題。利用素數(shù)構(gòu)造可同時反映局部及次級鄰接關系的鄰接矩陣，根據(jù)線性方程組解向量的分組情況對鄰接矩陣進行修改，提出了具有多項式計算復雜度的同構(gòu)判別的鄰接矩陣動態(tài)修改法[10]，并將該方法應用于含復合鉸的運動鏈同構(gòu)判別[11]。

1 賦權(quán)混合圖的拓撲轉(zhuǎn)化

本文提出一種混合圖拓撲描述方法，將賦權(quán)、無向邊、有向邊用素數(shù)及其乘積進行識別轉(zhuǎn)化，根據(jù)轉(zhuǎn)化結(jié)果形成鄰接矩陣，進而對鄰接矩陣動態(tài)修改法進行推廣以適用于賦權(quán)混合圖的同構(gòu)判別。設混合拓撲圖的頂點數(shù)為n，邊數(shù)為m，用集合P表示素數(shù)集合: P = {} = { 2 , 3 , 5 , 7 , . . . } 。

定義1 混合圖頂點號為i的度di是頂點i鄰接的邊的數(shù)目。記頂點度集合為D={di}={d1,d2,d3,...,dn}。定義2 混合圖邊賦權(quán)矩陣W= [wij]n××n為對稱矩陣，

將權(quán)值矩陣W中的元素wi′j≠0,1按數(shù)值相等分組，設共分為kw組，kwd≤ mm ， 每組元素用一個素數(shù)區(qū)分，i =1,2,...,k，規(guī)定＜＜＜...＜。w將權(quán)值矩陣W中不等于0和1的元素用對應的素數(shù)pw,i =1,2,...替換，形成新的用素數(shù)描述的權(quán)值i矩陣。定義3 用素數(shù)描述混合圖無向邊、有向邊的方向矩陣S=為：

式(2)中psps為兩個素數(shù)，規(guī)定＜＜，方12向矩陣S為非對稱矩陣。方向矩陣S 將有向邊轉(zhuǎn)化為賦權(quán)無向邊，有向圖傳統(tǒng)的描述是用正負數(shù)值表示出弧和入弧，但對于混合圖(既有無向邊又有有向邊)顯然不能用正負數(shù)值描述圖的出弧和入弧，而方向矩陣S則較好地解決了這一問題。

用傳統(tǒng)的鄰接矩陣難以描述賦權(quán)重邊或賦權(quán)混合重邊，本文利用素數(shù)乘積將賦權(quán)重邊或賦權(quán)混合重邊轉(zhuǎn)化為一條賦權(quán)無向邊，從而便于用鄰接矩陣描述。先將重邊數(shù)作為權(quán)值并用一個素數(shù)區(qū)分，例如圖1(a)、(b)的重邊數(shù)為3(權(quán)值3對應的素數(shù)為)，圖1中標注的、、等數(shù)值分別 為邊(i, j)之間的不等于1的賦權(quán)對應的素數(shù)和有向邊對應的素數(shù)，圖1(a)、(b)可以轉(zhuǎn)化為圖1(c)的一條賦權(quán)無向邊。其中圖1(a)轉(zhuǎn)化后的賦權(quán)為圖1(b)轉(zhuǎn)化后的賦權(quán)為：轉(zhuǎn)化后根據(jù) 重新形成矩陣。其它的重邊情況亦可按類似方法轉(zhuǎn)化。

圖1 賦權(quán)重邊、賦權(quán)混合重邊的轉(zhuǎn)化Fig.1 Weighted multiple-edge and weighted mixed multipleedge transform into weighted edge

除元素0、1外將矩陣H中元素按相等數(shù)值分組，設共分為k組，用k個素數(shù) ph,,i =1,2,...,k進dlhlhhil行區(qū)分，規(guī)定 pkd＜ p1＜ p2＜ ... ＜ pkl，并將矩陣H 元素(除0、1外)用對應的素數(shù)替換，最后得到混合圖的賦權(quán)與方向的綜合轉(zhuǎn)化矩陣,其中元素包含了邊的方向和權(quán)值信息，元素可以定義在鄰接矩陣中。矩陣H的元素包含了混合圖的無向邊、有向邊、賦權(quán)等綜合信息，通過與矩陣H 的元素有一一映射關系的矩陣H將賦權(quán)混合圖轉(zhuǎn)化為賦權(quán)無向圖處理。為了方便自動轉(zhuǎn)化，被分組的數(shù)值按從小到大排序，每組元素按數(shù)值大小依次按順序與素數(shù)集合P中的元素對應。

下面用一個混合圖說明上述拓撲轉(zhuǎn)化方法，圖2是一個包含無向邊、有向邊的賦權(quán)混合圖，圖2中(1, 2)、(1, 4)、(3, 2)邊為有向邊，其余邊為無向邊，其中(1, 2)、(2, 3)、(1, 3)邊的中部標上了權(quán)值，其它未標注邊的權(quán)值規(guī)定為1。

圖2 賦權(quán)混合圖Fig.2 Weighted mixed graphs

圖2的頂點度集合為D = {d1,d2,d3,d4}={3,2,3,2}，頂點度集合中元素共分為2組，即kd=2，分別用素數(shù)= 2 ，= 3 區(qū)分。根據(jù)定義2，圖2的權(quán)值矩陣W 為：

H 矩陣元素（除0、1外）共分為7組，即kl=7，H 矩陣中不等于0、1的元素分別用素數(shù)區(qū)分如下：

矩陣中元素與素數(shù)映射關系為：

混合圖拓撲轉(zhuǎn)化算法計算時間復雜性分析：轉(zhuǎn)化算法主要用到數(shù)值排序算法，頂點度排序算法復雜性為o(n log n)，權(quán)值矩陣W 排序算法運算量為o(m log m)，S 矩陣元素不需排序，形成H矩陣的乘法運算次數(shù)為o( n2)，建立H矩陣元素與素數(shù)映射的排序算法的運算量為o(n(n ? 1)log(n(n?1))，因此混合圖拓撲轉(zhuǎn)化算法總運算量最多為o( n3)。

2 混合圖同構(gòu)判別

同構(gòu)的兩個混合圖在判別時實際上需要找到以下映射關系，即：兩個混合圖的頂點與頂點保持映射，且保持無向邊映射到無向邊，有向邊映射到有向邊(尾部、頭部保持一致)，權(quán)值映射到權(quán)值，因此混合圖同構(gòu)判別相比無向圖的同構(gòu)判別更復雜。文獻[10]中提出了適用于一般無權(quán)無向圖同構(gòu)判別的鄰接矩陣動態(tài)修改方法，為了將鄰接矩陣動態(tài)修改法推廣到賦權(quán)混合圖的同構(gòu)判別，本文對文獻[10]鄰接矩陣A、進行改進。用頂點度對應的素數(shù)形成鄰接矩陣A=[aij]如下：

當圖的頂點最大度與最小度相差較大時，為了避免度較小的頂點的次級鄰接關系信息可能被削弱，因此對描述次級鄰接關系的矩陣A改進如下：

圖3 混合圖同構(gòu)判別流程Fig.3 The fow chart of isomorphism identifcation of weighted

圖4 改進后的矩陣修改流程Fig.4 The fow chart of further dynamic modifcation of adjacency matrix

圖5 圖同構(gòu)自動判別軟件主界面Fig.5 The main interface of isomorphism identifcation software of graphs

改進后的鄰接矩陣動態(tài)修改法的同構(gòu)判別時間復雜性分析：設矩陣修改次數(shù)為L，當拓撲圖同構(gòu)時，一般情況下建立同構(gòu)映射關系的矩陣修改次數(shù)1≤L＜n，其同構(gòu)判別運算量為o( L n3)，對于某些正則圖最壞情況下有 。當拓撲圖異構(gòu)時，一般情況下只需計算、的行列式或特征值各一次就可以得到兩圖異構(gòu)的結(jié)論，在圖3的判別流程就可以結(jié)束判別，無須進入矩陣修改流程，因此判別運算量為o( n3)，但是對于某些頂點度對應相等的部分同譜圖(初始矩陣、特征值對應相等的異構(gòu)圖)則需進入圖4的矩陣修改流程以判別其異構(gòu)，由于每次矩陣修改后，均能使得解向量X、Y內(nèi)獨立的元素增加，由圖4知，最壞的情況是矩陣修改后最終得到X=Y，但不能建立頂點和邊的雙射關系，這時矩陣修改次數(shù)n≤ L≤，其中n1為解向量初次分組的組內(nèi)元素個數(shù)，，一般取n1最小的一組。因此對于某些同譜圖最壞情況下判別為異構(gòu)的運算量為 o ( n5) 。

深入的研究表明，當拓撲圖異構(gòu)時鄰接矩陣動態(tài)修改法能在多項式時間復雜度內(nèi)給出異構(gòu)的結(jié)果。對同構(gòu)的拓撲圖也進行了大量的同構(gòu)判別實例驗證，實例中圖的最大頂點數(shù)達到1 000個，邊數(shù)達到20 000條，驗證方法是將隨機產(chǎn)生的拓撲圖G(A)復制到拓撲圖G(B)，然后將拓撲圖G(B)的頂點號進行隨機排列，驗證結(jié)果表明均能在多項式時間復雜度內(nèi)找到同構(gòu)的雙射關系。

3 同構(gòu)判別實例

應用改進后的鄰接矩陣動態(tài)修改法，能有效對一般無向圖、賦權(quán)混合圖進行同構(gòu)判別，下面給出3個判別實例，判別實例中，取q=1.5。

判別實例1：圖6 是兩個16節(jié)點32條邊的混合圖，圖6(a)、(b)中的邊(8, 12)、(8, 13)、(13, 16)、(14, 15)為無向邊，其余為有向邊，邊(3, 12)、(9, 16)為賦權(quán)邊，權(quán)值均為4，其它未賦權(quán)的邊權(quán)值為1。計算得到 d e t ()=-10694.9620，de t ()=-10695.5351，det()≠det()兩個圖異構(gòu)。

圖6 判別實例1Fig.6 Example 1

圖7 判別實例2Fig.7 Example 2

表1 圖8的拓撲圖同構(gòu)標號映射Tab.1 The label mapping of the topological graph in Fig.8

判別實例3：圖8 是兩個20節(jié)點30條邊的混合圖，其中圖8(a)的邊(1, 17)、(5, 12)、(7, 19)為無向邊，其余為有向邊，邊(1, 14)、(3, 11)、(5, 15)的賦權(quán)分別為3、2.5、3.5。圖8(b)的邊(7, 15)、(6, 17)、(1, 13)為無向邊，其余為有向邊，邊(15, 18)、(4, 16)、(6, 12)的賦權(quán)分別為3、2.5、3.5，其它未賦權(quán)的邊權(quán)值為1。用改進后的鄰接矩陣動態(tài)修改法經(jīng)一次判別得到兩個混合圖同構(gòu)，且得到同構(gòu)的頂點標號映射關系見表1。容易驗證圖8(a)、(b)的無向邊、有向邊、權(quán)值也保持了映射。

4 結(jié) 論

針對傳統(tǒng)的鄰接矩陣難以描述包含無向邊和有向邊的賦權(quán)混合圖問題，提出了用素數(shù)及其乘積識別頂點度、權(quán)值、有向邊方向，將賦權(quán)混合圖轉(zhuǎn)化為賦權(quán)無向圖，由于素數(shù)具有唯一性，且素數(shù)乘積具有可逆性，因此利用素數(shù)能對混合圖進行拓撲轉(zhuǎn)化，用轉(zhuǎn)化結(jié)果形成的矩陣能對混合圖進行拓撲描述，轉(zhuǎn)化方法也適用于一般賦權(quán)無向圖和一般賦權(quán)有向圖，對于頂點包含混合自環(huán)（逆時針自環(huán)、順時針自環(huán)和無向環(huán)）的情況，只要將三種自環(huán)也用不同的素數(shù)區(qū)分，將該素數(shù)與頂點度對應的素數(shù)相乘，該乘積與素數(shù)重新進行映射即可區(qū)分頂點類型，因此本文的轉(zhuǎn)化方法也適用于包含混合自環(huán)的混合有向圖，另外轉(zhuǎn)化方法也適用于頂點賦權(quán)。轉(zhuǎn)化算法在同構(gòu)判別前一次完成。最后改進了鄰接矩陣動態(tài)修改法以適用于賦權(quán)混合圖的同構(gòu)判別，判別實例表明了本文方法的有效性和可靠性，判別方法同樣適用于一般正則圖、強正則圖以及同譜圖的同構(gòu)判別，且同構(gòu)判別時間復雜度為多項式。

[1] 李鋒, 商慧亮. 有向圖的同構(gòu)判定算法: 出入度序列法[J]. 應用科學學報, 2002, 20(3): 258-262.

LI Feng, et al. Journal of Applied Sciences, 2002, 20(3): 258-262.

[2] 臧威, 李鋒. 混合圖的同構(gòu)判定算法：度序列法[J]. 計算機應用與軟件, 2008, 25(3): 198-200.

ZANG Wei, et al. Computer Applications and Software, 2008, 25(3): 198-200.

[3] SHANG Huiliang, LIU Yang, CHEN Xiong, et al. The optimized circuit simulation method for isomorphism determination of mixed graphs. Journal of Bionanoscience, 2013, 7(1): 97-103.

[4] 鄒瀟湘, 戴瓊. 圖同構(gòu)中的一類頂點細分方法[J]. 軟件學報, 2007, 18(2): 213-219.

ZOU Xiaoxiang, et al. Journal of Software, 2007, 18(2): 213-219.

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

HOU Aimin, et al. Journal of South China University of Technology(Natural Science Edition), 2011, 39(10): 79-83.

[6] WEBER M, LIWICKI M, DENGEL A. Faster subgraph isomorphism detection by well-founded total order indexing[J].Pattern Recognition Letters, 2012, 33(15): 2011-2019.

[7] JAIN B J, WYSOTZKI F. Solving inexact graph isomorphism problems using neural networks[J]. Neurocomputing, 2005, 63: 45-67.

[8] BERRY S D, WANG J B. Two-particle quantum walks: entanglement and graph isomorphism testing[J]. Physical Review A, 2011, 83(4): 042317-1-042317-12.

[9] DE OLIVEIRA OLIVEIRA M, GREVE F. A new refinement procedure for graph isomorphism algorithms[J]. Electronic Notes in Discrete Mathematics, 2005, 19: 373-379.

[10] 羅賢海. 機構(gòu)運動鏈鄰接矩陣的素數(shù)表示與同構(gòu)判別[J]. 機械工程學報, 2013, 49(5): 24-31.

LUO Xianhai. Journal of Mechanical Engineering, 2013, 49(5): 24-31.

[11] 羅賢海, 李亮臻, 李濤. 含復合鉸機構(gòu)運動鏈的拓撲圖表示與同構(gòu)判別[J]. 機械設計與制造, 2014, 3: 247-250.

LUO Xianhai, et al. Machinery Design & Manufacture, 2014, 3: 247-250.

Topology Transformation and Isomorphism Identifcation of Weighted Mixed Graphs

LUO Xianhai, LI Tao
(School of Mechanical & Electronic Engineering, Jingdezhen Ceramic Institute, Jingdezhen 333403, Jiangxi, China)

A new method is used to transform the topological information of mixed graphs. The primes represent vertex degree, weights, undirected edges, and directed edges of mixed graphs. One weighted matrix is constructed by some primes with weights while another asymmetrically matrix S is also constructed by other primes with undirected and directed edges. Furthermore, the product of elements of two matrices is mapped onto new primes to synthesize information of weights and edges. Hence, weighted mixed graphs are transformed into weighted undirected graphs in application to isomorphism identifcation of weighted mixed graphs by further dynamic modifcation of adjacency matrix. More examples verify the availability and reliability of prime classifcation and isomorphism identifcation.

weighted mixed graphs; undirected edge; directed edge; topology transformation; isomorphism identifcation

date: 2014-04-27. Revised date: 2014-05-10.

TQ174.5

A

1000-2278(2014)04-0419-06

10.13957/j.cnki.tcxb.2014.04.015

2014-04-27。

2014-05-10。

江西省自然科學基金(編號：2010GZC0087)；

江西省教育廳科技計劃(編號：GJJ12491)資助項目。

羅賢海(1965－)，男，博士，教授。

Correspondent author:LUO Xianhai(1965-), male, Ph. D., Professor.

E-mail:Lxh9031@163.com