Algoritmo para encontrar simetrías de un árbol

Question

Tengo n sectores, enumerados 0 a n-1 en el sentido contrario a las agujas del reloj. Los límites entre estos sectores son ramas infinitas (n de ellos). Los sectores viven en el plano complejo, y para n incluso, sector 0 y n/2 están bisecados por el eje real, y los sectores están espaciados uniformemente.

Estas ramas se encuentran en ciertos puntos, llamados cruces. Cada unión es adyacente a un subconjunto de los sectores (al menos 3 de ellos).

La especificación de las uniones, (en orden de pre-corrección, digamos, comenzando desde la unión adyacente al sector 0 y 1), y la distancia entre las uniones, describe de manera única el árbol.

Ahora, dada tal representación, ¿cómo puedo ver si es simétrica con respecto al eje real?

Por ejemplo, n = 6, el árbol (0,1,5) (1,2,4,5) (2,3,4) tiene tres uniones en la línea real, por lo que es wrt simétrico el eje real Si las distancias entre (015) y (1245) son iguales a la distancia desde (1245) a (234), , esto también es simétrico con respecto al eje imaginario.

El árbol (0,1,5) (1,2,5) (2,4,5) (2,3,4) tienen 4 uniones, y esto nunca es wrt simétrica o bien eje imaginario o real, pero tiene una simetría de rotación de 180 grados si la distancia entre las primeras dos y las últimas dos uniones en la representación es igual.

Editar: continuación se muestran todos los árboles con ramas 6, distancias 1. http://www2.math.su.se/~per/files/allTrees.pdf

Por lo tanto, dada la descripción/representación, quiero encontrar algún algoritmo para decidir si es WRT simétrica real, imaginaria, y rotación 180 grados. El último ejemplo tiene una simetría de 180 grados.

Edición 2: Esto es en realidad para mi investigación. También publiqué la pregunta en mathoverflow, , pero mis días en la programación de la competencia me dicen que esto es más como una tarea de IOI. El código en mathematica sería excelente, pero java, python o cualquier otro idioma legible por un humano es suficiente.

(Estas simetrías corresponde a un tipo especial de potencial en la ecuación de Schrödinger, que tiene propiedades agradables en la mecánica cuántica.)

Answer 1

Como usted ya tiene un algoritmo para construir el punto de ajuste para el árbol, sólo es necesario para determinar si el conjunto de puntos tiene simetría invertida. Idealmente, su conjunto se calcula simbólicamente (y se deja en términos de sin (theta), cos (theta)) para los puntos no racionales, lo que debería estar bien ya que parece estar usando Mathematica.

Ahora quieren saber si su conjunto de puntos tiene una simetría sobre algunos ejes, por lo que representan la transformación flip/rotación como una matriz Un, y tenemos {x '} = Un {x}. Ordene la imagen posterior configurada {x '} (utilizando las expresiones, no los valores numéricos) y compárela con el punto original establecido {x}. Si no hay una correspondencia 1-1, entonces no tienes una simetría; de lo contrario, sí.

Creo que hay una función de Mathematica para encontrar las expresiones únicas en un conjunto (por ejemplo Único [beforeImage] == Único [Afterimage])

Answer 2

Podría por favor definir mejor qué quiere decir con simetría del árbol?

En primer lugar decir que

"Los sectores viven en el complejo avión, y para n par, el sector 0 y n/2 se atravesada por el eje real, y los sectores están uniformemente espaciadas "

y que desea encontrar la simetría

verdadera WRT, imaginario, y la rotación de 180 grados

Entonces yo espero que las simetrías serían puramente geométrica, pero entonces también por ejemplo, en el comentario a la respuesta de Justin

Tampoco hay una manera canónica de dibujar un árbol, y mi algoritmo de dibujo no respetar todas las posibles simetrías que un árbol puede tener

¿Cómo se puede buscar la simetría geométrica si la posición de los vértices del árbol no se puede definir de forma única en el avión? Además, en muchos de los trazados que has dado (N = 6, par), los sectores 0 y 3 no están divididos en dos por el eje x (eje real), por lo que consideraría que tus propios dibujos son incorrectos.

Answer 3

No he tenido tiempo para poner en práctica esto, tal vez alguien aquí podría ir más lejos:

Primera partición de las uniones por cuadrante, esto debería producir 4 árboles. {Tpp, Tmp, Tmm, Tpm} (p para más, m para menos). Ahora la comprobación de la simetría parece ser una amplitud direccional primer recorrido:

Su sido un tiempo en mi Mathematica, así que nada de esto se compilará

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]]; 

Dónde TraverseCompare comprueba la estructura del árbol usando una respiración primero recorrido transversal a lo largo de un árbol, y un recorrido inverso de ancho a lo largo del otro árbol. (algo como lo siguiente, pero esto no funcionará en).

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