Алгоритм нахождения симметрий дерева

Question

У меня есть n секторов, нумерованные от 0 до n-1 против часовой стрелки. Границы между этими секторами являются бесконечными ветвями (n из них). Секторы живут в комплексной плоскости, и даже п, сектор 0 и n / 2 разделены пополам реальной осью, а сектора расположены равномерно.

Эти ветви встречаются в определенных точках, называемых соединениями. Каждый узел смежен с подмножеством секторов (по крайней мере, 3 из них).

Указание соединений (в порядке до исправления, скажем, начиная с соединения, смежного с сектором 0 и 1) и расстояния между соединениями однозначно описывает дерево.

Теперь, при таком представлении, как я могу увидеть, симметрична ли она относительно реальной оси?

Например, n = 6, дерево (0,1,5) (1,2,4,5) (2,3,4) имеет три соединения на реальной линии, так что это симметрично относительно реальной оси. Если расстояния между (015) и (1245) равны расстоянию от (1245) до (234), это также симметрично относительно мнимой оси.

Дерево (0,1,5) (1,2,5) (2,4,5) (2,3,4) имеет 4 перехода, и это никогда не симметрично относительно мнимой или действительной оси, но он имеет симметрию вращения на 180 градусов, если расстояние между первыми двумя и последними двумя соединениями в представлении равно.

Edit: Здесь все деревья с 6 ветками, расстояния 1. http://www2.math.su.se/~per/files/allTrees.pdf

Итак, учитывая описание / представление, я хочу найти некоторый алгоритм, чтобы решить, является ли он симметричным относительно действительного, мнимого и поворота на 180 градусов. Последний пример имеет симметрию 180 градусов.

Редактировать 2: Это на самом деле для моего исследования. Я также разместил вопрос в mathoverflow, но мои дни в программировании соревнований говорят мне, что это больше похоже на задачу IOI. Код в mathematica был бы превосходным, но достаточно java, python или любого другого языка, читаемого человеком.

(Эти симметрии соответствуют особым видам потенциала в уравнении Шредингера, который имеет хорошие свойства в квантовой механике.)

Answer 1

Не могли бы вы лучше определить, что вы подразумеваете под симметрией дерева?

Вы сначала говорите, что

"Секторы живут в комплексе плоскость, и для четного п, сектор 0 и n / 2 разделены пополам реальной осью, и сектора расположены равномерно. "

и что вы хотите найти симметрию

по отношению к реальному, воображаемому и повороту на 180 градусов

Я бы тогда ожидал, что симметрии будут чисто геометрическими, но тогда вы также скажете, в комментарии к ответу Джастина

Также нет канонического способа нарисовать дерево, и мой алгоритм рисования не учитывает все возможные симметрии, которые дерево может иметь

Как вы можете искать геометрическую симметрию, если положение вершин дерева не может быть однозначно определено на плоскости? Более того, на многих графиках, которые вы указали (N = 6, четные), сектора 0 и 3 не разделены пополам осью x (действительной осью), поэтому я считаю ваши собственные рисунки неправильными.

Answer 2

У меня не было времени, чтобы реализовать это, возможно, кто-то здесь может пойти дальше:

Сначала разделите соединения по квадранту, это должно дать 4 дерева. {Tpp, Tmp, Tmm, Tpm} (p для плюс, m для минус). Теперь проверка на симметрию кажется первым направленным обходом ширины:

Это было какое-то время на моей математике, поэтому ничего из этого не скомпилирует

CheckRealFlip[T_] := And[TraverseCompare[Tpp[T], Tpm[T]],
                         TraverseCompare[Tmp[T], Tmm[T]];
CheckImFlip[T_] :=   And[TraverseCompare[Tpp[T], Tmp[T]],
                         TraverseCompare[Tpm[T], Tmm[T]];

Где TraverseCompare проверяет структуру дерева с использованием первого обхода дыхания по одному дереву и обратного хода по ширине сначала по другому дереву. (что-то вроде следующего, но это не сработает).

TraverseCompare[A_, B_] := Size[A] == Size[B] && 
  Apply[TraverseCompare, Children[A], Reverse[Children[B]];

Answer 3

Поскольку у вас уже есть алгоритм для построения набора точек для дерева, вам нужно только определить, имеет ли набор точек симметричность. В идеале ваш набор вычисляется символически (и оставляется в терминах sin (theta), cos (theta)) для нерациональных точек, что должно быть хорошо, так как вы, похоже, используете Mathematica.

Теперь вы хотите узнать, имеет ли ваш набор точек симметрию относительно некоторой оси, поэтому представьте преобразование переворота / вращения в виде матрицы A , и мы получим {x '} = A {х}. Сортируйте набор изображений после {x '} (используя выражения, а не числовые значения) и сравните с исходным набором точек {x}. Если нет соответствия 1-1, то у вас нет симметрии, иначе вы делаете.

Я думаю, что есть функция mathematica для поиска уникальных выражений в наборе (например, Unique [beforeImage] == Unique [afterImage])