9

反時計回りに0からn-1まで列挙されたn個のセクターがあります。これらのセクター間の境界は無限のブランチです（そのうちのn個）。セクターは複素平面に存在し、nが偶数の場合、セクター0とn / 2は実軸で二等分され、セクターは等間隔に配置されます。

これらのブランチは、ジャンクションと呼ばれる特定のポイントで合流します。各ジャンクションは、セクターのサブセット（少なくとも3つ）に隣接しています。

ジャンクション（たとえば、セクター0と1に隣接するジャンクションから開始する前置順序）とジャンクション間の距離を指定すると、ツリーが一意に記述されます。

さて、そのような表現が与えられた場合、それが実際の軸に対して対称であるかどうかをどのように確認できますか？

たとえば、n = 6の場合、ツリー（0,1,5）（1,2,4,5）（2,3,4）には実線上に3つのジャンクションがあるため、実軸に対して対称になります。（015）と（1245）の間の距離が（1245）から（234）までの距離に等しい場合、これも仮想軸に対して対称です。

ツリー（0,1,5）（1,2,5）（2,4,5）（2,3,4）には4つのジャンクションがあり、これは仮想軸または実軸のいずれに対しても対称ではありませんが、180があります。表現の最初の2つのジャンクションと最後の2つのジャンクションの間の距離が等しい場合、回転対称度。

編集：これが6つの枝、距離1のすべての木です 。http：//www2.math.su.se/~per/files/allTrees.pdf

したがって、説明/表現を前提として、実数、虚数、および180度の回転に対して対称であるかどうかを判断するためのアルゴリズムを見つけたいと思います。最後の例は180度の対称性を持っています。

編集2：これは実際に私の研究のためです。mathoverflowにも質問を投稿しましたが、競技プログラミングでの日々は、これはIOIタスクのようなものだと教えてくれます。数学のコードは素晴らしいでしょうが、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)。対称性のチェックは、方向幅優先トラバーサルのようです。

それは私のmathematicaでしばらくしていたので、これはコンパイルされません

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(シータ)、cos(シータ) に関して残されます)。これは、Mathematica を使用しているように見えるので問題ありません。

ポイントセットがいくつかの軸について対称性を持っているかどうかを知りたいので、反転/回転変換を行列Aとして表すと、{x'} = A {x} になります。後の画像セット {x'} を (数値ではなく式を使用して) 並べ替え、元のポイント セット {x} と比較します。1 対 1 の対応がない場合、対称性はありません。

セット内の一意の式を見つけるための mathematica 関数があると思います (例: Unique[beforeImage] == Unique[afterImage])

于 2010-05-10T19:31:14.253 に答える