algorithm - 模糊图自同构群成员测试

Question

假设我们有一张彩色图。令 G 为其自同构群。我们如何测试 G 中是否存在排列 p，使得对于给定的 (x_i,y_i) 集合 p(x_i) = y_i？具体假设G是一个超过6个元素的置换群。然后我想做的一个示例测试是 G 是否包含任何将 2 发送到 2 和 3 发送到 5 的排列，我不关心 1、4、5、6 在哪里结束。

您可以假设像 saucy 这样的程序可以有效地为组 G 计算一组生成器。

Answer 1

如果 G 是连通的，并且你可以在不同的图上运行 saucy，准备一个彩色图 H，它由 G 与其自身的不相交并集组成，并且对于每个 i，重新着色图中的顶点 x_i G 的第一个副本和 G 的第二个副本中的 y_i 是与 G 中现有颜色不同的颜色 i。当且仅当存在 Aut( H) 将第一个副本中的顶点映射到第二个副本中的顶点。

也许有更直接的方法基于Schreier-Sims .

编辑:这是基于 SS 的方法可以采用的一种方式。假设有 p 对 x₁, y₁, …, x_p, y_p。如果 p = 0，答案当然是是。否则判断是否存在从x_p到y_p的置换g，即x_p^g = y_p。如果不是这样，答案是否。如果是这样，当且仅当它可以写成 h g(g 后跟 h)的形式时，您正在寻找的排列才存在，其中 h 属于 y_p 的稳定子。使用 SS 机器计算稳定器的生成器并返回递归计算的答案 x₁^g, y₁, …, x_p-1^g, y_p-1.