什么是图同构问题？

图论中的图（graph）是由顶点（vertex）和边（edge）组成的组合结构。用于建模现实世界时，一般用顶点表示各种对象，用边表示对象之间的关系。比如人与人之间的校友关系构成一个图，数学家之间的合作关系构成一个图，国家之间的建交关系，城市之间的道路连通关系，等等。
 
两个图同构，最浅显的理解就是这两个图「一样」。举个简单的例子： A 是 B 的朋友，B 是 C 的朋友，A 与 C 却不认识；中俄接壤、中越接壤，俄越不接壤。那么 ABC 三人的朋友关系图，与中俄越的接壤关系图，就是同构的：A 对应俄、B 对应中，C 对应越。
 
图同构问题，就是如何判定两个图同构。如果我们能高效的做这样的判定，那就意味着我们能快速识别两个相同的组合结构。很明显，这对于图像识别、数据检索（特别是化学领域）、复杂结构的分析挖掘等，都有重大意义。这些当然会给「普通人」的生活带来巨大改善……虽然「普通人」是不需要知道什么是图同构问题的。
 
图同构目前为止还没有高效的算法。我们甚至不知道图同构问题有多难，是不是 P 问题。但是下周二（2015 年 11 月 10 日）可能会有一个准多项式算法公布。