关于图同构复杂性的分析

图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注。在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法。本文对此进行了讨论,并给出了一些反例来证明其算法的错误。根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究。

Analysis on Complexity of Graph Isomorphism Problem

The graph isomorphism is to find a bijection between the vertexes of two graphs that preserve the edges. This problem has been paid much attention by many researchers. In some papers the complexity of the graph problem has been wrong described, and polynomial time algorithm is given. In this paper, we discuss that algorithm. Some examples are proposed to show the error of that algorithm. Graph isomorphism problem is one of the problems that have not been classified as NP complete, or within P. So it is an open problem until now and need further studies.