摘要
给出一个源于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.
出处
《计算机与现代化》
2013年第4期18-21,共4页
Computer and Modernization
基金
四川省科技厅应用基础研究重点项目(2011JY032)
阿坝师范高等专科学校校级重点科研资助项目(ASA11-26)
关键词
有向图
多重图
子图
结点度数
同构
Ulam猜想
digraph
multigraph
subgraph
vertex valency
isomorphism
Ulam conjecture
