图和排列问题
我有一个图（带有节点和边），包含对称性和一组用于标记节点的排列，因此不会更改边（自同构）。现在我想确定哪些节点的排列交换两个等效的（即具有相同颜色或对称类的节点）相邻节点。
当具有等效邻居的节点保持相同时，只需检查邻居是否在排列中交换就足够了。然而，当具有等效邻居的节点也被排列时（即，存在具有相同颜色/对称类且具有相同等效邻居的多个节点），问题变得更加复杂。
是否有任何已知的算法可以解决此类问题？
一些备注： 该图没有坐标，它只是一个拓扑
示例：
身份排列： http://imagebin.ca/ view/2vAOi0I.html
有 384 种自守排列：http://pastebin.org/157954
简单的例子，其中排列反转节点 5 和 5。 23： http://imagebin.ca/view/myQCvZnp.html
只要 5 和23 保持在同一个位置，很容易确定它们是否被倒置（与恒等排列相比）。然而，当这些点也互换时，事情就变得更加困难。
困难的示例，排列 67： http://imagebin.ca/view/9gl-Wmzt.html< /a>
I have a graph (with nodes and edges) containing symmetry and a group of permutations to label the nodes so no edges are changed (automorphisms). Now I would like to determine for which nodes a permutation exchanges two equivalent (i.e. nodes with the same color or symmetry class) neighboring nodes.
When the nodes with equivalent neighbors stay the same, simply checking if the neighbors are exchanged in the permutation is enough. However, when the nodes with equivalent neighbors are also permuted (i.e. there are multiple nodes with the same color/symmetry class with the same equivalent neighbors), the problem becomes more complex.
Is there any known algorithm for such a problem?
Some remarks:
The graph has no coordinates, it's a topology only
An example:
Identity permutation: http://imagebin.ca/view/2vAOi0I.html
There are 384 automorphic permutations: http://pastebin.org/157954
Simple example where the permutation inverts nodes 5 & 23: http://imagebin.ca/view/myQCvZnp.html
As long as 5 and 23 remain in the same place it is easy to determine if they are inverted (compared to the identity permutation). However, when these points are also interchanged it becomes more difficult.
Difficult example, permutation 67: http://imagebin.ca/view/9gl-Wmzt.html
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为你的问题没有明确定义。想象一下下面的图：
现在考虑交换 1 的两个子树的两个自同构。
自同构 A：1→1、2→3、4→6 和 5→7
自同构 B：1→1、2→3、4→7 和 5→6
其中哪一个“反转”了 2 的孩子？因为 2 映射到 3，所以我们必须决定自然对应是 4-6 和 5-7，还是 4-7 和 5-6。但我们没有任何信息可以用来确定这一事实。
I don't think your problem is well-defined. Imagine the following graph:
Now consider the two automorphisms that swap the two subtrees of 1.
automorphism A: 1<->1, 2<->3, 4<->6, and 5<->7
automorphism B: 1<->1, 2<->3, 4<->7, and 5<->6
Which one of these "inverts" the children of 2? Because 2 gets mapped to 3, we have to decide whether the natural correspondence is 4-6 and 5-7, or 4-7 and 5-6. But we have no information we can use to decide this fact.