Алгоритм для нахождения симметрий дерева
У меня есть n секторы, перечисленные 0 к n-1 против часовой стрелки. Границы между этими секторами являются бесконечными ответвлениями (n их). Секторы, живые в комплексной плоскости, и для n даже, сектор 0 и n/2 разделен пополам вещественной осью, и секторы равномерно расположены с интервалами.
Эти ответвления встречаются в определенные моменты, названные соединениями. Каждое соединение смежно с подмножеством секторов (по крайней мере 3 из них).
При определении соединений, (в порядке префикса, позволяет, говорят, начинающий с соединения, смежного с сектором 0 и 1), и расстояние между соединениями, исключительно описывает дерево.
Теперь, учитывая такое представление, как я могу видеть, является ли это симметричный wrt вещественная ось?
Например, n=6, дерево (0,1,5) (1,2,4,5) (2,3,4) имеет три соединения на реальной строке, таким образом, это - симметричный wrt вещественная ось. Если расстояния между (015) и (1245) равны расстоянию от (1 245) до (234), это - также симметричный wrt мнимая ось.
Дерево (0,1,5) (1,2,5) (2,4,5) (2,3,4) имеет 4 соединения, и это никогда не симметричный wrt или мнимая или вещественная ось, но это имеет симметрию вращения на 180 градусов, если расстояние между первыми двумя и последними двумя соединениями в представлении равно.
Править: Вот все деревья с 6 ответвлениями, расстояния 1. http://www2.math.su.se/~per/files/allTrees.pdf
Так, учитывая описание/представление, я хочу найти, что некоторый алгоритм решает, ли это симметрично wrt реальный, мнимый, и вращение 180 градусов. Последний пример имеет симметрию на 180 градусов.
Редактирование 2: Это на самом деле для моего исследования. Я отправил вопрос в mathoverflow также, но мои дни в программировании конкуренции говорят мне, что это больше похоже на задачу IOI. Код в mathematica был бы превосходен, но Java, Python или любой другой язык, читаемый человеком, достаточны.
(Эти симметрии соответствуют специальным видам потенциала в уравнении Schroedinger, которое имеет хорошие свойства в квантовой механике.)
3 ответа
Поскольку у вас уже есть алгоритм для построения набора точек для дерева, вам нужно только определить, имеет ли набор точек обратную симметрию. В идеале ваш набор вычисляется символически (и остается в терминах sin (theta), cos (theta)) для нерациональных точек, что должно быть хорошо, поскольку вы, похоже, используете Mathematica.
Теперь вы хотите знать, имеет ли ваш набор точек симметрию относительно некоторой оси, поэтому представьте преобразование переворота / поворота в виде матрицы A , и у нас есть {x '} = A {x}. Отсортируйте набор последующих изображений {x '} (используя выражения, а не числовые значения) и сравните с исходным набором точек {x}. Если нет соответствия 1-1, тогда у вас нет симметрии, иначе она есть.
Я думаю, что есть математическая функция для поиска уникальных выражений в наборе (например, Unique [beforeImage] == Unique [afterImage])
Не могли бы вы лучше определить, что вы подразумеваете под симметрией дерева?
Сначала вы говорите, что
«Секторы живут в комплексе { {1}} плоскость, а для четного n сектор 0 и n / 2 делятся пополам по действительной оси, а секторы равномерно разнесены.«
и что вы хотите найти симметрию
относительно реального, мнимого и поворота на 180 градусов
, тогда я бы ожидал, что симметрии будут чисто геометрическими, но тогда вы также говорите в комментарии к ответу Джастина
Также не существует канонического способа рисования дерева, и мой алгоритм рисования не учитывает все возможные симметрии, которые может иметь дерево
Как вы можете искать геометрическую симметрию если положение вершин дерева не может быть однозначно определено на плоскости? Кроме того, на многих графиках, которые вы указали (N = 6, четных), секторы 0 и 3 не делятся пополам по оси x (действительной оси), поэтому Я бы посчитал ваши собственные рисунки неправильными.
У меня не было времени реализовать это, возможно, кто-то здесь может пойти дальше:
Сначала разделите соединения по квадрантам, это должно дать 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]];