Граф и проблема перестановок

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. Но у нас нет информации, которую мы можем использовать, чтобы решить этот факт.