赋权混合图的拓扑转化与同构判别_罗贤海.pdfVIP

第 35 卷 第 4 期 Vol.35 No.4 Journal of Ceramics · 419 · 2014 年 8 月 Aug. 2014 第 35 卷 第 4 期 DOI：10.13957/ki.tcxb.2014.04.015 赋权混合图的拓扑转化与同构判别 罗贤海，李 涛 （景德镇陶瓷学院机电学院，江西 景德镇 333403） 摘 要：提出一种赋权混合图的拓扑转化方法，将混合图的顶点度、权值、无向边和有向边用不同素数进行区分，用素数构 建一个描述混合图边方向的非对称矩阵S，将用素数描述的权值矩阵的元素与S矩阵元素进行相乘，将该乘积与素数重新映 射，该映射下的素数反映了赋权和混合图边方向的综合信息，从而将赋权混合图转化为赋权无向图，最后对邻接矩阵动态修 改法进行推广以适用于赋权混合图的同构判别，判别实例表明该方法的有效性和可靠性。 关键词：赋权混合图；无向边；有向边；拓扑转化；同构判别 中图分类号：TQ174.5 文献标志码：A 文章编号：1000-2278(2014)04-0419-06 Topology Transformation and Isomorphism Identification of Weighted Mixed Graphs LUO Xianhai, LI Tao (School of Mechanical Electronic Engineering, Jingdezhen Ceramic Institute, Jingdezhen 333403, Jiangxi, China) Abstract: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 identification of weighted mixed graphs by further dynamic modification of adjacency matrix. More examples verify the availability and reliability of prime classification and isomorphism identification. Key words:weighted mixed graphs; undirected edge; directed edge; topology transformation;