主题
Search

图同构完备

对于图同构测试，目前还没有已知的 P 算法，尽管该问题也未被证明是 NP 完全 的。事实上，如果 P 和 NP 完全之间存在裂缝（Skiena 1990，第 181 页），那么识别同构图的问题似乎就落在这个裂缝中。因此，这个问题有时被归类为一个特殊的图同构完备复杂度类。

另请参阅

复杂度理论, 图同构, 同构图, NP 完全问题, P 问题

使用 Wolfram|Alpha 探索

参考文献

Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, pp. 155-156, 1983.Skiena, S. "Graph Isomorphism." §5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 181-187, 1990.

在 Wolfram|Alpha 上被引用

图同构完备

引用为

Weisstein, Eric W. "Graph Isomorphism Complete." From MathWorld--A Wolfram Web Resource. https://mathworld.net.cn/GraphIsomorphismComplete.html

主题分类