Algorytm znajdowania symetrii drzewa

Question

Mam n sektorów, wyliczonych od 0 do n-1 przeciwnie do ruchu wskazówek zegara. Granice między tymi sektorami to nieskończone gałęzie (n z nich). Sektory znajdują się w płaszczyźnie złożonej, a dla n nawet sektory 0 i n/2 są podzielone na pół przez rzeczywistą oś, a sektory są równomiernie rozmieszczone.

Te gałęzie spotykają się w określonych punktach, zwanych skrzyżowaniami. Każde skrzyżowanie przylega do podzbioru sektorów (co najmniej 3 z nich).

Określenie skrzyżowań, (w kolejności przed utrwaleniem, powiedzmy, począwszy od połączenia sąsiadującego z sektorem 0 i 1) oraz odległość między skrzyżowaniami, jednoznacznie opisuje drzewo.

Teraz, biorąc pod uwagę taką reprezentację, jak mogę sprawdzić, czy jest ona symetryczna względem rzeczywistej osi?

Na przykład, n = 6, drzewo (0,1,5) (1,2,4,5) (2,3,4) ma trzy złącza na linii rzeczywistej, , więc jest symetryczne. prawdziwa oś. Jeśli odległości między (015) i (1245) są równe odległości od (1245) do (234), , jest to również symetryczne względem osi urojonej.

Drzewo (0,1,5) (1,2,5) (2,4,5) (2,3,4) ma 4 węzły, a to nigdy nie jest symetryczne ani na osi urojonej, ani rzeczywistej, ale ma symetrię obrotu o 180 stopni, jeśli odległość między dwoma pierwszymi a dwoma ostatnimi skrzyżowaniami w reprezentacji jest równa.

Edit: Oto wszystkie drzewa z 6 oddziałów, dystansuje 1. http://www2.math.su.se/~per/files/allTrees.pdf

więc, biorąc pod uwagę opis/reprezentacja, chcę znaleźć jakiś algorytm zdecydować, czy jest symetryczny wrt prawdziwy, wyimaginowany, a obrót o 180 stopni. Ostatni przykład ma symetrię 180 stopni.

Edytuj 2: To jest tak naprawdę dla moich badań. Postawiłem to pytanie również pod adresem mathoverflow, , ale moje dni w programowaniu konkurencji mówią mi, że jest to bardziej jak zadanie IOI. Kod w matematyce byłby doskonały, ale java, python lub jakikolwiek inny język czytelny dla człowieka wystarczy.

(te symetrie odpowiada szczególnych rodzajów potencjału w równaniu Schroedingera, który ma ładne właściwości w mechanice kwantowej.)

Answer 1

Skoro masz już algorytm konstruowania wartości zadanej dla drzewa, wystarczy aby ustalić, czy ustawiony punkt ma odwrócenie symetrii. Idealnie twój zestaw jest obliczany symbolicznie (i pozostawiony pod względem grzechu (theta), cos (theta)) dla nieracjonalnych punktów, co powinno być w porządku, ponieważ wydajesz się używać Mathematica.

Teraz chcą wiedzieć, czy zadana ma symetrię o niektórych osi, tak stanowią transformację z klapką/rotacji jako matryca i mamy {x '} = {x}. Posortuj zbiór po {x '} (używając wyrażeń, a nie wartości liczbowych) i porównaj z oryginalnym zbiorem punktów {x}. Jeśli nie ma korespondencji 1-1, to nie masz symetrii, w przeciwnym razie robisz.

Myślę, że jest to funkcja Mathematica znaleźć unikalne wyrażenia w zestawie (np Unique [beforeImage] == Unikalne [powidok])

Answer 2

mógłbyś zdefiniować lepiej co masz na myśli przez symetrii drzewa?

najpierw powiedzieć, że

„Sektory żyć w kompleksie płaszczyźnie, a dla n nawet, sektor 0 i n/2 jest dwudzielna przez osi rzeczywistej, a sektory są równomiernie rozmieszczone . "

i że chcesz znaleźć symetria

wrt real, wyimaginowane i obrót o 180 stopni

bym wtedy oczekiwać, że symetrie byłoby czysto geometryczny, ale wtedy także powiedzmy w komentarzu do odpowiedzi Justina:

Nie ma również kanonicznego sposobu narysowania drzewa, i mój algorytm rysunek nie uwzględnia wszystkich możliwych symetrie, że drzewo może mieć

Jak można szukać geometrycznej symetrii jeśli położenie wierzchołków drzewa nie można jednoznacznie zdefiniowane w samolocie? Ponadto na wielu działkach, które dałeś (N = 6, parzyste), sektory 0 i 3 nie są przecinane przez oś x (oś rzeczywista), więc uznałbym twoje własne rysunki za błędne.

Answer 3

nie miałem czasu, aby wdrożyć to, być może ktoś tutaj może potrwać dalej:

pierwsza partycja na skrzyżowaniach przez ćwiartce, to powinien produkować 4 drzew. {Tpp, Tmp, Tmm, Tpm} (p dla plus, m dla minus). Teraz sprawdzania symetrii wydaje się być kierunkowe szerokość pierwszy przejścia:

Its been a na moim Mathematica, więc nic z tego nie będzie skompilować

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

Gdzie TraverseCompare sprawdza strukturę drzewa przy użyciu pierwszy oddech przechodzenie wzdłuż jednego drzewa, a kolejność w odwrotnym kierunku jest pierwszym przejściem wzdłuż drugiego drzewa. (coś w stylu poniżej, ale to nie zadziała).