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