प्रतिश्रृंखला: Difference between revisions
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
आंशिक रूप से क्रमित किए गए समुच्चय में सबसे बड़े प्रतिश्रृंखला का आकार इसकी चौड़ाई (आंशिक क्रम) के रूप में जाना जाता है। दिलवर्थ के प्रमेय द्वारा, यह श्रृंखलाओं की न्यूनतम संख्या (पूर्ण रूप से क्रमबद्ध उपसमुच्चय) के बराबर है जिसमें समुच्चय को विभाजित किया जा सकता है। [[आंशिक रूप से आदेशित सेट|आंशिक रूप से क्रमित समुच्चय]] की ऊंचाई (इसकी सबसे लंबी श्रृंखला की लंबाई) मिर्स्की के प्रमेय के बराबर होती है, जिसमें न्यूनतम संख्या में प्रतिश्रृंखला होते हैं, जिसमें समुच्चय को विभाजित किया जा सकता है। | आंशिक रूप से क्रमित किए गए समुच्चय में सबसे बड़े प्रतिश्रृंखला का आकार इसकी चौड़ाई (आंशिक क्रम) के रूप में जाना जाता है। दिलवर्थ के प्रमेय द्वारा, यह श्रृंखलाओं की न्यूनतम संख्या (पूर्ण रूप से क्रमबद्ध उपसमुच्चय) के बराबर है जिसमें समुच्चय को विभाजित किया जा सकता है। [[आंशिक रूप से आदेशित सेट|आंशिक रूप से क्रमित समुच्चय]] की ऊंचाई (इसकी सबसे लंबी श्रृंखला की लंबाई) मिर्स्की के प्रमेय के बराबर होती है, जिसमें न्यूनतम संख्या में प्रतिश्रृंखला होते हैं, जिसमें समुच्चय को विभाजित किया जा सकता है। | ||
परिमित आंशिक रूप से क्रमित समुच्चय में सभी प्रतिश्रृंखला के वर्ग को एक [[वितरण जाली|वितरणी जालक]] में बनाने के लिए संचालन में सम्मिलित होने और समागम के लिए दिया जा सकता है। परिमित समुच्चय के सभी उपसमुच्चयों के आंशिक रूप से क्रमबद्ध प्रणाली के लिए, समुच्चय समावेशन द्वारा क्रमित, प्रतिश्रृंखलाओं को [[स्पर्नर परिवार|स्पर्नर वर्ग]] कहा जाता है और उनकी जाली एक मुक्त वितरण वाली जाली है, जिसमें डेडेकिंड अवयवों की संख्या होती है। अधिक सामान्यतः, परिमित आंशिक रूप से क्रमित समुच्चय के प्रतिश्रृंखला की संख्या की गणना करना #P-पूर्ण है। | |||
== परिभाषाएँ == | == परिभाषाएँ == | ||
| Line 10: | Line 10: | ||
मान लीजिए कि <math>S</math> आंशिक रूप से क्रमित समुच्चय है। आंशिक रूप से क्रमित समुच्चय के दो अवयव <math>a</math> और <math>b</math> को तुलनात्मकता कहा जाता है यदि <math>a \leq b \text{ or } b \leq a</math>। यदि दो अवयव तुलनीय नहीं हैं, तो उन्हें अतुलनीय कहा जाता है; अर्थात्, <math>x</math> और <math>y</math> अतुलनीय हैं यदि न तो <math>x \leq y \text{ nor } y \leq x</math>। | मान लीजिए कि <math>S</math> आंशिक रूप से क्रमित समुच्चय है। आंशिक रूप से क्रमित समुच्चय के दो अवयव <math>a</math> और <math>b</math> को तुलनात्मकता कहा जाता है यदि <math>a \leq b \text{ or } b \leq a</math>। यदि दो अवयव तुलनीय नहीं हैं, तो उन्हें अतुलनीय कहा जाता है; अर्थात्, <math>x</math> और <math>y</math> अतुलनीय हैं यदि न तो <math>x \leq y \text{ nor } y \leq x</math>। | ||
<math>S</math> में एक श्रृंखला एक उपसमुच्चय <math>C \subseteq S</math> है जिसमें अवयवों का प्रत्येक युग्म तुलनीय है; अर्थात्, <math>C</math> [[कुल आदेश|पूर्णत: क्रमित संरचना]] है। <math>S</math> में एक प्रतिश्रृंखला, <math>S</math> का एक उपसमुच्चय <math>A</math> है जिसमें विभिन्न तत्वों का प्रत्येक युग्म अतुलनीय है; अर्थात्, <math>A</math> में किन्हीं दो भिन्न तत्वों के बीच कोई क्रम संबंध नहीं है। (यद्यपि, कुछ लेखक प्रतिश्रृंखला शब्द का उपयोग [[मजबूत एंटीचैन|दृढ प्रतिश्रृंखला]] के लिए करते हैं, एक उपसमुच्चय ऐसा है कि आंशिक रूप से क्रमित समुच्चय का कोई अवयव प्रतिश्रृंखला के दो अलग-अलग अवयवों से छोटा नहीं है।) | <math>S</math> में एक श्रृंखला एक उपसमुच्चय <math>C \subseteq S</math> है जिसमें अवयवों का प्रत्येक युग्म तुलनीय है; अर्थात्, <math>C</math> [[कुल आदेश|पूर्णत: क्रमित संरचना]] है। <math>S</math> में एक प्रतिश्रृंखला, <math>S</math> का एक उपसमुच्चय <math>A</math> है जिसमें विभिन्न तत्वों का प्रत्येक युग्म अतुलनीय है; अर्थात्, <math>A</math> में किन्हीं दो भिन्न तत्वों के बीच कोई क्रम संबंध नहीं है। (यद्यपि, कुछ लेखक प्रतिश्रृंखला शब्द का उपयोग [[मजबूत एंटीचैन|दृढ प्रतिश्रृंखला]] के लिए करते हैं, एक उपसमुच्चय ऐसा है कि आंशिक रूप से क्रमित समुच्चय का कोई अवयव प्रतिश्रृंखला के दो अलग-अलग अवयवों से छोटा नहीं है।) | ||
== ऊंचाई और चौड़ाई == | == ऊंचाई और चौड़ाई == | ||
एक अधिकतम प्रतिश्रृंखला एक प्रतिश्रृंखला है जो किसी भी अन्य प्रतिश्रृंखला का उचित उपसमुच्चय नहीं है। एक अधिकतम प्रतिश्रृंखला एक प्रतिश्रृंखला है जिसमें गणनांक कम से कम प्रत्येक दूसरे प्रतिश्रृंखला जितनी बड़ी होती है। {{em|आंशिक रूप से क्रमित समुच्चय की चौड़ाई अधिकतम}} प्रतिश्रृंखला का गणनांक है। कोई भी प्रतिश्रृंखला किसी भी श्रृंखला को अधिकतम | एक अधिकतम प्रतिश्रृंखला एक प्रतिश्रृंखला है जो किसी भी अन्य प्रतिश्रृंखला का उचित उपसमुच्चय नहीं है। एक अधिकतम प्रतिश्रृंखला एक प्रतिश्रृंखला है जिसमें गणनांक कम से कम प्रत्येक दूसरे प्रतिश्रृंखला जितनी बड़ी होती है। {{em|आंशिक रूप से क्रमित समुच्चय की चौड़ाई अधिकतम}} प्रतिश्रृंखला का गणनांक है। कोई भी प्रतिश्रृंखला किसी भी श्रृंखला को अधिकतम अवयव में प्रतिच्छेद कर सकता है, इसलिए, यदि हम किसी क्रम के अवयवों को <math>k</math> श्रृंखलाओं में विभाजित कर सकते हैं, तो क्रम की चौड़ाई अधिकतम <math>k</math> होनी चाहिए (यदि प्रतिश्रृंखला में <math>k</math> से अधिक अवयव हैं, कोष्ठ सिद्धांत द्वारा, इसके 2 अवयव एक ही श्रृंखला से संबंधित अन्तर्विरोध होंगे)। दिलवर्थ के प्रमेय में कहा गया है कि इस सीमा तक सदैव पहुंचा जा सकता है: सदैव एक प्रतिश्रृंखला स्थित होता है, और अवयवों का श्रृंखला में विभाजन होता है, जैसे कि श्रृंखला की संख्या प्रतिश्रृंखला में अवयवों की संख्या के बराबर होती है, जो कि चौड़ाई के बराबर भी होनी चाहिए।{{r|dilworth}} इसी प्रकार, एक आंशिक क्रम की {{em|ऊंचाई}} को एक श्रृंखला की अधिकतम गणनांक के रूप में परिभाषित किया जा सकता है। मिर्स्की के प्रमेय में कहा गया है कि परिमित ऊंचाई के किसी भी आंशिक क्रम में, ऊंचाई कम से कम प्रतिश्रृंखला के बराबर होती है जिसमें क्रम को विभाजित किया जा सकता है।{{r|mirsky}} | ||
== स्पर्नर वर्ग == | == स्पर्नर वर्ग == | ||
एक <math>n</math>-अवयव समुच्चय के उपसमुच्चय के समावेशन क्रम में | एक <math>n</math>-अवयव समुच्चय के उपसमुच्चय के समावेशन क्रम में प्रतिश्रृंखला को स्पर्नर वर्ग के रूप में जाना जाता है। विभिन्न स्पर्नर वर्गों की संख्या की गणना डेडेकिंड संख्याओं द्वारा की जाती है,{{r|kahn}} जिनमें से पहले कुछ संख्याएँ | ||
:2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 {{OEIS|id=A000372}} हैं। | :2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 {{OEIS|id=A000372}} हैं। | ||
यहां तक कि रिक्त समुच्चय की घात समुच्चय में दो प्रतिश्रृंखला होते हैं: एक में एक समुच्चय होता है (स्वयं रिक्त समुच्चय) और एक में कोई समुच्चय नहीं होता है। | यहां तक कि रिक्त समुच्चय की घात समुच्चय में दो प्रतिश्रृंखला होते हैं: एक में एक समुच्चय होता है (स्वयं रिक्त समुच्चय) और एक में कोई समुच्चय नहीं होता है। | ||
== | == संबद्ध और समागम संचालन == | ||
कोई भी प्रतिश्रृंखला <math>A</math> कम समुच्चय | कोई भी प्रतिश्रृंखला <math>A</math> कम समुच्चय | ||
<math display="block">L_A = \{x : \exists y \in A \mbox{ such that } x \leq y\}</math> से मेल खाता है। | <math display="block">L_A = \{x : \exists y \in A \mbox{ such that } x \leq y\}</math> से मेल खाता है। | ||
परिमित आंशिक क्रम में (या अधिक सामान्यतः [[आरोही श्रृंखला की स्थिति]] को संतुष्ट करने वाला आंशिक क्रम) सभी निचले समुच्चयों में यह रूप होता है। | परिमित आंशिक क्रम में (या अधिक सामान्यतः [[आरोही श्रृंखला की स्थिति]] को संतुष्ट करने वाला आंशिक क्रम) सभी निचले समुच्चयों में यह रूप होता है। किसी भी दो निचले समुच्चयों का मिलन एक और निचला समुच्चय है, और संयोजन संचालन इस प्रकार से प्रतिश्रृंखला पर एक संबद्ध संचालन से मेल खाता है : | ||
<math display=block>A \vee B = \{ x \in A \cup B : \nexists y \in A \cup B \mbox{ such that } x < y\}.</math> | <math display=block>A \vee B = \{ x \in A \cup B : \nexists y \in A \cup B \mbox{ such that } x < y\}.</math> | ||
इसी प्रकार, हम प्रतिश्रृंखला पर | इसी प्रकार, हम प्रतिश्रृंखला पर समागम संचालन को परिभाषित कर सकते हैं, जो निचले समुच्चयों के प्रतिच्छेदन के अनुरूप है: | ||
<math display=block>A \wedge B = \{ x \in L_A \cap L_B : \nexists y \in L_A \cap L_B \mbox{ such that } x < y\}.</math> | <math display=block>A \wedge B = \{ x \in L_A \cap L_B : \nexists y \in L_A \cap L_B \mbox{ such that } x < y\}.</math> | ||
एक समुच्चय के परिमित उपसमुच्चय के सभी परिमित प्रतिश्रृंखला पर सम्मिलित | एक समुच्चय <math>X</math> के परिमित उपसमुच्चय के सभी परिमित प्रतिश्रृंखला पर सम्मिलित होने और समागम संचालन एक वितरणात्मक जाली को परिभाषित करते हैं, जो <math>X</math> द्वारा उत्पन्न मुक्त वितरण जाली है। वितरणात्मक जाली के लिए बिरखॉफ के प्रतिनिधित्व प्रमेय में कहा गया है कि प्रत्येक परिमित वितरणी जालक को परिमित आंशिक क्रम के प्रतिश्रृंखला पर संबद्ध और समागम के संचालन के माध्यम से या आंशिक क्रम के निचले समुच्चय पर संयोजन और प्रतिच्छेदन के संचालन के रूप में प्रदर्शित किया जा सकता है।{{r|birkhoff}} | ||
== | == संगणनात्मक जटिलता == | ||
बहुपद समय में एक अधिकतम प्रतिश्रृंखला (और इसका आकार, आंशिक रूप से दिए गए समुच्चय की चौड़ाई) पाया जा सकता है।{{r|felragspin}} | बहुपद समय में एक अधिकतम प्रतिश्रृंखला (और इसका आकार, आंशिक रूप से दिए गए समुच्चय की चौड़ाई) पाया जा सकता है।{{r|felragspin}} दिए गए आंशिक रूप से क्रमित किए गए समुच्चय में प्रतिश्रृंखला की संख्या की गणना करना#P-पूर्ण है।{{r|provball}} | ||
दिए गए आंशिक रूप से क्रमित किए गए समुच्चय में प्रतिश्रृंखला की संख्या की गणना | |||
== संदर्भ == | == संदर्भ == | ||
Revision as of 23:41, 11 May 2023
गणित में, क्रम सिद्धांत के क्षेत्र में, एक प्रतिश्रृंखला आंशिक रूप से क्रमित किए गए समुच्चय का एक उपसमुच्चय है, जैसे कि उपसमुच्चय में दो अलग-अलग अवयव अतुलनीय हैं।
आंशिक रूप से क्रमित किए गए समुच्चय में सबसे बड़े प्रतिश्रृंखला का आकार इसकी चौड़ाई (आंशिक क्रम) के रूप में जाना जाता है। दिलवर्थ के प्रमेय द्वारा, यह श्रृंखलाओं की न्यूनतम संख्या (पूर्ण रूप से क्रमबद्ध उपसमुच्चय) के बराबर है जिसमें समुच्चय को विभाजित किया जा सकता है। आंशिक रूप से क्रमित समुच्चय की ऊंचाई (इसकी सबसे लंबी श्रृंखला की लंबाई) मिर्स्की के प्रमेय के बराबर होती है, जिसमें न्यूनतम संख्या में प्रतिश्रृंखला होते हैं, जिसमें समुच्चय को विभाजित किया जा सकता है।
परिमित आंशिक रूप से क्रमित समुच्चय में सभी प्रतिश्रृंखला के वर्ग को एक वितरणी जालक में बनाने के लिए संचालन में सम्मिलित होने और समागम के लिए दिया जा सकता है। परिमित समुच्चय के सभी उपसमुच्चयों के आंशिक रूप से क्रमबद्ध प्रणाली के लिए, समुच्चय समावेशन द्वारा क्रमित, प्रतिश्रृंखलाओं को स्पर्नर वर्ग कहा जाता है और उनकी जाली एक मुक्त वितरण वाली जाली है, जिसमें डेडेकिंड अवयवों की संख्या होती है। अधिक सामान्यतः, परिमित आंशिक रूप से क्रमित समुच्चय के प्रतिश्रृंखला की संख्या की गणना करना #P-पूर्ण है।
परिभाषाएँ
मान लीजिए कि आंशिक रूप से क्रमित समुच्चय है। आंशिक रूप से क्रमित समुच्चय के दो अवयव और को तुलनात्मकता कहा जाता है यदि । यदि दो अवयव तुलनीय नहीं हैं, तो उन्हें अतुलनीय कहा जाता है; अर्थात्, और अतुलनीय हैं यदि न तो ।
में एक श्रृंखला एक उपसमुच्चय है जिसमें अवयवों का प्रत्येक युग्म तुलनीय है; अर्थात्, पूर्णत: क्रमित संरचना है। में एक प्रतिश्रृंखला, का एक उपसमुच्चय है जिसमें विभिन्न तत्वों का प्रत्येक युग्म अतुलनीय है; अर्थात्, में किन्हीं दो भिन्न तत्वों के बीच कोई क्रम संबंध नहीं है। (यद्यपि, कुछ लेखक प्रतिश्रृंखला शब्द का उपयोग दृढ प्रतिश्रृंखला के लिए करते हैं, एक उपसमुच्चय ऐसा है कि आंशिक रूप से क्रमित समुच्चय का कोई अवयव प्रतिश्रृंखला के दो अलग-अलग अवयवों से छोटा नहीं है।)
ऊंचाई और चौड़ाई
एक अधिकतम प्रतिश्रृंखला एक प्रतिश्रृंखला है जो किसी भी अन्य प्रतिश्रृंखला का उचित उपसमुच्चय नहीं है। एक अधिकतम प्रतिश्रृंखला एक प्रतिश्रृंखला है जिसमें गणनांक कम से कम प्रत्येक दूसरे प्रतिश्रृंखला जितनी बड़ी होती है। आंशिक रूप से क्रमित समुच्चय की चौड़ाई अधिकतम प्रतिश्रृंखला का गणनांक है। कोई भी प्रतिश्रृंखला किसी भी श्रृंखला को अधिकतम अवयव में प्रतिच्छेद कर सकता है, इसलिए, यदि हम किसी क्रम के अवयवों को श्रृंखलाओं में विभाजित कर सकते हैं, तो क्रम की चौड़ाई अधिकतम होनी चाहिए (यदि प्रतिश्रृंखला में से अधिक अवयव हैं, कोष्ठ सिद्धांत द्वारा, इसके 2 अवयव एक ही श्रृंखला से संबंधित अन्तर्विरोध होंगे)। दिलवर्थ के प्रमेय में कहा गया है कि इस सीमा तक सदैव पहुंचा जा सकता है: सदैव एक प्रतिश्रृंखला स्थित होता है, और अवयवों का श्रृंखला में विभाजन होता है, जैसे कि श्रृंखला की संख्या प्रतिश्रृंखला में अवयवों की संख्या के बराबर होती है, जो कि चौड़ाई के बराबर भी होनी चाहिए।[1] इसी प्रकार, एक आंशिक क्रम की ऊंचाई को एक श्रृंखला की अधिकतम गणनांक के रूप में परिभाषित किया जा सकता है। मिर्स्की के प्रमेय में कहा गया है कि परिमित ऊंचाई के किसी भी आंशिक क्रम में, ऊंचाई कम से कम प्रतिश्रृंखला के बराबर होती है जिसमें क्रम को विभाजित किया जा सकता है।[2]
स्पर्नर वर्ग
एक -अवयव समुच्चय के उपसमुच्चय के समावेशन क्रम में प्रतिश्रृंखला को स्पर्नर वर्ग के रूप में जाना जाता है। विभिन्न स्पर्नर वर्गों की संख्या की गणना डेडेकिंड संख्याओं द्वारा की जाती है,[3] जिनमें से पहले कुछ संख्याएँ
- 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sequence A000372 in the OEIS) हैं।
यहां तक कि रिक्त समुच्चय की घात समुच्चय में दो प्रतिश्रृंखला होते हैं: एक में एक समुच्चय होता है (स्वयं रिक्त समुच्चय) और एक में कोई समुच्चय नहीं होता है।
संबद्ध और समागम संचालन
कोई भी प्रतिश्रृंखला कम समुच्चय
परिमित आंशिक क्रम में (या अधिक सामान्यतः आरोही श्रृंखला की स्थिति को संतुष्ट करने वाला आंशिक क्रम) सभी निचले समुच्चयों में यह रूप होता है। किसी भी दो निचले समुच्चयों का मिलन एक और निचला समुच्चय है, और संयोजन संचालन इस प्रकार से प्रतिश्रृंखला पर एक संबद्ध संचालन से मेल खाता है :
संगणनात्मक जटिलता
बहुपद समय में एक अधिकतम प्रतिश्रृंखला (और इसका आकार, आंशिक रूप से दिए गए समुच्चय की चौड़ाई) पाया जा सकता है।[5] दिए गए आंशिक रूप से क्रमित किए गए समुच्चय में प्रतिश्रृंखला की संख्या की गणना करना#P-पूर्ण है।[6]
संदर्भ
- ↑ Dilworth, Robert P. (1950), "A decomposition theorem for partially ordered sets", Annals of Mathematics, 51 (1): 161–166, doi:10.2307/1969503, JSTOR 1969503
- ↑ Mirsky, Leon (1971), "A dual of Dilworth's decomposition theorem", American Mathematical Monthly, 78 (8): 876–877, doi:10.2307/2316481, JSTOR 2316481
- ↑ Kahn, Jeff (2002), "Entropy, independent sets and antichains: a new approach to Dedekind's problem", Proceedings of the American Mathematical Society, 130 (2): 371–378, doi:10.1090/S0002-9939-01-06058-0, MR 1862115
- ↑ Birkhoff, Garrett (1937), "Rings of sets", Duke Mathematical Journal, 3 (3): 443–454, doi:10.1215/S0012-7094-37-00334-X
- ↑ Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Recognition algorithms for orders of small width and graphs of small Dilworth number", Order, 20 (4): 351–364 (2004), doi:10.1023/B:ORDE.0000034609.99940.fb, MR 2079151, S2CID 1363140
- ↑ Provan, J. Scott; Ball, Michael O. (1983), "The complexity of counting cuts and of computing the probability that a graph is connected", SIAM Journal on Computing, 12 (4): 777–788, doi:10.1137/0212053, MR 0721012
