Algorithm for finding symmetries of a tree
- by Paxinum
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:
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.
Here are some examples (pretend the double edges are single and we have a tree)
http://www2.math.su.se/~per/files.php?file=contr_ex_1.pdf
http://www2.math.su.se/~per/files.php?file=contr_ex_2.pdf
http://www2.math.su.se/~per/files.php?file=contr_ex_5.pdf
Example 1 is described as (0,1,4)(1,2,4)(2,3,4)(0,4,5) with distances (2,1,3).
Example 2 is described as (0,1,4)(1,2,4)(2,3,4)(0,4,5) with distances (2,1,1).
Example 5 is described as (0,1,4,5)(1,2,3,4) with distances (2).
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.
(These symmetries corresponds to special kinds of potential in the Schroedinger equation,
which has nice properties in quantum mechanics.)
