设 
为 简单图 的 顶点集，
为其 边集。那么从 简单图 
到 简单图 
的图同构是一个 双射 
，使得 
当且仅当 
(West 2000, p. 7)。
如果存在从 
到 
的图同构，则称 
与 
同构，记作 
。
目前还没有已知的 P 算法用于图同构测试，尽管该问题也未被证明是 NP-完全 的。因此，特殊的复杂度类 图同构完全 有时被用来指代图同构测试问题。
图同构
另请参阅
图自同构, 图同构完全, 同构, 同构图, 同构使用 探索
参考文献
Du, D.-Z. 和 Ko, K.-I. Theory of Computational Complexity. New York; Wiley, p. 117, 2000.Garey, M. R. 和 Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, pp. 155-156, 1983.McKay, B. "Practical Graph Isomorphism." Congr. Numer. 30, 45-87, 1981.Skiena, S. "Graph Isomorphism." §5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 181-187, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.在 中被引用
图同构请引用为
Weisstein, Eric W. “图同构。” 来自 Web 资源。 https://mathworld.net.cn/GraphIsomorphism.html