Algorithm for finding symmetries of a tree

Question

I have n sectors, enumerated 0 to n-1 counterclockwise. The boundaries between these sectors are infinite branches (n of them). The sectors live in the complex plane, and for n even, sector 0 and n/2 are bisected by the real axis, and the sectors are evenly spaced.

These branches meet at certain points, called junctions. Each junction is adjacent to a subset of the sectors (at least 3 of them).

Specifying the junctions, (in pre-fix order, lets say, starting from junction adjacent to sector 0 and 1), and the distance between the junctions, uniquely describes the tree.

Now, given such a representation, how can I see if it is symmetric wrt the real axis?

For example, n=6, the tree (0,1,5)(1,2,4,5)(2,3,4) have three junctions on the real line, so it is symmetric wrt the real axis. If the distances between (015) and (1245) is equal to distance from (1245) to (234), this is also symmetric wrt the imaginary axis.

The tree (0,1,5)(1,2,5)(2,4,5)(2,3,4) have 4 junctions, and this is never symmetric wrt either imaginary or real axis, but it has 180 degrees rotation symmetry if the distance between the first two and the last two junctions in the representation are equal.

Edit: Here are all trees with 6 branches, distances 1. http://www2.math.su.se/~per/files/allTrees.pdf

So, given the description/representation, I want to find some algorithm to decide if it is symmetric wrt real, imaginary, and rotation 180 degrees. The last example have 180 degree symmetry.

Edit 2: This is actually for my research. I have posted the question at mathoverflow as well, but my days in competition programming tells me that this is more like an IOI task. Code in mathematica would be excellent, but java, python, or any other language readable by a human suffices.

(These symmetries corresponds to special kinds of potential in the Schroedinger equation, which has nice properties in quantum mechanics.)

Answer 1

Since you already have an algorithm to construct the point set for the tree, you only need to determine if the point set has flip symmetry. Ideally your set is computed symbolically (and left in terms of sin(theta), cos(theta)) for non rational points, which should be fine since you seem to be using Mathematica.

You now want to know if your point set has a symmetry about some axis, so represent the flip/rotation transformation as a matrix A, and we have {x'} = A{x}. Sort the after image set {x'} (using the expressions not the numeric values), and compare to the original point set {x}. If there is not a 1-1 correspondence then you don't have a symmetry otherwise you do.

I think there is a mathematica function to find the unique expressions in a set (e.g. Unique[beforeImage] == Unique[afterImage])

Answer 2

Could you please define better what you mean by symmetry of the tree?

You first say that

"The sectors live in the complex plane, and for n even, sector 0 and n/2 are bisected by the real axis, and the sectors are evenly spaced."

and that you want to find symmetry

wrt real, imaginary, and rotation 180 degrees

I would then expect that the symmetries would be purely geometrical, but then you also say, in the comment to Justin's answer

There is also not a canonical way to draw a tree, and my drawing algorithm does not respect all possible symmetries that a tree can have

How can you look for geometrical symmetry if the position of the vertices of the tree cannot be uniquely defined on the plane? Furthermore in many of the plots you have given (N=6, even) sectors 0 and 3 are not bisected by the x axis (real axis), so I would deem your own drawings wrong.

Answer 3

I have not had time to implement this, perhaps someone here might take it further:

First partition the junctions by quadrant, this should produce 4 trees. { Tpp, Tmp, Tmm, Tpm} (p for plus, m for minus). Now checking for symmetry seems to be a directional breadth first traversal:

Its been a while on my mathematica, so none of this will compile

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

Where TraverseCompare checks the structure of the tree using a breath first traversal along one tree, and a reverse order breadth first traversal along the other tree. (something like the following, but this won't work at ).

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