Algorithme pour trouver les symétries d'un arbre

Question

J'ai n secteurs, énumérés de 0 à n-1 dans le sens anti-horaire. Les frontières entre ces secteurs sont des branches infinies (n d'entre eux). Les secteurs vivent dans le plan complexe, et pour n pair, les secteurs 0 et n/2 sont divisés par l'axe réel, et les secteurs sont régulièrement espacés.

Ces branches se rencontrent à certains points, appelés jonctions. Chaque jonction est adjacente à un sous-ensemble des secteurs (au moins 3 d'entre eux).

La spécification des jonctions (dans l'ordre des pré-fixations, disons, à partir de la jonction adjacente aux secteurs 0 et 1) et la distance entre les jonctions, décrit uniquement l'arborescence. Maintenant, étant donné une telle représentation, comment puis-je voir si elle est symétrique par rapport à l'axe réel?

Par exemple, n = 6, l'arbre (0,1,5) (1,2,4,5) (2,3,4) a trois jonctions sur la ligne réelle, donc il est symétrique par rapport à l'axe réel. Si les distances entre (015) et (1245) sont égales à la distance de (1245) à (234), est également symétrique par rapport à l'axe imaginaire.

L'arbre (0,1,5) (1,2,5) (2,4,5) (2,3,4) a 4 jonctions, et ce n'est jamais symétrique par rapport à l'axe imaginaire ou réel, mais il a une symétrie de rotation de 180 degrés si la distance entre les deux premières et les deux dernières jonctions dans la représentation est égale.

Edit: Voici tous les arbres avec 6 branches, distances 1. http://www2.math.su.se/~per/files/allTrees.pdf

Ainsi, compte tenu de la description/représentation, je veux trouver un algorithme pour décider si elle est réelle wrt symétrique, imaginaire, et rotation 180 degrés. Le dernier exemple a une symétrie de 180 degrés.

Éditer 2: Ceci est en fait pour ma recherche. J'ai aussi posté la question à mathoverflow, mais mes jours en programmation de compétition me disent que c'est plutôt une tâche d'IOI. Le code dans mathematica serait excellent, mais java, python, ou tout autre langage lisible par un humain suffit.

(Ces symétries correspondent à des types particuliers de potentiel dans l'équation de Schrödinger, qui a des propriétés agréables en mécanique quantique.)

Answer 1

Puisque vous avez déjà un algorithme pour construire le point de consigne pour l'arbre, vous avez seulement besoin pour déterminer si l'ensemble de points a une symétrie de retournement. Idéalement, votre ensemble est calculé symboliquement (et laissé en termes de sin (thêta), cos (thêta)) pour les points non rationnels, ce qui devrait être bien puisque vous semblez utiliser Mathematica.

Vous voulez maintenant savoir si votre jeu de point a une symétrie par rapport à un certain axe, afin de représenter la transformation chiquenaude/rotation en tant que matrice A, et nous avons {x '} = A {x}. Triez le jeu d'images après {x '} (en utilisant les expressions et non les valeurs numériques) et comparez le jeu de points original {x}. S'il n'y a pas de correspondance 1-1 alors vous n'avez pas de symétrie sinon vous le faites.

Je pense qu'il ya une fonction Mathematica pour trouver les expressions uniques dans un ensemble (par exemple unique [beforeImage] == unique [AfterImage])

Answer 2

Pourriez-vous s'il vous plaît mieux définir ce que vous entendez par symétrie de l'arbre?

Vous dites d'abord que

« Les secteurs vivent dans le plan complexe, et n même, le secteur 0 et n/2 sont deux parties égales par l'axe réel et les secteurs sont régulièrement espacés "

et que vous voulez trouver la symétrie

wrt réel, imaginaire et la rotation de 180 degrés

Je puis attendre à ce que les symétries seraient purement géométrique, mais vous aussi dire, dans le commentaire à la réponse de Justin

Il n'y a pas non plus de manière canonique de dessiner un arbre, et mon algorithme de dessin ne respecte pas toutes les possibles symétries qu'un arbre peut avoir

Comment pouvez-vous rechercher la symétrie géométrique si la position des sommets de l'arbre ne peut pas être définie de manière unique sur le plan? De plus, dans plusieurs des graphiques que vous avez donnés (N = 6, même), les secteurs 0 et 3 ne sont pas divisés par l'axe des x (axe réel), donc je considère que vos propres dessins sont erronés.

Answer 3

Je n'ai pas eu le temps de mettre en œuvre ce, peut-être quelqu'un ici pourrait prendre davantage:

partition d'abord les jonctions par quadrant, cela devrait produire 4 arbres. {Tpp, Tmp, Tmm, Tpm} (p pour plus, m pour moins). Maintenant, la vérification de la symétrie semble être une largeur directionnelle premier traversal:

Son été un moment sur mon Mathematica, donc rien de tout cela compilera

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

Où TraverseCompare vérifie la structure de l'arbre à l'aide d'un souffle premier traversal le long d'un arbre, et un ordre inverse de la largeur de la première traversée le long de l'autre arbre. (quelque chose comme le suivant, mais cela ne fonctionnera pas à).

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