定义
如果两个图具有相同的顶点数、边数以及相同的边连通性，这样的两个图完全等价，被称为同构图[1]。如下图1所示，左右两侧图属于同构图：
图 1 同构图
图同构的问题一般可以分为四个不同的研究类型：精确图完全同构、精确子图同构、不精确图完全同构、不精确子图同构。
与图同构问题类似的是图匹配问题，图匹配(graph matching)是判断两个图是否同构，如果同构，找出至少一个使得两者做成同构的节点间的一一对应关系。图同构和图匹配问题的计算负责度都属于NP问题[2]，近期有很多学者就计算复杂度的挑战提出一系列的近似方法[3]。
参考文献
[1] McKay B D. Practical graph isomorphism[J]. 1981.
[2] László Babai. Groups, Graphs, Algorithms: The Graph Isomorphism Problem. ICM 2018.
[3] Lyzinski, Vince, Information Recovery in Shuffled Graphs via Graph Matching, 2016, arXiv:1605.02315.
