賦權混合圖的拓撲轉化與同構判別

羅賢海，李 濤

（景德鎮陶瓷學院機電學院，江西 景德鎮 333403）

賦權混合圖的拓撲轉化與同構判別

羅賢海，李 濤

（景德鎮陶瓷學院機電學院，江西 景德鎮 333403）

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

賦權混合圖；無向邊；有向邊；拓撲轉化；同構判別

0 引 言

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

1 賦權混合圖的拓撲轉化

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

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

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

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

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

圖1 賦權重邊、賦權混合重邊的轉化Fig.1 Weighted multiple-edge and weighted mixed multipleedge transform into weighted edge

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

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

圖2 賦權混合圖Fig.2 Weighted mixed graphs

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

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

矩陣中元素與素數映射關系為：

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

2 混合圖同構判別

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

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

圖3 混合圖同構判別流程Fig.3 The fow chart of isomorphism identifcation of weighted

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

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

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

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

3 同構判別實例

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

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

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

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

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

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

4 結 論

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

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

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

[2] 臧威, 李鋒. 混合圖的同構判定算法：度序列法[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] 鄒瀟湘, 戴瓊. 圖同構中的一類頂點細分方法[J]. 軟件學報, 2007, 18(2): 213-219.

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

[5] 侯愛民, 郝志峰, 胡傳福, 等. 無向圖同構的快速算法[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] 羅賢海. 機構運動鏈鄰接矩陣的素數表示與同構判別[J]. 機械工程學報, 2013, 49(5): 24-31.

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

[11] 羅賢海, 李亮臻, 李濤. 含復合鉸機構運動鏈的拓撲圖表示與同構判別[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