图同构是计算机科学中一个研究得很好的问题，但还没有已知的多项式时间算法(有一些说法，但还没有一个得到证实)。
我必须测试两个图的同构，但对于我的情况，问题略有不同。图的大小小于 10 或 11，即顶点数较少。图的边数没有限制，可以是密集的也可以是稀疏的。这种成对测试(同构检查)的数量将在 10^8 左右。
如果有人可以建议一些最适合这种情况的算法。如果算法可以并行化，那就太好了。
感谢任何帮助。
最佳答案
这个答案依赖于两个图之一对于所有同构检查都是相同的这一事实。对于在重新标记下不变的每个节点，您可以计算出各种各样的数字:
- 节点的度数
- 其邻居的度数之和
- 其邻居的邻居的度数之和
- 对于那些度数为k的邻居，他们邻居的度数之和
- 包含该节点的长度为k的循环数
- 从这个节点到任何其他节点的最大距离
- 距离该节点 k 的节点数
- …
您可以获取引用图并为每个节点计算其中的几个数字。运气好的话，您会找到一组计算成本不太高的函数，并且生成的数字将唯一地标识每个节点。您甚至可以将这些数字散列为一个数字。在这种情况下，您可以按如下方式处理每个输入图:通过计算每个节点的这些数字及其哈希值，您可以快速确定引用图中的哪个节点对应于输入图的每个节点(如果有)。一旦您在节点之间建立了一对一的对应关系，检查是否所有边都适合就很简单了。
如果您找不到一组足够便宜的函数来唯一地描述每个节点，我希望在大多数真实世界的图中(即不是专门为高对称性构建的)，您仍然会获得相当小的等价类，因此检查每个类中所有可能的排列对于您的应用程序来说可能仍然足够便宜。
作为一个想法:如果性能在这里是一个真正的问题，您甚至可以尝试将您的分析结果转化为定制的程序代码。因此，对于每个引用图，您可以让您的应用程序编译一小段代码，然后它可以动态加载这些代码，以使用编译器优化的机器代码可以为您提供的所有功能来执行这些检查。不确定这是否值得付出努力，但我认为这可能是一种有趣的方法。
高度对称的图可能需要更多的工作。您可以尝试预先识别图形的同构。例如，如果您可以互换 v1 和 v2 的标签而不影响图结构，那么对于您处理的每个输入图，如果您不确定是否将给定顶点映射到 v1 或 v2，您知道它不会很重要，因此您不必尝试两种选择，而可以任意选择 v1。这大大减少了您必须检查的排列数量。
关于algorithm - 较小图上的图同构但大量测试，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12989096/