图同构

图同构(Graph Isomorphism)描述的是图论中，两个图之间的完全等价关系。在图论的观点下，两个同构的图被当作同一个图来研究。

实用解法

与理论研究主要关注计算复杂度不同，对实用解法的研究主要关注具体应用中的实践计算速度。P/NP问题只关注时间复杂度中的指数，而不关注其系数大小。即使一个算法是多项式时间的，它也可能因的系数过大导致的速度太慢及/或数值上不稳定，而在实践中根本没有用处；反之，一个优秀的实用解法，即使不能保证是多项式时间的，在很多应用上也可能比一些多项式时间的解法快得多。
在图同构问题上，目前处于领先性能的实用解法是由澳大利亚计算机科学家Brendan McKay在1980年代提出的NAUTY，其对每一个图估计其节点的一个标准索引排列(Canonical Indexing，或称Canonical Labeling)。标准索引可以非常耗时，而NAUTY算法通过探索图的自同构性群的性质，对索引步骤进行剪枝，大大加快了标准索引的计算速度。NAUTY自从提出以来，成为了几乎每一篇研究图同构和图匹配问题实用解法的论文必定要进行比较的竞争对手。
其它流行的方法包括：各色启发式算法；对QAP约化进行SDP松弛；近似计算图之间的某种不依赖于节点顺序的距离，例如图之间的编辑距离和cut distance等，这些距离的精确计算通常是NP困难的。