图同构判定与双射函数相关技术咨询

咱们先设定这样一个场景：有两个手镯，每个手镯上都串了$8$颗珍珠，珍珠的颜色序列完全相同，但珍珠的标注序列不一样。如果把珍珠看作图的顶点，手镯的周长看作图的边，那这两个手镯就对应两个无向图$G_1$和$G_2$。

问题1 #

我觉得这两个图应该是同构的，因为它们的顶点数、边数、连通性这些性质都一样，而且我想不出有什么性质是不一样的。我这个想法对吗？

问题2 #

图同构的定义是存在一个双射函数$f: V(G_1) \to V(G_2)$。既然这是个函数，那是不是意味着我们能写出一个公式来根据$G_1$里的顶点得到$G_2$里对应的顶点呢？

问题1解答 #

你这个判断完全正确！这两个图确实是同构的。图同构的核心是结构完全一致：两个图的顶点数、边数相同，顶点之间的邻接关系也完全匹配。这里两个手镯对应都是8个顶点的环图$C_8$，珍珠颜色序列相同意味着顶点的属性（如果把颜色当作顶点属性）也能一一对应，只是标注不同而已。你找不到任何不一样的图论性质，这正好说明它们满足同构的所有条件。

问题2解答 #

首先要明确一个关键点：存在这样的双射函数，不代表一定能写出简洁的“公式”。

举个直观的例子：如果两个手镯的珍珠标注只是做了循环移位（比如$G_1$的标注是1,2,...,8，$G_2$的标注是3,4,...,8,1,2），那我们很容易写出对应的公式，比如$f(v) = (v+2) \mod 8$（假设标注是连续数字）。但如果标注是完全随机打乱的——比如$G_1$的顶点A对应$G_2$的顶点5，$G_1$的顶点B对应$G_2$的顶点2，完全没有规律——那这个双射确实存在，但你没法用一个简单的代数公式或者规则来描述它，只能通过一一列举的方式来定义这个函数。

简单来说，图同构只要求存在这样的双射来保持邻接关系，不管这个双射能不能用“公式化”的方式表达出来。只要能找到任意一种方式（哪怕是枚举）建立顶点之间的一一对应，并且保证相邻的顶点在映射后依然相邻，那这个双射就符合图同构的要求。

备注：内容来源于stack exchange，提问作者madhurkant