9

我有 n 个扇区，逆时针枚举 0 到 n-1。这些扇区之间的边界是无限的分支（其中 n 个）。扇区位于复平面中，对于 n 偶数，扇区 0 和 n/2 被实轴二等分，扇区间距均匀。

这些分支在某些点相遇，称为交汇点。每个路口都与扇区的一个子集（至少其中 3 个）相邻。

指定连接点（以前缀顺序，假设从与扇区 0 和 1 相邻的连接点开始）以及连接点之间的距离，唯一地描述了树。

现在，给定这样的表示，我如何查看它是否与实轴对称？

例如，n=6，树 (0,1,5)(1,2,4,5)(2,3,4) 在实线上有三个交汇点，所以它是关于实轴对称的。如果 (015) 和 (1245) 之间的距离等于从 (1245) 到 (234) 的距离，这也是关于虚轴对称的。

树 (0,1,5)(1,2,5)(2,4,5)(2,3,4) 有 4 个连接点，无论是虚轴还是实轴，这都不是对称的，但它有 180 个如果表示中的前两个和最后两个交汇点之间的距离相等，则旋转对称度数。

编辑：这里是所有有 6 个分支的树，距离为 1。 http://www2.math.su.se/~per/files/allTrees.pdf

因此，鉴于描述/表示，我想找到一些算法来确定它是否是对称的实数、虚数和 180 度旋转。最后一个示例具有 180 度对称性。

编辑2：这实际上是为了我的研究。我也在 mathoverflow 上发布了这个问题，但是我在竞赛编程中的日子告诉我，这更像是一个 IOI 任务。mathematica 中的代码会非常好，但 java、python 或任何其他人类可读的语言就足够了。

（这些对称性对应于薛定谔方程中的特殊势能，它在量子力学中具有很好的性质。）

4

3 回答 3

1

您能否更好地定义树的对称性是什么意思？

你先这么说

“扇区位于复平面上，对于 n 偶数，扇区 0 和 n/2 被实轴一分为二，扇区间距均匀。”

你想找到对称性

wrt 实数、虚数和旋转 180 度

然后我希望对称性将是纯几何的，但你也说，在对贾斯汀的回答的评论中

绘制树也没有规范的方法，而且我的绘图算法不尊重树可能具有的所有可能的对称性

如果树的顶点位置不能在平面上唯一定义，您如何寻找几何对称性？此外，在您给出的许多图中（N=6，偶数），扇区 0 和 3 没有被 x 轴（实轴）一分为二，所以我认为您自己的绘图是错误的。

于 2010-05-12T09:39:50.220 回答
0

我还没有时间来实现这一点，也许这里有人可能会更进一步：

首先按象限划分路口，这应该产生 4 棵树。{ Tpp, Tmp, Tmm, Tpm}（p 为正，m 为负）。现在检查对称性似乎是方向广度优先遍历：

我的数学已经有一段时间了，所以这些都不会编译

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

TraverseCompare 使用沿一棵树的呼吸优先遍历和沿另一棵树的逆序广度优先遍历来检查树的结构。（类似于以下内容，但这不适用于 ）。

TraverseCompare[A_, B_] := Size[A] == Size[B] && 
  Apply[TraverseCompare, Children[A], Reverse[Children[B]];
于 2010-05-12T14:47:24.347 回答
0

由于你已经有了一个算法来为树构造点集，你只需要确定点集是否具有翻转对称性。理想情况下，对于非理性点，您的集合是象征性地计算的（并以 sin(theta)、cos(theta) 的形式留下），这应该没问题，因为您似乎正在使用 Mathematica。

您现在想知道您的点集是否关于某个轴对称，因此将翻转/旋转变换表示为矩阵A，我们有 {x'} = A {x}。对后图像集 {x'} 进行排序（使用表达式而不是数值），并与原始点集 {x} 进行比较。如果没有 1-1 对应关系，那么你就没有对称性，否则你就有。

我认为有一个数学函数可以找到一组中的唯一表达式（例如 Unique[beforeImage] == Unique[afterImage]）

于 2010-05-10T19:31:14.253 回答