Domino tiling
ज्यामिति में, यूक्लिडियन तल में एक क्षेत्र की एक डोमिनोज़ टाइलिंग डोमिनोज़ द्वारा क्षेत्र का एक टेसेलेशन है, जो दो इकाई वर्गों के मिलन से बनी आकृतियाँ हैं जो किनारे से किनारे तक मिलती हैं। समान रूप से, यह क्षेत्र के प्रत्येक वर्ग के केंद्र में एक शीर्ष रखने और दो शीर्षों को जोड़ने से बने ग्रिड ग्राफ में एक सही मिलान है जब वे आसन्न वर्गों के अनुरूप होते हैं। ऊँचाई के कार्य दो आयामों में एक नियमित ग्रिड पर झुकाव के कुछ वर्गों के लिए, ग्रिड के शीर्षों से एक पूर्णांक को जोड़ने वाले ऊँचाई के कार्य को परिभाषित करना संभव है। उदाहरण के लिए, एक शतरंज की बिसात बनाएँ, ऊंचाई 0 के साथ एक नोड ठीक करें, फिर किसी भी नोड के लिए उससे एक रास्ता है। इस पथ पर प्रत्येक नोड की ऊँचाई को परिभाषित करें (अर्थात। वर्गों के कोने) पिछले नोड की ऊंचाई प्लस एक होने के लिए यदि पथ के दाईं ओर वर्ग काला है, और अन्यथा माइनस एक है। अधिक विवरण में पाया जा सकता है। थर्स्टन की ऊँचाई की स्थिति यह निर्धारित करने के लिए एक परीक्षण का वर्णन करती है कि क्या समतल में इकाई वर्गों के संघ के रूप में गठित एक सरल-जुड़े क्षेत्र में एक डोमिनोज़ टाइलिंग है। वह एक दिशाहीन ग्राफ बनाता है जिसके शीर्ष पर त्रि-आयामी पूर्णांक जाली में बिंदु (x, y, z) होते हैं, जहां प्रत्येक ऐसा बिंदु चार पड़ोसियों से जुड़ा होता हैः यदि x + y सम है, तो (x, y, z) (x + 1, y, z + 1), (x, y + 1, z-1), और (x, y-1, z-1) से जुड़ा होता है, जबकि यदि x + y विषम है, तो (x, y, z) (x + 1, y, z-1), (x-1, y, z-1), (x, y, z-1) से जुड़ा होता है। क्षेत्र की सीमा, जिसे (x, y) तल में पूर्णांक बिंदुओं के अनुक्रम के रूप में देखा जाता है, इस त्रि-आयामी ग्राफ में एक पथ पर विशिष्ट रूप से (एक बार शुरुआती ऊंचाई चुने जाने के बाद) उठती है। इस क्षेत्र के टाइल करने योग्य होने के लिए एक आवश्यक शर्त यह है कि इस मार्ग को तीन आयामों में एक साधारण बंद वक्र बनाने के लिए बंद होना चाहिए, हालांकि, यह स्थिति पर्याप्त नहीं है। सीमा पथ के अधिक सावधानीपूर्वक विश्लेषण का उपयोग करते हुए, थर्स्टन ने एक ऐसे क्षेत्र की टाइल क्षमता के लिए एक मानदंड दिया जो पर्याप्त के साथ-साथ आवश्यक भी था। जब m और n दोनों विषम होते हैं, तो सूत्र सही ढंग से शून्य संभव डोमिनोज़ झुकाव तक कम हो जाता है। एक विशेष मामला तब होता है जब आयत को एन डोमिनोज़ के साथ टाइल किया जाता हैः अनुक्रम फिबोनाची अनुक्रम तक कम हो जाता है। एक अन्य विशेष मामला m = n = 0,2,4,6,8,10,12 के साथ वर्गों के लिए होता है। इन संख्याओं को एक तिरछे-सममित मैट्रिक्स के प्फाफियन के रूप में लिखकर पाया जा सकता है जिनके आइगेनवैल्यू स्पष्ट रूप से पाए जा सकते हैं। इस तकनीक को कई गणित से संबंधित विषयों में लागू किया जा सकता है, उदाहरण के लिए, सांख्यिकीय यांत्रिकी में डायमर-डायमर सहसंयोजक कार्य की शास्त्रीय, द्वि-आयामी गणना में। किसी क्षेत्र के झुकाव की संख्या सीमा स्थितियों के प्रति बहुत संवेदनशील होती है, और क्षेत्र के आकार में स्पष्ट रूप से महत्वहीन परिवर्तनों के साथ नाटकीय रूप से बदल सकती है। यह n क्रम के एज़्टेक हीरे के झुकाव की संख्या से सचित्र है, जहाँ झुकाव की संख्या 2 (n + 1) n/2 है। यदि इसे 2 के बजाय बीच में 3 लंबी पंक्तियों के साथ क्रम n के "संवर्धित एज़्टेक हीरे" द्वारा प्रतिस्थापित किया जाता है, तो झुकाव की संख्या बहुत कम संख्या D (n, n), एक डेलानॉय संख्या तक गिर जाती है, जिसमें n में सुपर-एक्सपोनेंशियल वृद्धि के बजाय केवल एक्सपोनेंशियल होता है। केवल एक लंबी मध्य पंक्ति के साथ क्रम n के "कम एज़्टेक हीरे" के लिए, केवल एक टाइलिंग होती है। तातामी तातामी एक डोमिनोज़ (1x2 आयत) के आकार में जापानी फर्श चटाई हैं। इनका उपयोग कमरों को टाइल करने के लिए किया जाता है, लेकिन उन्हें कैसे रखा जा सकता है, इस बारे में अतिरिक्त नियमों के साथ। विशेष रूप से, आम तौर पर, जिन जंक्शनों पर तीन ततामी मिलते हैं, उन्हें शुभ माना जाता है, जबकि जिन जंक्शनों पर चार मिलते हैं, वे अशुभ होते हैं, इसलिए एक उचित ततामी टाइलिंग वह है जहां किसी भी कोने में केवल तीन ततामी मिलते हैं। एक अनियमित कमरे को टाटामी द्वारा टाइल करने की समस्या जो एक कोने में तीन से मिलती है, एनपी-पूर्ण है। सांख्यिकीय भौतिकी में अनुप्रयोग एक आवधिक डोमिनोज़ टाइलिंग और दो आयामी आवधिक जाली पर पूरी तरह से फ्रस्ट्रेटेड आइसिंग मॉडल के ग्राउंड स्टेट कॉन्फ़िगरेशन के बीच एक-से-एक पत्राचार होता है। यह देखने के लिए, हम ध्यान देते हैं कि जमीनी अवस्था में, स्पिन मॉडल के प्रत्येक प्लाकेट में बिल्कुल एक हताश बातचीत होनी चाहिए। इसलिए, दोहरे जाली से देखने पर, प्रत्येक हताश किनारे को 1x2 आयत द्वारा "कवर" किया जाना चाहिए, जैसे कि आयत पूरे जाली को फैलाते हैं और ओवरलैप नहीं करते हैं, या दोहरी जाली की एक डोमिनोज़ टाइलिंग। गौसी मुक्त क्षेत्र भी देखें, सामान्य स्थिति में ऊंचाई कार्य की स्केलिंग सीमा (उदाहरण के लिए, एक बड़े एज़्टेक हीरे की उत्कीर्ण डिस्क के अंदर) विकृत शतरंज की बिसात की समस्या, एक मानक 8 × 8 शतरंज की बिसात (या चेकरबोर्ड) के 62-वर्ग क्षेत्र के डोमिनोज़ टाइलिंग से संबंधित एक पहेली सांख्यिकीय यांत्रिकी नोट्स संदर्भ आगे पढ़ने के लिए संयोजन वास्तव में हल करने योग्य मॉडल जाली मॉडल मिलान (ग्राफ सिद्धांत) सांख्यिकीय यांत्रिकी टाइलिंग पहेलियाँ