algorithm - 多面体图（平面三连通图）同构的算法？

Question

我已经对平面 3 连通图的图同构主题进行了一些研究，但是有大量不同限制、理论复杂性和使用频率的算法，我很难找到一个突出的算法：

• 容易明白
• 可以以最大的清晰度实施
• 在小图（最多几十个顶点）上具有良好的实际性能

如果我自己不了解不同的算法，很难知道我是否更适合使用旧的、更专业的算法来解决这个问题，还是使用更新的、更通用的算法。在所有可能的候选人中，哪一个是最合适的？

Answer 1

我认为温伯格的算法符合要求。

• 易于理解：计算G 和 H 的旋转系统，作为平面测试算法的副产品。由于 G 和 H 是 3 连通的，因此当且仅当 G 和 H 同构时，这些旋转系统是同构的，直到顺时针和逆时针互换。在 G 中选择一个省道（= 具有指示方向的边缘）d 并尝试将其映射到 H 中的所有省道 e（并重复 H 的其他方向）。由于 G 是连通的，所有其他飞镖 d' 可以通过组合 G 的旋转系统的两个操作从 d 到达。将相应的操作应用于 e 并检查是否存在同构。

• 最大清晰度：除了平面性测试，上面是一页代码。也许您可以重复使用其他人的平面性测试？例如，Boost 中有一个。如果不是，我仍然认为实现你自己的比重写 nauty 更容易。

• 在小图上有很好的实用性能：经过平面性测试，Weinberg 的算法基本上是对每个 dart 进行两次同步的深度优先遍历。总运行时间为 O(|V| ² )，没有潜伏的大常数。