Тестирование членства в группах автоморфизмов нечетких графов

Question

Предположим, нам дан цветной график. Пусть G его группа автоморфизмов. Как мы можем проверить, существует ли перестановка p в G такая, что p (x_i) = y_i для данного набора (x_i, y_i)? Конкретно предположим, что G группа перестановок из 6 элементов. Затем примерный тест, который я хотел бы сделать, состоит в том, содержит ли G какую-либо перестановку, которая посылает 2 к 2 и 3 к 5, и мне все равно, где 1,4,5,6 заканчиваются.

Можно предположить, что такая программа, как saucy, может эффективно вычислить набор генераторов для группы G.

Answer 1

Если G подключен, и вы можете запустить saucy на другом графике, подготовьте цветной граф H, состоящий из непересекающегося объединения G с самим собой и для каждого i, перекрасьте вершину x _i в первомкопия G и y _i во второй копии G должна быть цветом i, отличным от существующих цветов в G. Подходящий автоморфизм G существует тогда и только тогда, когда существует генератор Aut (H)который отображает вершину в первой копии на вершину во второй копии.

Возможно, существует более прямой метод, основанный на Schreier-Sims .

РЕДАКТИРОВАТЬ: вотОдним из способов может быть SS-метод.Пусть будет p пар x ₁ , y ₁ ,…, x _p , y _p .Если р = 0, ответ, конечно, да .В противном случае определите, существует ли перестановка g, которая переносит x _p в y _p , то есть x _p ^g = y _р .Если это не так, ответ будет нет .Если это так, то искомая перестановка существует тогда и только тогда, когда она может быть записана в виде hg (g, за которым следует h), где h принадлежит стабилизатору y _p .Используйте механизм SS для вычисления генераторов для стабилизатора и возврата рекурсивного ответа для x ₁ ^g , y ₁ ,…, x _p-1 ^г , у _р-1 .

Answer 2

Я понятия не имею, какие методы или объекты вы определили, но в псевдокоде вы смотрите на что-то вроде:

foreach (permutation p in G) {
    if p.permute(2) == 2 && p.permute(3) == 5:
         return true
}
return false

при условии, что p является объектом, у которого есть метод перестановки.