基于子图结点度数相异的图同构判定方法  

A Method for Determining Two Graphs' Isomorphism Based on Dissimilarity of Subgraphs' Vertex Valency

作　　者：谢科[1] 吴文权[1] 刘洪江[1] 

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

出　　处：《计算机与现代化》2013年第4期18-21,共4页Computer and Modernization

基　　金：四川省科技厅应用基础研究重点项目(2011JY032);阿坝师范高等专科学校校级重点科研资助项目(ASA11-26)

摘　　要：给出一个源于Ulam猜想的图同构的定理,基于该定理得到的同构算法可以借助子图的结点度数来寻找结点间的对应关系。对结点度数重复率不高的图可以极大减少其同构判定的时间复杂度。This paper gives a theorem for graphs isomorphism that originates from the Ulam conjecture. Based on this theorem, the algorithm for determining graphs isomorphism can find out the bijection of vertexes by comparing the subgraphs＇ vertex valen- cy. Especially, this algorithm can reduce the time complexity for determining graphs isomorphism obviously within some graphs that have minor repeatability of vertex valency.

关 键 词：有向图 多重图 子图 结点度数 同构 Ulam猜想 

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