有向图和多重图同构判定的一个优化方案  

An Optimization Scheme for Determining Isomorphism of Digraphs or Multigraphs

作　　者：谢科[1] 吴文权[1] 

机构地区：[1]阿坝师范高等专科学校计算机科学系,四川汶川623002

出　　处：《绵阳师范学院学报》2013年第5期71-73,共3页Journal of Mianyang Teachers＇ College

基　　金：四川省科技厅应用基础研究重点项目(2011JY032);阿坝师专校级科研基金规划项目(ASB10-07)

摘　　要：给出了有向图或多重图同构的一个必要条件.通过先将有向图或多重图转换为无向图,根据其邻接矩阵不等于零的特征根数量和符号差是否相等来判定其是否合同,进而判定其是否同构,由无向图的同构情况,排除某些有向图或多重图的同构可能.该方法可以优化有向图或多重图同构的判定过程.This paper gives one of the necessary conditions for determining digraphs or multigraphs isomorphism.Converting the digraphs or multigraphs to non-directional graphs at first,then judging whether they are congruent which based on the result that the number of non-zero characteristic roots and signatures of their adjacency matrixes are equivalent or not.Finally determining whether the non-directional graphs are isomorphic and excluding isomorphic probability of some digraphs and multi-graphs according to the isomorphism situation of non-directional graphs.This scheme can optimize the decision process for isomorphism of digraphs or multi-graphs efficiently.

关 键 词：有向图 多重图 同构 邻接矩阵 不等于零的特征根 

分 类 号：O157[理学—数学]