Algorithmus zum Finden von Symmetrien eines Baumes

9

Ich habe n Sektoren, von 0 bis n-1 gegen den Uhrzeigersinn aufgezählt. Die Grenzen zwischen diesen Sektoren sind unendliche Zweige (n davon). Die Sektoren leben in der komplexen Ebene, und für n sogar, Sektor 0 und n / 2 werden durch die reelle Achse halbiert und die Sektoren sind gleichmäßig beabstandet.

Diese Zweige treffen sich an bestimmten Punkten, sogenannten Junctions. Jede Verzweigung ist benachbart zu einer Teilmenge der Sektoren (mindestens 3 von ihnen).

Das Angeben der Junctions (in der Reihenfolge vor der Fixierung, zum Beispiel ausgehend von der Junction neben Sektor 0 und 1) und der Abstand zwischen den Junctions beschreibt den Baum eindeutig.

Wie kann ich nun bei einer solchen Darstellung sehen, ob es symmetrisch zur reellen Achse ist?

Zum Beispiel, n = 6, der Baum (0,1,5) (1,2,4,5) (2,3,4) hat drei Übergänge auf der reellen Linie, es ist also symmetrisch zur reellen Achse. Wenn die Abstände zwischen (015) und (1245) gleich der Entfernung von (1245) bis (234) sind, Dies ist auch symmetrisch bezüglich der imaginären Achse.

Der Baum (0,1,5) (1,2,5) (2,4,5) (2,3,4) hat 4 Übergänge, und dies ist nie symmetrisch, weder imaginär noch reell, sondern es hat eine Rotationssymmetrie von 180 Grad, wenn der Abstand zwischen den ersten beiden und den letzten beiden Knoten in der Darstellung gleich ist.

Bearbeiten: Hier sind alle Bäume mit 6 Ästen, Distanzen 1. Ссылка

Angesichts der Beschreibung / Darstellung möchte ich also einen Algorithmus finden, der entscheidet, ob er in reeller, imaginärer und Rotation um 180 Grad symmetrisch ist. Das letzte Beispiel hat 180 Grad Symmetrie.

Bearbeiten 2: Das ist eigentlich für meine Forschung. Ich habe die Frage auch bei mathoverflow gepostet, aber meine Tage im Wettbewerb Programmierung sagt mir, dass dies eher wie eine IOI Aufgabe ist. Code in Mathematica wäre hervorragend, aber Java, Python oder jede andere Sprache, die von einem Menschen gelesen werden kann, reicht aus.

(Diese Symmetrien entsprechen speziellen Arten von Potential in der Schrödinger-Gleichung, das hat schöne Eigenschaften in der Quantenmechanik.)

    
Per Alexandersson 01.05.2010, 14:42
quelle

3 Antworten

1

Könnten Sie bitte besser definieren, was Sie mit der Symmetrie des Baumes meinen?

Das sagst du zuerst

  

"Die Sektoren leben in der Anlage   Ebene, und für n gerade, Sektor 0 und   n / 2 werden von der reellen Achse halbiert, und   Die Sektoren sind gleichmäßig verteilt. "

und dass Sie Symmetrie suchen

  

wrt real, imaginär und Rotation um 180 Grad

Ich würde dann erwarten, dass die Symmetrien rein geometrisch sein würden, aber dann sagt man auch im Kommentar zu Justins Antwort

  

Es gibt auch keine kanonische Art, einen Baum zu zeichnen,   und mein Zeichnungsalgorithmus respektiert nicht alles mögliche   Symmetrien, die ein Baum haben kann

Wie kann man nach einer geometrischen Symmetrie suchen, wenn die Position der Knoten des Baumes in der Ebene nicht eindeutig definiert werden kann? Außerdem sind die Sektoren 0 und 3 in vielen der von Ihnen angegebenen Plots (N = 6, gerade) nicht durch die x-Achse (reelle Achse) halbiert, so dass ich Ihre eigenen Zeichnungen für falsch halten würde.

    
NeXuS 12.05.2010 09:39
quelle
0

Da Sie bereits einen Algorithmus haben, um den Punktsatz für den Baum zu konstruieren, müssen Sie nur bestimmen, ob der Punktsatz eine Umkippsymmetrie aufweist. Im Idealfall wird Ihre Menge symbolisch (und in Bezug auf sin (theta), cos (theta)) für nicht rationale Punkte berechnet, was in Ordnung sein sollte, da Sie scheinen, Mathematica zu verwenden.

Sie möchten nun wissen, ob Ihre Punktmenge eine Symmetrie um eine Achse hat, also stellen Sie die Flip / Rotation-Transformation als Matrix A dar, und wir haben {x '} = A {x}. Sortieren Sie das Nachbildset {x '} (verwenden Sie die Ausdrücke nicht die numerischen Werte) und vergleichen Sie es mit dem ursprünglichen Punktset {x}. Wenn es keine 1-1 Korrespondenz gibt, dann haben Sie keine Symmetrie, sonst tun Sie es.

Ich denke, es gibt eine mathematische Funktion, um die eindeutigen Ausdrücke in einer Menge zu finden (z. B. Unique [vorherigesBild] == Eindeutiges [nachBild])

    
Justin 10.05.2010 19:31
quelle
0

Ich hatte noch keine Zeit, dies umzusetzen, vielleicht könnte jemand hier noch weiter gehen:

Teilen Sie zuerst die Übergänge nach Quadranten, dies sollte 4 Bäume ergeben. {Tpp, Tmp, Tmm, Tpm} (p für Plus, m für Minus). Die Überprüfung auf Symmetrie scheint nun eine gerichtete erste Durchquerung zu sein:

Es ist eine Weile auf meiner Mathematica gewesen, also kompiliert nichts davon

%Vor%

Wo TraverseCompare die Struktur des Baums überprüft, indem zuerst ein Atemzug entlang eines Baums und eine umgekehrte Reihenfolge zuerst entlang des anderen Baums durchlaufen wird. (etwas wie das Folgende, aber das wird nicht funktionieren).

%Vor%     
Justin 12.05.2010 14:47
quelle

Tags und Links