algorithm - 图和排列问题

Question

我有一个图(带有节点和边)，其中包含对称性和一组排列来标记节点，因此不会更改边(自同构)。现在我想确定哪些节点的排列交换两个等效(即具有相同颜色或对称类的节点)相邻节点。

当具有等效邻居的节点保持不变时，只需检查邻居是否在排列中交换就足够了。然而，当具有等效邻居的节点也被置换时(即有多个具有相同颜色/对称类且具有相同等效邻居的节点)，问题变得更加复杂。

是否有解决此类问题的已知算法？

一些说明:该图没有坐标，它只是一个拓扑结构

一个例子:

身份排列:http://imagebin.ca/view/2vAOi0I.html

有 384 个自守排列:http://pastebin.org/157954

排列反转节点 5 和 23 的简单示例:http://imagebin.ca/view/myQCvZnp.html

只要 5 和 23 保持在同一个位置，就很容易确定它们是否倒置(与恒等排列相比)。然而，当这些点也互换时，它变得更加困难。

困难的例子，排列 67:http://imagebin.ca/view/9gl-Wmzt.html

Answer 1

我认为您的问题定义不明确。想象下图:

      1
     / \
    /   \
   2     3
  / \   / \
 4   5 6   7

现在考虑交换 1 的两个子树的两个自同构。自同构 A:1<->1、2<->3、4<->6 和 5<->7自同构 B:1<->1、2<->3、4<->7 和 5<->6

其中哪一个“反转”了 2 的 child ？因为 2 映射到 3，我们必须决定自然对应是 4-6 和 5-7，还是 4-7 和 5-6。但是我们没有可以用来确定这一事实的信息。