Проблема с графом и перестановкой

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. автоморфизм А: 1 < -> 1, 2 < -> 3, 4 < -> 6 и 5 < -> 7 автоморфизм Б: 1 < -> 1, 2 < -> 3, 4 < -> 7 и 5 < -> 6

Какой из этих "инвертирует" детей 2? Поскольку 2 сопоставляется с 3, мы должны решить, соответствует ли естественное соответствие 4-6 и 5-7, или 4-7 и 5-6. Но у нас нет информации, которую мы можем использовать, чтобы решить этот факт.