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

Abstract: 给出一个源于Ulam猜想的图同构的定理，基于该定理得到的同构算法可以借助子图的结点度数来寻找结点间的对应关系。对结点度数重复率不高的图可以极大减少其同构判定的时间复杂度。

Key words: 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 valency. Especially, this algorithm can reduce the time complexity for determining graphs isomorphism obviously within some graphs that have minor repeatability of vertex valency.