ब्लॉक डिजाइन

This article is about block designs with fixed block size (uniform). For block designs with variable block sizes, see Combinatorial design. For experimental designs in statistics, see randomized block design.

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

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

सिंहावलोकन

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

डिज़ाइन को आमतौर पर अधूरा कहा जाता है (या माना जाता है), जिसका अर्थ है कि किसी भी ब्लॉक में सेट के सभी तत्व नहीं होते हैं, इस प्रकार एक तुच्छ डिज़ाइन को खारिज कर दिया जाता है।

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

ब्लॉक डिजाइन में बार-बार ब्लॉक हो भी सकते हैं और नहीं भी। दोहराए गए ब्लॉक के बिना डिज़ाइन सरल कहलाते हैं, इस मामले में ब्लॉक का परिवार multiset के बजाय एक सेट (गणित) है।

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

नियमित वर्दी डिजाइन (कॉन्फ़िगरेशन)

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

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

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

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

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

v	points, number of elements of X
b	number of blocks
r	number of blocks containing a given point
k	number of points in a block
λ	number of blocks containing any 2 (or more generally t) distinct points

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

$bk=vr,$ जोड़े (बी, पी) की संख्या की गणना करके प्राप्त किया गया जहां बी एक ब्लॉक है और पी उस ब्लॉक में एक बिंदु है, और

$\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-डिज़ाइनों में सममित डिज़ाइनों में सबसे कम संख्या में ब्लॉक होते हैं।

एक सममित डिजाइन में आर = के साथ ही साथ बी = वी, और, जबकि यह आम तौर पर मनमाना 2-डिजाइनों में सच नहीं है, एक सममित डिजाइन में प्रत्येक दो अलग-अलग ब्लॉक λ बिंदुओं में मिलते हैं। H. J. Ryser का एक प्रमेय इसका विलोम प्रदान करता है। यदि एक्स एक वी-तत्व सेट है, और बी के-तत्व उपसमुच्चय (ब्लॉक) का एक वी-तत्व सेट है, जैसे कि किसी भी दो अलग-अलग ब्लॉकों में बिल्कुल λ अंक आम हैं, तो (एक्स, बी) एक सममित ब्लॉक है डिज़ाइन। एक सममित डिजाइन के पैरामीटर संतुष्ट करते हैं

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

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

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

प्रक्षेपी विमान

Main article: Projective plane

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

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