摘要
图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注。在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法。本文对此进行了讨论,并给出了一些反例来证明其算法的错误。根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究。
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.
出处
《计算机科学》
CSCD
北大核心
2006年第11期219-221,共3页
Computer Science
基金
中科院计算所青年基金课题20056600-4支持
关键词
图同构
NP问题
P问题
NPC问题
图同构完备
Graph isomorphism, NP problem, P problem, NPC problem, Graph isomorphism complete
