ब्लॉक डिजाइन

This article is about निश्चित ब्लॉक आकार के साथ ब्लॉक डिजाइन (वर्दी). For चर ब्लॉक आकार के साथ ब्लॉक डिजाइन, see संयोजन डिजाइन. For प्रायोगिक डिजाइन सांख्यिकी में, see यादृच्छिक खण्ड अभिकल्पना.

साहचर्य गणित में, ब्लॉक संरचना घटना संरचना है जिसमें उपसमुच्चय के परिवार के साथ मिलकर समुच्चय होता है जिसे 'ब्लॉक' के रूप में जाना जाता है, इस तरह चुना जाता है कि तत्वों की आवृत्ति कुछ शर्तों को पूरा करती है जिससे ब्लॉक का संग्रह समरूपता (संतुलन) प्रदर्शित करता है। ब्लॉक संरचनाों में प्रयोगात्मक संरचना, परिमित ज्यामिति, भौतिक रसायन शास्त्र, सॉफ़्टवेयर परीक्षण, क्रिप्टोग्राफी और बीजगणितीय ज्यामिति सहित कई क्षेत्रों में अनुप्रयोग हैं।

आगे विशिष्टताओं के बिना 'ब्लॉक संरचना' शब्द सामान्यतः संतुलित अपूर्ण ब्लॉक संरचना (बीआईबीडी) को संदर्भित करता है, विशेष रूप से (और समानार्थक रूप से) 2-संरचना, जो संरचना में इसके अनुप्रयोग के कारण ऐतिहासिक रूप से सबसे गहन अध्ययन प्रकार रहा है। इसके प्रयोगों का सामान्यीकरण को t-संरचना के रूप में जाना जाता है।

अवलोकन

संरचना को संतुलित (t तक) कहा जाता है यदि मूल समुच्चय के सभी t-उपसमुच्चय समान रूप से कई (यानी, λ) ब्लॉकों में होते हैं। जब t निर्दिष्ट नहीं होता है, तो इसे सामान्यतः 2 माना जा सकता है, जिसका अर्थ है कि तत्वों की प्रत्येक जोड़ी समान संख्या में ब्लॉक में पाई जाती है और संरचना जोड़ीदार संतुलित है। t = 1 के लिए, प्रत्येक तत्व समान संख्या में ब्लॉक (प्रतिकृति संख्या, निरूपित r) में होता है और संरचना को नियमित कहा जाता है। t तक संतुलित कोई भी संरचना t के सभी निचले मूल्यों (चूंकि विभिन्न λ-मानों के साथ) में भी संतुलित है, इसलिए उदाहरण के लिए जोड़ीदार संतुलित (t = 2) संरचना भी नियमित (t = 1) है। जब संतुलन की आवश्यकता विफल हो जाती है, तब भी संरचना आंशिक रूप से संतुलित हो सकता है यदि t-उपसमुच्चय को n वर्गों में विभाजित किया जा सकता है, प्रत्येक का अपना (अलग) λ-मूल्य है। t = 2 के लिए इन्हें 'पीबीआईबीडी (n) संरचना' के रूप में जाना जाता है, जिनकी कक्षाएं संघ योजना बनाती हैं।

संरचना को सामान्यतः अधूरा कहा जाता है (या माना जाता है), जिसका अर्थ है कि किसी भी ब्लॉक में समुच्चय के सभी तत्व नहीं होते हैं, इस प्रकार तुच्छ संरचना को निष्फल कर दिया जाता है।

ब्लॉक संरचना जिसमें सभी ब्लॉकों का आकार समान होता है (सामान्यतः k को निरूपित किया जाता है) को समान या उचित कहा जाता है। इस आलेख में चर्चा की गई संरचना सभी समान हैं। ब्लॉक संरचना जो आवश्यक रूप से एक समान नहीं हैं, का भी अध्ययन किया गया है; t = 2 के लिए वे साहित्य में सामान्य नाम कॉम्बिनेटरियल संरचना जोड़ीदार संतुलित संरचना (पीबीडी) के अंतर्गत जाने जाते हैं।

ब्लॉक संरचना में बार-बार ब्लॉक हो भी सकते हैं और नहीं भी दोहराए गए ब्लॉक के बिना संरचना सरल कहलाते हैं, इस स्थितियों में ब्लॉक का परिवार बहु-समुच्चय के अतिरिक्त समुच्चय (गणित) है।

आँकड़ों में, ब्लॉक संरचना की अवधारणा को गैर-बाइनरी ब्लॉक संरचनाों तक बढ़ाया जा सकता है, जिसमें ब्लॉक में तत्व की कई प्रतियां हो सकती हैं (ब्लॉकिंग (आँकड़े) देखें)। वहां, संरचना जिसमें प्रत्येक तत्व एक ही कुल संख्या में होता है, उसे समकक्ष कहा जाता है, जिसका अर्थ केवल नियमित संरचना होता है, जब संरचना भी द्विआधारी होता है। गैर-बाइनरी संरचना की घटना मैट्रिक्स प्रत्येक ब्लॉक में प्रत्येक तत्व के दोहराए जाने की संख्या को सूचीबद्ध करती है।

नियमित यूनिफार्म संरचना (विन्यास)

सबसे सरल प्रकार की संतुलित संरचना (t = 1) को 'सामरिक विन्यास' या '1-संरचना' के रूप में जाना जाता है। ज्यामिति में संबंधित घटना संरचना को 'विन्यास' के रूप में जाना जाता है, विन्यास (ज्यामिति) देखें। ऐसा संरचना एक समान और नियमित है: प्रत्येक ब्लॉक में k तत्व होते हैं और प्रत्येक तत्व r ब्लॉक में समाहित होता है। समुच्चय तत्वों की संख्या v और ब्लॉकों की संख्या b से संबंधित हैं $bk=vr$, जो तत्वों की घटनाओं की कुल संख्या है।

निरंतर पंक्ति और स्तंभ योगों वाला प्रत्येक बाइनरी मैट्रिक्स नियमित यूनिफार्म ब्लॉक संरचना का घटना मैट्रिक्स है। इसके अतिरिक्त, प्रत्येक विन्यास में संबंधित बिरेगुलर ग्राफ द्विपक्षीय ग्राफ ग्राफ (असतत गणित) होता है जिसे इसकी घटना या v ग्राफ के रूप में जाना जाता है।

जोड़ीदार संतुलित यूनिफार्म संरचना (2-संरचना या बीआईबीडी)

परिमित समुच्चय X (बिंदु कहे जाने वाले तत्वों का) और पूर्णांक k, r, λ ≥ 1 को देखते हुए, हम 2-संरचना (या बीआईबीडी, संतुलित अपूर्ण ब्लॉक संरचना के लिए खड़े) B को परिभाषित करते हैं, जो कि X के k-तत्व उपसमुचय का परिवार है। , ब्लॉक कहा जाता है, जैसे कि X में कोई भी x r ब्लॉक में समाहित है, और X में अलग-अलग बिंदु x और y की कोई भी जोड़ी λ ब्लॉक में समाहित है। यहां, शर्त यह है कि x में कोई भी x r ब्लॉक में निहित है, जैसा कि नीचे दिखाया गया है।

यहाँ v (X के तत्वों की संख्या, जिसे बिंदु कहा जाता है), b (ब्लॉक की संख्या), k, r, और λ संरचना के पैरामीटर हैं। (पतित उदाहरणों से बचने के लिए, यह भी माना जाता है कि v > k, यद्यपि किसी भी ब्लॉक में समुच्चय के सभी तत्व सम्मिलित न हों। इन संरचनाों के नाम में अपूर्णता का यही अर्थ है।) तालिका में:

v	अंक, x के तत्वों की संख्या
b	ब्लॉक की संख्या
r	दिए गए बिंदु वाले ब्लॉकों की संख्या
k	ब्लॉक में अंकों की संख्या
λ	किसी भी 2 (या अधिक सामान्यतः t) अलग-अलग बिंदुओं वाले ब्लॉक की संख्या

संरचना को a (v, k, λ)-संरचना या a (v, b, r, k, λ)-संरचना कहा जाता है। पैरामीटर सभी स्वतंत्र नहीं हैं; v, k, और λ b और r निर्धारित करते हैं, और v, k, और λ के सभी संयोजन संभव नहीं हैं। इन मापदंडों को जोड़ने वाले दो मूलभूत समीकरण हैं।

$bk=vr,$

जोड़े (B, p) की संख्या की गणना करके प्राप्त किया गया जहां b ब्लॉक है और p उस ब्लॉक में बिंदु है। और

$\lambda (v-1)=r(k-1),$

निश्चित x के लिए गिनने से प्राप्त ट्रिपल (x, y, B) जहां x और y अलग-अलग बिंदु हैं और B ऐसा ब्लॉक है जिसमें ये दोनों सम्मिलित हैं। प्रत्येक x के लिए यह समीकरण यह भी सिद्ध करता है कि r स्थिर है (x से स्वतंत्र) भले ही इसे स्पष्ट रूप से ग्रहण न किया गया हो, इस प्रकार यह सिद्ध होता है कि x में कोई भी x r ब्लॉक में समाहित है, यह निरर्थक है और r की गणना अन्य मापदंडों से की जा सकती है।

ये शर्तें पर्याप्त नहीं हैं, उदाहरण के लिए, (43,7,1)-संरचना उपस्थित नहीं है।

2-संरचना का क्रम n = r − λ के रूप में परिभाषित किया गया है। 2-संरचना का 'पूरक' बिंदु समुच्चय X में प्रत्येक ब्लॉक को इसके पूरक के साथ बदलकर प्राप्त किया जाता है। यह 2-संरचना भी है और इसके पैरामीटर v′ = v, b′ = b, r′ = b − r हैं , k′ = v − k, λ′ = λ + b − 2r। 2-संरचना और उसके पूरक का एक ही क्रम है।

मौलिक प्रमेय, फिशर की असमानता, जिसका नाम सांख्यिकीविद् रोनाल्ड फिशर के नाम पर रखा गया है, वह किसी भी 2-संरचना में b ≥ v है।

उदाहरण

अद्वितीय (6,3,2)-संरचना (v = 6, k = 3, λ = 2) में 10 ब्लॉक (b = 10) हैं और प्रत्येक तत्व को 5 बार (r = 5) दोहराया जाता है। प्रतीकों 0 − 5 का उपयोग करते हुए, ब्लॉक निम्नलिखित त्रिगुण हैं।

012 013 024 035 045 125 134 145 234 235

और संबंधित घटना मैट्रिक्स v × b बाइनरी मैट्रिक्स निरंतर पंक्ति योग r और निरंतर स्तंभ योग k के साथ) है:

${\begin{pmatrix}1&1&1&1&1&0&0&0&0&0\\1&1&0&0&0&1&1&1&0&0\\1&0&1&0&0&1&0&0&1&1\\0&1&0&1&0&0&1&0&1&1\\0&0&1&0&1&0&1&1&1&0\\0&0&0&1&1&1&0&1&0&1\\\end{pmatrix}}$

चार गैर-समरूपी (8,4,3)-संरचनाों में से में 14 ब्लॉक हैं जिनमें प्रत्येक तत्व को 7 बार दोहराया गया है। प्रतीकों 0 − 7 का उपयोग करते हुए ब्लॉक निम्नलिखित 4-ट्यूपल हैं::

0123 0124 0156 0257 0345 0367 0467 1267 1346 1357 1457 2347 2356 2456

अद्वितीय (7,3,1)-संरचना सममित है और इसमें 7 ब्लॉक हैं जिनमें प्रत्येक तत्व को 3 बार दोहराया गया है। प्रतीकों 0 − 6 का उपयोग करते हुए, ब्लॉक निम्नलिखित त्रिक हैं::

013 026 045 124 156 235 346

यह संरचना फानो समतल के साथ जुड़ा हुआ है, संरचना फ़ानो समतल के तत्वों और ब्लॉकों के साथ समतल के बिंदु और रेखा के लिए ब्लॉक संरचना सिद्धांत है। इसके संबंधित घटना मैट्रिक्स भी सममित हो सकते हैं।, यदि लेबल या ब्लॉक को सही विधियों से क्रमबद्ध किया गया हो:

$\left({\begin{matrix}1&1&1&0&0&0&0\\1&0&0&1&1&0&0\\1&0&0&0&0&1&1\\0&1&0&1&0&1&0\\0&1&0&0&1&0&1\\0&0&1&1&0&0&1\\0&0&1&0&1&1&0\end{matrix}}\right)$

सममित 2-संरचना (बाइंड)

फिशर की असमानता में समानता का स्थितियों, अर्थात, समान संख्या में बिंदुओं और ब्लॉकों के साथ 2-संरचना को सममित संरचना कहा जाता है। समान अंक वाले सभी 2-संरचनाों में सममित संरचनाों में सबसे कम संख्या में ब्लॉक होते हैं।

सममित संरचना में r = k साथ ही साथ b = v, और, जबकि यह सामान्यतः मनमाना 2-संरचनाों में सही नहीं है, सममित संरचना में प्रत्येक दो अलग-अलग ब्लॉक λ बिंदुओं में मिलते हैं। एच जे रायसर का प्रमेय इसका विलोम प्रदान करता है। यदि x एक v-तत्व समुच्चय है, और b के-तत्व उपसमुच्चय (ब्लॉक) का v-तत्व समुच्चय है, जैसे कि किसी भी दो अलग-अलग ब्लॉकों में बिल्कुल λ अंक सामान्य हैं, तो (x, B) सममित ब्लॉक संरचना है।

सममित संरचना के पैरामीटर संतुष्ट करते हैं।

$\lambda (v-1)=k(k-1).$

यह v पर मजबूत प्रतिबंध लगाता है, इसलिए अंकों की संख्या मनमानी से दूर है। ब्रुक-रेज़र-चावला प्रमेय इन मापदंडों के संदर्भ में सममित संरचना के अस्तित्व के लिए आवश्यक, लेकिन पर्याप्त नहीं, शर्तें देता है।

निम्नलिखित सममित 2-संरचनाों के महत्वपूर्ण उदाहरण हैं:

प्रक्षेपी सतह

Main article: प्रक्षेपी सतह

प्रक्षेपी प्लेन परिमित प्रक्षेपी प्लेन λ = 1 और ऑर्डर n> 1 के साथ सममित 2-संरचना हैं। इन संरचनाों के लिए सममित संरचना समीकरण बन जाता है:

$v-1=k(k-1).$