ब्रुइज़न टोरस
File:De bruijn torus 3x3.stlसाहचर्य गणित में, एक डी ब्रुइज़न टोरस, जिसका नाम डच गणितज्ञ निकोलस गोवर्ट डी ब्रुइज़न के नाम पर रखा गया है, एक वर्णमाला (अक्सर केवल 0 और 1) के प्रतीकों का एक मैट्रिक्स (गणित) है जिसमें दिए गए आयामों के हर संभव मैट्रिक्स (गणित) शामिल होते हैं। m × n बिलकुल एक बार. यह एक टोरस्र्स है क्योंकि मैट्रिक्स खोजने के उद्देश्य से किनारों को रैपराउंड माना जाता है। इसका नाम डी ब्रुइज़न अनुक्रम से आया है, जिसे एक विशेष मामला माना जा सकता है n = 1 (एक आयाम).
डी ब्रुइजन तोरी के संबंध में मुख्य खुले प्रश्नों में से एक यह है कि क्या किसी विशेष वर्णमाला आकार के लिए डी ब्रुइजन टोरस का निर्माण किया जा सकता है m और n. ज्ञातव्य है कि ये सदैव विद्यमान रहते हैं n = 1, तब से हमें बस डी ब्रुइज़न अनुक्रम मिलते हैं, जो हमेशा मौजूद रहते हैं। यह भी ज्ञात है कि वर्गाकार तोरी जब भी अस्तित्व में होती है m = n और सम (विषम स्थिति के लिए परिणामी टोरी वर्गाकार नहीं हो सकती)।[1][2][3] सबसे छोटा संभव बाइनरी वर्ग डी ब्रुइज़न टोरस, ऊपर दाईं ओर दर्शाया गया है, जिसे इस रूप में दर्शाया गया है (4,4;2,2)2 डी ब्रुइज़न टोरस (या बस के रूप में B2), सभी शामिल हैं 2×2 बाइनरी मैट्रिसेस।
बी2
अनुवाद, व्युत्क्रम (0s और 1s का आदान-प्रदान) और घूर्णन (90 डिग्री तक) के अलावा, कोई अन्य नहीं (4,4;2,2)2 डी ब्रुइज़न तोरी संभव हैं - यह सभी 2 के पूर्ण निरीक्षण द्वारा दिखाया जा सकता है16 बाइनरी मैट्रिक्स (या 0 और 1 की समान संख्या जैसी बाधाओं को पूरा करने वाला उपसमुच्चय)।[4]
n−1 पंक्तियों और स्तंभों को दोहराकर टोरस को अनियंत्रित किया जा सकता है। बिना रैपराउंड के सभी n×n सबमैट्रिस, जैसे कि एक छायांकित पीला, फिर पूरा सेट बनाते हैं:
1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 1
बड़ा उदाहरण: बी4
_2_de_Bruijn_torus.svg)
ग्रिड 4×4 मैट्रिक्स में से कुछ को हाइलाइट करता है, जिसमें ऊपरी मार्जिन पर शून्य मैट्रिक्स और मैट्रिक्स शामिल हैं।
अगले संभावित बाइनरी स्क्वायर डी ब्रुइज़न टोरस का एक उदाहरण, (256,256;4,4)2 (संक्षिप्त रूप में बी4), स्पष्ट रूप से निर्मित किया गया है।[5]
दाईं ओर की छवि इसका एक उदाहरण दिखाती है (256,256;4,4)2 डी ब्रुइज़न टोरस / ऐरे, जहां शून्य को क्रमशः सफेद और शून्य को लाल पिक्सेल के रूप में एन्कोड किया गया है।
बड़े आकार की बाइनरी डी ब्रुइज़न टोरी
वह पेपर जिसमें का एक उदाहरण है (256,256;4,4)2 डी ब्रुइज़न टोरस का निर्माण बाइनरी के 10 से अधिक पृष्ठों से किया गया था, इसके कम फ़ॉन्ट आकार के बावजूद, सरणी की प्रति पंक्ति तीन पंक्तियों की आवश्यकता होती है।
बाद में संभावित बाइनरी डी ब्रुइज़न टोरस, जिसमें सभी बाइनरी शामिल हैं 6×6 मैट्रिसेस, होगा 236 = 68,719,476,736 प्रविष्टियाँ, आयाम की एक वर्गाकार सरणी उत्पन्न करती हैं 262,144×262,144, निरूपित ए (262144,262144;6,6)2 डी ब्रुइज़न टोरस या बस बी6. इसे आसानी से कंप्यूटर पर संग्रहीत किया जा सकता है - यदि 0.1 मिमी किनारे के पिक्सेल के साथ मुद्रित किया जाता है, तो ऐसे मैट्रिक्स को लगभग 26×26 वर्ग मीटर के क्षेत्र की आवश्यकता होगी।
वस्तु बी8, जिसमें सभी बाइनरी शामिल हैं 8×8 आव्यूह और निरूपित (4294967296,4294967296;8,8)2, का योग 2 है64 ≈ 18.447×1018 प्रविष्टियाँ: ऐसे मैट्रिक्स को संग्रहीत करने के लिए 18.5 एक्ज़ाबिट, या 2.3 एक्साबाइट भंडारण की आवश्यकता होगी। उपरोक्त पैमाने पर, यह 429×429 वर्ग किलोमीटर को कवर करेगा।
निम्न तालिका सुपर-घातीय वृद्धि को दर्शाती है।
| n | Cells in a submatrix = n2 |
Number of submatrices = 2n2 |
Bn side length = 2(n2/2) |
|---|---|---|---|
| 2 | 4 | 16 | 4 |
| 4 | 16 | 65 536 | 256 |
| 6 | 36 | 68 719 476 736 | 262 144 |
| 8 | 64 | ~1.84×1019 | ~4.29×109 |
| 10 | 100 | ~1.27×1030 | ~1.13×1015 |
| 12 | 144 | ~2.23×1043 | ~4.72×1021 |
| 14 | 196 | ~1.00×1059 | ~3.17×1029 |
| 16 | 256 | ~1.16×1077 | ~3.40×1038 |
| 18 | 324 | ~3.42×1097 | ~5.85×1048 |
| 20 | 400 | ~2.60×10120 | ~1.61×1060 |
यह भी देखें
- डी ब्रुइन अनुक्रम
- डी ब्रुइन ग्राफ
संदर्भ
- ↑ Fan, C. T.; Fan, S. M.; Ma, S. L.; Siu, M. K. (1985). "On de Bruijn arrays". Ars Combinatoria A. 19: 205–213.
- ↑ Chung, F.; Diaconis, P.; Graham, R. (1992). "Universal cycles for combinatorial structures". Discrete Mathematics. 110 (1): 43–59. doi:10.1016/0012-365x(92)90699-g.
- ↑ Jackson, Brad; Stevens, Brett; Hurlbert, Glenn (Sep 2009). "ग्रे कोड और सार्वभौमिक चक्रों पर अनुसंधान समस्याएं". Discrete Mathematics. 309 (17): 5341–5348. doi:10.1016/j.disc.2009.04.002.
- ↑ Eggen, Bernd R. (1990). "The Binatorix B2". Private communication.
- ↑ Shiu, Wai-Chee (1997). "Decoding de Bruijn arrays constructed by the FFMS method". Ars Combinatoria. 47 (17): 33–48.
