格拉夫和置換問題

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的孩子之一？因爲2被映射到3，我們必須決定自然對應是4-6和5-7還是4-7和5-6。但我們沒有任何信息可以用來決定這個事實。