赋权混合图的拓扑转化与同构判别

罗贤海，李 涛

（景德镇陶瓷学院机电学院，江西 景德镇 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