一千萬個為什麽

搜索

圖形和置換問題

我有一個包含對稱性的圖形(帶有節點和邊)和一組用於標記節點的排列,因此沒有邊緣被改變(自同構)。現在我想確定排列交換兩個等效節點(即具有相同顏色或對稱類的節點)相鄰節點的節點。

當具有等效鄰居的節點保持不變時,只需檢查鄰居是否在置換中交換就足夠了。然而,當具有等效鄰居的節點也被置換時(即,存在具有相同顏色/對稱類且具有相同等效鄰居的多個節點),問題變得更加復雜。

對於這樣的問題,有沒有已知的算法?

一些評論: 圖表沒有坐標,只是拓撲圖

一個例子:

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

只要5和23保持在同一位置,就很容易確定它們是否被倒置(與身份置換相比)。然而,當這些點也互換時,它變得更加困難。

Difficult example, permutation 67: http://imagebin.ca/view/9gl-Wmzt.html

最佳答案

我不認為你的問題是明確的。想象一下下面的圖:

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

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

這些中的哪一個“顛倒”2的孩子?因為2被映射到3,我們必須決定自然對應是4-6和5-7,還是4-7和5-6。但我們沒有任何信息可以用來決定這個事實。

轉載註明原文: 圖形和置換問題