摘要
判定两个图是否同构的算法复杂性至今还是一个开问题。作者研究一类图的同构问题,给出了K-可区分图及K-标准图的定义〔0<K<n,K∈Z〕。并且讨论了1-可区分图的结构和性质,利用其结构和性质可以证明:1-可区分图的同构判定问题可以在O(n2)时间内完成。
The algorithmic complexity of the decision problem for graph isomorphism remains a open question at present. In order to research the isomorphism problem of certain graphs, we defineK-divisive graphs and K-standard standard graphs, and research the structure and property of 1-divisive graphs. We have proved that the decision problem of isomorphism for 1-divisive graphs can be decided in O（n^2） time.
出处
《贵州大学学报（自然科学版）》
2007年第3期229-233,共5页
Journal of Guizhou University:Natural Sciences
关键词
图同构
K-可区分图
K-标准图
graph isomorphism
K-divisive graph
K-standard graph
