पेड़ की समरूपता खोजने के लिए एल्गोरिदम

Question

मेरे पास एन सेक्टर हैं, जो 0 से एन-1 विपरीत दिशा में हैं। इन क्षेत्रों के बीच सीमाएं अनंत शाखाएं हैं (उनमें से एन)। क्षेत्र जटिल विमान में रहते हैं, और यहां तक ​​कि सेक्टर 0 और एन/2 वास्तविक धुरी से विभाजित होते हैं, और क्षेत्र समान रूप से दूरी पर हैं।

ये शाखाएं कुछ बिंदुओं पर मिलती हैं, जिन्हें जंक्शन कहा जाता है। प्रत्येक जंक्शन सेक्टरों के उप-समूह (उनमें से कम से कम 3) के निकट होता है।

जंक्शन निर्दिष्ट करना, (प्री-फ़िक्स ऑर्डर में, कहें, जंक्शन के आस-पास जंक्शन से शुरू होने से पहले 0 और 1), और जंक्शन के बीच की दूरी, विशिष्ट रूप से पेड़ का वर्णन करती है।

अब, इस तरह के एक प्रतिनिधित्व के बाद, मैं कैसे देख सकता हूं कि यह वास्तविक धुरी सममित है?

उदाहरण के लिए, एन = 6, पेड़ (0,1,5) (1,2,4,5) (2,3,4) वास्तविक लाइन पर तीन जंक्शन हैं, इसलिए यह सममित wrt है असली धुरी यदि (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

तो, वर्णन/प्रतिनिधित्व को देखते हुए, मैं अगर यह सममित wrt असली, काल्पनिक है कुछ एल्गोरिथ्म खोजने के लिए तय करने के लिए चाहते हैं, और घूर्णन 180 डिग्री। अंतिम उदाहरण में 180 डिग्री समरूपता है।

संपादित करें 2: यह वास्तव में मेरे शोध के लिए है। मैंने मैथोवरफ्लो पर भी सवाल पोस्ट किया है, लेकिन प्रतिस्पर्धा प्रोग्रामिंग में मेरे दिन मुझे बताते हैं कि यह एक आईओआई कार्य की तरह है। गणित में कोड उत्कृष्ट होगा, लेकिन जावा, पायथन, या किसी भी अन्य भाषा को मानव पर्याप्तताओं द्वारा पठनीय किया जा सकता है।

(ये समानताएं Schroedinger समीकरण, जो क्वांटम यांत्रिकी में अच्छा गुण है में क्षमता का विशेष प्रकार से मेल खाती है।)

Answer 1

के बाद से आप पहले से ही बिंदु पेड़ के लिए सेट के निर्माण के लिए एक एल्गोरिथ्म है, तो आप केवल जरूरत है यह निर्धारित करने के लिए कि बिंदु सेट में समरूपता फ्लिप है या नहीं। आदर्श रूप से आपके सेट को प्रतीकात्मक रूप से गणना की जाती है (और पाप (थेटा), कोस (थेटा) के मामले में छोड़ दिया जाता है) गैर तर्कसंगत बिंदुओं के लिए, जो ठीक है, क्योंकि आप गणित का उपयोग कर रहे हैं।

अब आप अगर अपनी बात सेट कुछ अक्ष के बारे में समरूपता है पता है, इसलिए एक मैट्रिक्स एक के रूप में फ्लिप/रोटेशन परिवर्तन का प्रतिनिधित्व करना चाहते हैं, और हम {x '} है = एक {x}। बाद के छवि सेट {x '} को क्रमबद्ध करें (अभिव्यक्तियों का उपयोग संख्यात्मक मान नहीं), और मूल बिंदु सेट {x} से तुलना करें। यदि कोई 1-1 पत्राचार नहीं है तो आपके पास एक समरूपता नहीं है अन्यथा आप करते हैं।

मुझे लगता है कि एक mathematica समारोह एक सेट में अद्वितीय भाव लगाने के लिए नहीं है (उदाहरण के लिए अनोखा [beforeImage] == अनोखा [afterimage])

Answer 2

आप बेहतर आप पेड़ की समरूपता से क्या मतलब है परिभाषित कर सकते हैं?

आप पहले का कहना है कि

"क्षेत्रों जटिल विमान में रहते हैं, और के लिए n भी, क्षेत्र 0 और n/2 असली धुरी से विभाजित कर रहे हैं, और क्षेत्रों समान रूप से कर रहे हैं । "

और आप समरूपता

wrt असली, काल्पनिक, और रोटेशन 180 डिग्री

मैं तो, उम्मीद करेंगे कि समानताएं विशुद्ध रूप से ज्यामितीय होगा खोजने के लिए चाहते हैं, लेकिन तब आपको उस कहते हैं, जस्टिन के जवाब पर टिप्पणी में

पेड़ खींचने के लिए एक कैनोनिकल तरीका भी नहीं है, और मेरी ड्राइंग एल्गोरिथ्म सभी संभव समानताएं सम्मान नहीं करता है एक पेड़ हो सकता है

आप ज्यामितीय समरूपता के लिए देख सकते कैसे करता है, तो पेड़ के कोने की स्थिति विशिष्ट विमान पर परिभाषित नहीं किया जा सकता है? इसके अलावा आपके द्वारा दिए गए कई भूखंडों में (एन = 6, यहां तक ​​कि) सेक्टर 0 और 3 एक्स अक्ष (असली धुरी) से विभाजित नहीं हैं, इसलिए मैं आपके स्वयं के चित्र गलत मानूंगा।

Answer 3

मैं इस लागू करने के लिए समय नहीं पड़ा है, शायद किसी को यहाँ इसे आगे ले सकता है: वृत्त का चतुर्थ भाग द्वारा

पहले विभाजन जंक्शनों, यह 4 पेड़ों की उपज चाहिए। {टीपीपी, टीएमपी, टीएमएम, टीपीएम} (प्लस के लिए पी, माइनस के लिए एम)। अब समरूपता के लिए जाँच एक दिशात्मक चौड़ाई पहले ट्रेवर्सल हो रहा है:

इसकी मेरी 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]];