CAJ | 학술논문

图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注.在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法.本文对此进行了讨论,并给出了一些反例来证明其算法的错误.根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究.
도동구문제시지대량개도심조정점지간적일개일일영사,사득량도적변재해영사하야보지대응관계,해문제득도허다연구자적관주.재일사논문중대도동구문제적복잡성급출료착오적묘술,유적급출료다항식시간산법.본문대차진행료토론,병급출료일사반례래증명기산법적착오.근거도동구국내외목전적연구진전,도동구기미피귀입P문제,야미피귀입NPC문제,시일개상미해결적문제,유대진일보연구.