测试次数较多的较小图的图同构

Question

图同构是计算机科学中一个研究得很好的问题，但目前还没有已知的多项式时间算法(有一些说法，但还没有得到证明)。

我必须测试两个图的同构性，但对于我的情况，问题略有不同。图的大小小于10或11，即较少的顶点数量。图的边数没有限制，即图可以是密集的，也可以是稀疏的。这样的成对测试(同构检查)的数量将在10^8左右。

如果有人能推荐一些最适合这种情况的算法。此外，如果算法可以并行化，那就太好了。

感谢您的帮助。

Answer 1

这个答案依赖于这样一个事实，即对于所有同构检查，两个图中的一个将是相同的。您可以为每个节点计算大量的数字，这些数字在重新标记下是不变的：

• 节点的度
• 其邻居的度之和
• 其邻居的度之和
• 对于那些具有k度的邻居，其邻居的度之和

H19包含此节点的长度为k的循环的数目

• 从该节点到任何其他节点的最大距离H212H113距离此节点k的节点数
• …

您可以使用您的参考图，并为每个节点计算几个这样的数字。幸运的是，您将找到一组计算成本不太高的函数，并且所得到的数字将唯一地标识每个节点。您甚至可以将这些数字散列为一个单独的数字。在这种情况下，您可以按如下方式处理每个输入图:通过计算这些数字及其对每个节点的散列，您可以快速确定引用图中的哪个节点对应于输入图的每个节点。一旦节点之间有了一对一的对应关系，检查是否所有的边都拟合是微不足道的。

如果你找不到一组足够便宜的函数来唯一地描述每个节点，我希望在大多数现实世界的图中(即不是专门为高对称性而构建的)，你仍然可以获得相当小的等价类，所以检查每个类中所有可能的排列对于你的应用程序来说可能仍然足够便宜。

作为一个想法:如果性能在这里是一个真正的问题，您甚至可以尝试将分析结果转换为定制的程序代码。因此，对于每个引用图，您将让您的应用程序编译一小段代码，然后它可以动态加载这些代码，以利用编译器优化的机器码所能提供的所有功能执行这些检查。我不确定这样的努力是否值得，但我认为这可能是一种有趣的方法。

高度对称的图形可能需要更多的工作。您可以尝试预先识别图形的同构。例如，如果您可以在不影响图形结构的情况下交换v1和v2的标签，那么对于您处理的每个输入图形，如果您不确定是将给定的顶点映射到v1还是v2，您知道这并不重要，因此您不必同时尝试这两种方法，只需任意选择v1即可。这极大地减少了您必须检查的排列数量。

Answer 2

如果您有一种方法可以快速判断从v1到v2有多少条边，那么您可以快速生成这两个图的小表示，并执行暴力检查。但是如果你不能快速遍历所有的边，这意味着你甚至不能有效地阅读你的输入，更不用说检查同构了