关于图同构复杂性的分析  

Analysis on Complexity of Graph Isomorphism Problem

作　　者：戴琼[1] 邹潇湘[2] 谭建龙[3] 

机构地区：[1]中国科学院软件研究所,北京100080 [2]国家计算机网络与信息安全管理中心,北京100029 [3]中国科学院计算技术研究所,北京100080

出　　处：《计算机科学》2006年第11期219-221,共3页Computer Science

基　　金：中科院计算所青年基金课题20056600-4支持

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

关 键 词：图同构 NP问题 P问题 NPC问题 图同构完备 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]