2

图同构是计算机科学中一个经过充分研究的问题，但没有已知的多项式时间算法（有一些说法，但还没有一个被证明）。

我必须测试两个图的同构，但就我而言，问题略有不同。图的大小小于 10 或 11，即更少的顶点数。图可以是密集的或稀疏的，边的数量没有限制。这种成对测试（同构检查）的数量将在 10^8 左右。

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

任何帮助表示赞赏。

4

2 回答 2

2

这个答案依赖于这样一个事实，即两个图之一对于您的所有同构检查都是相同的。对于重新标记下不变的每个节点，您可以计算出各种各样的数字：

  • 节点度
  • 其邻居的度数之和
  • 其邻居的邻居度的总和
  • 对于那些度数为k的邻居，他们邻居度数的总和
  • 包含该节点的长度为k的循环数
  • 从这个节点到任何其他节点的最大距离
  • 与该节点距离为k的节点数
  • …</li>

您可以获取参考图并为每个节点计算其中的几个数字。运气好的话，您会发现一组函数的计算成本不会太高，并且生成的数字将唯一地标识每个节点。您甚至可以将这些数字散列为一个数字。在这种情况下，您可以按如下方式处理每个输入图：通过计算每个节点的这些数字及其哈希值，您可以快速确定参考图中的哪个节点对应于输入图的每个节点（如果有）。一旦您在节点之间建立了一对一的对应关系，检查是否所有边都适合是微不足道的。

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

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

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

于 2012-10-21T08:29:34.240 回答
-1

如果您有办法快速判断从 v1 到 v2 有多少条边，那么您可以快速生成两个图的小表示并进行强力检查。但是如果你不能快速通过所有的边缘，这意味着你甚至不能有效地阅读你的输入而不是谈论检查同构

于 2012-10-21T00:27:33.030 回答