Algoritmo per la ricerca di simmetrie di un albero

Question

Ho n settori, numerati da 0 a n-1 in senso antiorario. I confini tra questi settori sono rami infiniti (n di essi). I settori vivono nel piano complesso e per n pari, il settore 0 e il n/2 sono divisi in due dall'asse reale e i settori sono equidistanti.

Questi rami si incontrano in determinati punti, chiamati giunzioni. Ogni giunzione è adiacente a un sottoinsieme dei settori (almeno 3 di essi).

Specificare gli svincoli, (in ordine di pre-correzione, diciamo, a partire da giunzione adiacente al settore 0 e 1), e la distanza tra i raccordi, descrive in modo univoco l'albero.

Ora, data una tale rappresentazione, come posso vedere se è simmetrica rispetto all'asse reale?

Ad esempio, n = 6, l'albero (0,1,5) (1,2,4,5) (2,3,4) ha tre giunzioni sulla linea reale, quindi è simmetrico rispetto l'asse reale. Se la distanza tra (015) e (1245) è uguale alla distanza da (1245) a (234), questo è anche simmetrico rispetto all'asse immaginario.

L'albero (0,1,5) (1,2,5) (2,4,5) (2,3,4) ha 4 giunzioni e questo non è mai simmetrico rispetto all'asse immaginario o reale, ma ha una simmetria di rotazione di 180 gradi se la distanza tra le prime due e le ultime due giunzioni nella rappresentazione è uguale.

Edit: Ecco tutti gli alberi con 6 filiali, le distanze 1. http://www2.math.su.se/~per/files/allTrees.pdf

Quindi, data la descrizione/rappresentazione, voglio trovare qualche algoritmo per decidere se è simmetrica WRT reale, immaginario, e rotazione di 180 gradi. L'ultimo esempio ha una simmetria di 180 gradi.

Modifica 2: Questo è in realtà per la mia ricerca. Ho postato la domanda anche su mathoverflow, ma i miei giorni di programmazione in competizione mi dicono che questo è più simile a un compito IOI. Il codice in matematica sarebbe eccellente, ma java, python o qualsiasi altra lingua leggibile da un umano è sufficiente.

(Queste simmetrie corrisponde a particolari tipi di potenziale nella equazione di Schroedinger, che ha delle belle proprietà in meccanica quantistica.)

Answer 1

Dal momento che si dispone già di un algoritmo per costruire il set point per l'albero, è necessario solo per determinare se il set di punti ha una simmetria a flip. Idealmente il tuo set è calcolato simbolicamente (e lasciato in termini di sin (theta), cos (theta)) per i punti non razionali, che dovrebbe andare bene visto che sembra che tu stia usando Mathematica.

È ora vogliono sapere se il set point ha una simmetria di qualche asse, in modo rappresentare la trasformazione della medaglia/rotazione come matrice A, e abbiamo {x '} = Un {x}. Ordina l'after image set {x '} (usando le espressioni non i valori numerici) e confronta con il set point originale {x}. Se non c'è una corrispondenza di 1-1 allora non hai una simmetria altrimenti lo fai.

Penso che ci sia una funzione matematica per trovare le espressioni uniche in un set (ad esempio unico [beforeImage] == unico [residua])

Answer 2

Potresti definire meglio cosa si intende per la simmetria della struttura?

Innanzitutto dire che

"I settori vivono nel complesso aereo, e per n pari, settore 0 e n/2 sono attraversata dal asse reale, e i settori sono uniformemente distanziati ".

e che si desidera trovare la simmetria

WRT reale, immaginario, e la rotazione di 180 gradi

Vorrei quindi aspetto che le simmetrie sarebbero puramente geometrica, ma poi anche Dite, nel commento alla risposta di Justin

Non c'è anche un modo canonico per disegnare un albero, e il mio algoritmo di disegno non rispetta tutti i possibili simmetrie che un albero possa avere

Come si può cercare la simmetria geometrica se la posizione dei vertici della pianta non può essere univocamente definito sul piano? Inoltre in molti dei grafici che hai dato (N = 6, pari) i settori 0 e 3 non sono bisecati dall'asse x (asse reale), quindi ritengo che i tuoi stessi disegni siano errati.

Answer 3

non ho avuto il tempo di implementare questo, forse qualcuno qui potrebbe prendere ulteriormente:

prima partizione le giunzioni dal quadrante, questo dovrebbe produrre 4 alberi. {Tpp, Tmp, Tmm, Tpm} (p per più, m per meno). Ora il controllo per la simmetria sembra essere una larghezza direzionale primo attraversamento:

Il suo stato un po 'sul mio Mathematica, quindi nessuno di questo compilerà

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

Dove TraverseCompare controlla la struttura dell'albero utilizzando prima un respiro attraversare lungo un albero, e un ordine inverso largo prima traversata lungo l'altro albero. (qualcosa come il seguente, ma questo non funzionerà).

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