श्रृंखला-समानांतर आंशिक क्रम

From alpha
Jump to navigation Jump to search
श्रृंखला-समानांतर आंशिक क्रम, हस्से आरेख के रूप में दिखाया गया है।

क्रम-सैद्धांतिक गणित में, श्रृंखला-समानांतर आंशिक क्रम आंशिक रूप से क्रमबद्ध समुच्चय है, जो दो सरल संरचना संचालन द्वारा छोटी श्रृंखला-समानांतर आंशिक क्रमों से निर्मित होता है।[1][2]

श्रृंखला-समानांतर आंशिक क्रमों को N-मुक्त परिमित आंशिक क्रमों के रूप में वर्णित किया जा सकता है; उनके पास क्रम आयाम अधिकतम दो हैं।[1][3] वे अशक्त क्रम और निर्देशित ट्री और निर्देशित श्रृंखला-समानांतर रेखांकन में पुन: योग्यता संबंध सम्मिलित हैं।[2][3] श्रृंखला-समानांतर आंशिक क्रमों की तुलनात्मकता रेखांकन कोग्राफ हैं।[2][4]

जॉब शॉप शेड्यूलिंग,[5] समय श्रृंखला डेटा में इवेंट अनुक्रमण की मशीन लर्निंग,[6] मल्टीमीडिया डेटा के प्रसारण अनुक्रमण,[7] और डेटाफ्लो प्रोग्रामिंग में थ्रूपुट अधिकतमकरण में श्रृंखला-समानांतर आंशिक क्रम प्रयुक्त किए गए हैं।[8]

श्रृंखला-समानांतर आंशिक क्रमों को बहुट्री भी कहा जाता है;[4] चूँकि, यह नाम अस्पष्ट है: बहुट्री आंशिक क्रम को भी संदर्भित करता है, जिसमें कोई चार-तत्व हीरा उपक्रम नहीं होता है[9] और कई ट्री से बनी अन्य संरचनाओं के लिए नहीं होता है।

परिभाषा

दो आंशिक क्रमित समुच्चय P और Q पर विचार करें। P और Q की श्रृंखला संरचना, P; Q लिखी गई है,[7] P * Q,[2] या P ⧀ Q,[1] आंशिक रूप से क्रमबद्ध समुच्चय है, जिसके अवयव P और Q के तत्वों के अलग संघ हैं। P; Q में, दो तत्व x और y दोनों P से संबंधित हैं या दोनों Q से संबंधित हैं, उनका समान क्रम संबंध है, जो वे क्रमशः P या Q में करते हैं। चूंकि, प्रत्येक जोड़ी x, y के लिए जहाँ x, P से संबंधित है और y, Q से संबंधित है, श्रृंखला संरचना में अतिरिक्त क्रम संबंध x ≤ y है। श्रृंखला संरचना साहचर्य संक्रिया है: इसे P; Q; R लिखा जा सकता है; तीन क्रमों की श्रृंखला संरचना के रूप में, अस्पष्टता के बिना कि कैसे उन्हें जोड़ी में संयोजित किया जाए, क्योंकि दोनों कोष्ठक (P; Q); R और P; (Q; R) उसी आंशिक क्रम का वर्णन करेंगे। चूँकि, यह कम्यूटेटिव ऑपरेशन नहीं है, क्योंकि P और Q की भूमिकाओं को परिवर्तित करने से अलग आंशिक क्रम उत्पन्न होगा, जो P में तत्व और Q में एक के साथ जोड़े के क्रम संबंधों को उलट देता है।[1]

P और Q की समानांतर संरचना, P || Q,[7] P + Q,[2] या P ⊕ Q इसी तरह परिभाषित की गयी है,[1] P में तत्वों और Q में तत्वों के असंयुक्त संघ से, तत्वों के जोड़े के साथ P या Q से संबंधित हैं, उसी क्रम में हैं जैसे वे क्रमशः P या Q में करते हैं। P || Q में, जोड़ी x, y अतुलनीय है, जब x P से संबंधित होता है और y Q से संबंधित होता है। समानांतर संरचना कम्यूटेटिव और साहचर्य दोनों होती है।[1]

श्रृंखला-समानांतर आंशिक क्रम का वर्ग आंशिक क्रम का समुच्चय है, जिसे इन दो परिचालनों का उपयोग करके एकल-तत्व आंशिक क्रम से बनाया जा सकता है। समतुल्य रूप से, यह आंशिक क्रमों का सबसे छोटा समुच्चय है, जिसमें एकल-तत्व आंशिक क्रम सम्मिलित हैं और श्रृंखला और समानांतर संरचना संचालन के अनुसार क्लोजर है।[1][2]

अशक्त क्रम संरचना संचालन के अनुक्रम से प्राप्त श्रृंखला समानांतर आंशिक क्रम है, जिसमें सभी समानांतर संरचनाएं पहले की जाती हैं, और फिर इन संरचनाओं के परिणाम केवल श्रृंखला संरचनाओं का उपयोग करके संयुक्त होते हैं।[2]


निषिद्ध उपक्रम लक्षण वर्णन

चार तत्वों a, b, c, और d के साथ आंशिक क्रम N और वास्तव में तीन क्रम संबंध a ≤ b ≥ c ≤ d फेंस या ज़िगज़ैग पोसेट का उदाहरण है; इसके हस्से आरेख में बड़े अक्षर N का आकार है। यह श्रृंखला-समानांतर नहीं है, क्योंकि इसे दो छोटे आंशिक क्रमों की श्रृंखला या समानांतर संरचना में विभाजित करने की कोई विधि नहीं है। आंशिक क्रम P को N-मुक्त कहा जाता है, यदि इसमें चार तत्वों का समुच्चय P उपस्थित नहीं है, जैसे कि उन तत्वों के लिए P का प्रतिबंध N के लिए क्रम-आइसोमॉर्फिक है। श्रृंखला-समानांतर आंशिक क्रम वास्तव में गैर-रिक्त परिमित N-मुक्त आंशिक क्रम हैं।[1][2][3]

यह इससे तुरंत अनुसरण करता है (चूंकि यह सीधे भी सिद्ध किया जा सकता है) कि श्रृंखला-समानांतर आंशिक क्रम का कोई भी गैर-रिक्त प्रतिबंध स्वयं श्रृंखला-समानांतर आंशिक क्रम है।[1]



क्रम आयाम

आंशिक क्रम P का क्रम आयाम, P के रियलाइजर का न्यूनतम आकार है, P के रैखिक विस्तार का समुच्चय, संपत्ति के साथ, जो P के प्रत्येक दो अलग-अलग तत्वों x और y के लिए, x ≤ y P में यदि और केवल यदि x की रिलीवर के प्रत्येक रैखिक विस्तार में y की तुलना में पहले की स्थिति है। श्रृंखला-समानांतर आंशिक क्रम में अधिकतम दो क्रम आयाम होते हैं। यदि P और Q के पास क्रमशः {L1, L2} और {L3, L4} रियलाइजर हैं, तो {L1L3, L2L4} श्रृंखला संयोजन P; Q का रियलाइजर है, और {L1L3, L4L2} समानांतर संरचना P || Q का रियलाइजर है।[2][3] आंशिक क्रम श्रृंखला-समानांतर होती है, यदि और केवल यदि उसके पास रियलाइजर है, जिसमें दो क्रमपरिवर्तनों में से एक पहचान है और दूसरा वियोज्य क्रमपरिवर्तन है।

यह ज्ञात है कि आंशिक क्रम P का क्रम आयाम दो है यदि और केवल यदि समान तत्वों पर कोई संयुग्मी क्रम Q उपस्थित है, इस संपत्ति के साथ कि कोई भी दो अलग-अलग तत्व x और y इन दो क्रमों में से किसी पर तुलनीय हैं। श्रृंखला समानांतर आंशिक क्रमों की स्थिति में, संयुग्मित क्रम जो स्वयं श्रृंखला समानांतर है, उसी क्रम में संरचना संचालन के अनुक्रम को उसी क्रम में प्राप्त किया जा सकता है, जो समान तत्वों पर P को परिभाषित करते हैं, लेकिन प्रत्येक समानांतर रचना के लिए P के अपघटन में और इसके विपरीत श्रृंखला संरचना का प्रदर्शन करते हैं। अधिक दृढ़ता से, चूंकि आंशिक क्रम में कई अलग-अलग संयुग्म हो सकते हैं, श्रृंखला समानांतर आंशिक क्रम के प्रत्येक संयुग्म को स्वयं श्रृंखला समानांतर होनी चाहिए।[2]


ग्राफ सिद्धांत से संबंध

किसी भी आंशिक क्रम को निर्देशित चक्रीय ग्राफ द्वारा दर्शाया जा सकता है (सामान्यतः एक से अधिक विधियों से) जिसमें x से y तक का रास्ता होता है, जब भी x और y x ≤ y के आंशिक क्रम के तत्व होते हैं। इस तरह से श्रृंखला-समानांतर आंशिक क्रमों का प्रतिनिधित्व करने वाले ग्राफ़ को वर्टेक्स श्रृंखला समानांतर ग्राफ़ कहा जाता है, और उनके सकर्मक कमी (आंशिक क्रम के कवरिंग संबंधों के ग्राफ़) को न्यूनतम वर्टेक्स श्रृंखला समानांतर ग्राफ़ कहा जाता है।[3] निर्देशित ट्री और (दो-टर्मिनल) श्रृंखला समानांतर रेखांकन न्यूनतम वर्टेक्स श्रृंखला समानांतर रेखांकन के उदाहरण हैं; इसलिए, श्रृंखला समानांतर आंशिक क्रमों का उपयोग निर्देशित ट्री और श्रृंखला समानांतर रेखांकन में पुन: योग्यता संबंधों का प्रतिनिधित्व करने के लिए किया जा सकता है।[2][3]

आंशिक क्रम का तुलनीयता ग्राफ प्रत्येक तत्व के लिए शीर्ष के साथ अप्रत्यक्ष ग्राफ है और अलग-अलग तत्वों x, y की प्रत्येक जोड़ी के लिए x ≤ y या y ≤ x के साथ अप्रत्यक्ष किनारा है। अर्थात्, यह प्रत्येक किनारे के उन्मुखीकरण को भूलकर न्यूनतम वर्टेक्स श्रृंखला समानांतर ग्राफ से बनता है। श्रृंखला-समानांतर आंशिक क्रम का तुलनीयता ग्राफ कॉग्राफ है: आंशिक क्रम की श्रृंखला और समानांतर संरचना संचालन तुलनात्मकता ग्राफ पर संचालन को जन्म देते हैं, जो दो उपग्राफ के असंयुक्त संघ का निर्माण करते हैं या जो सभी संभावित किनारों से दो उपग्राफ को जोड़ते हैं; ये दो ऑपरेशन मूल ऑपरेशन हैं, जिनसे कोग्राफ परिभाषित किए गए हैं। इसके विपरीत, प्रत्येक कोग्राफ श्रृंखला-समानांतर आंशिक क्रम का तुलनात्मक ग्राफ है। यदि आंशिक क्रम में इसकी तुलनात्मकता ग्राफ के रूप में कोग्राफ है, तो यह श्रृंखला-समानांतर आंशिक क्रम होना चाहिए, क्योंकि हर दूसरे प्रकार के आंशिक क्रम में N उप-क्रम होता है, जो इसकी तुलनात्मकता ग्राफ में प्रेरित चार-वर्टेक्स पथ के अनुरूप होगा, और कोग्राफ में ऐसे रास्ते प्रतिबंधित हैं।[2][4]


कम्प्यूटेशनल जटिलता

श्रृंखला-समानांतर आंशिक क्रमों के निषिद्ध उप-क्रम लक्षण वर्णन को एल्गोरिथ्म के आधार के रूप में उपयोग किया जा सकता है, जो परीक्षण करता है कि क्या दिया गया द्विआधारी संबंध श्रृंखला-समानांतर आंशिक क्रम है, जो संबंधित जोड़े की संख्या में रैखिक है।[2][3] वैकल्पिक रूप से, यदि आंशिक क्रम को निर्देशित एसाइक्लिक ग्राफ के रीचैबिलिटी क्रम के रूप में वर्णित किया गया है, तो यह परीक्षण करना संभव है कि क्या यह श्रृंखला-समानांतर आंशिक क्रम है, और यदि ऐसा है, तो इसके सकर्मक बंद होने की गणना करें, समय में वर्टिकल की संख्या के अनुपात में और सकर्मक बंद होने में किनारों में यह खुला रहता है कि क्या श्रृंखला-समानांतर पुन: योग्यता क्रमों को पहचानने का समय इनपुट ग्राफ के आकार में रैखिक होने के लिए सुधारा जा सकता है।[10]

यदि श्रृंखला-समानांतर आंशिक क्रम को अभिव्यक्ति ट्री के रूप में दर्शाया जाता है, जो श्रृंखला और समानांतर संरचना संचालन का वर्णन करता है, तो आंशिक क्रम के तत्वों को अभिव्यक्ति ट्री की लीव्स द्वारा दर्शाया जा सकता है। किसी भी दो तत्वों के बीच तुलना संबंधित दो लीव्स के सबसे कम सामान्य पूर्वज की खोज करके एल्गोरिथम द्वारा की जा सकती है; यदि वह पूर्वज समानांतर संरचना है, तो दो तत्व अतुलनीय हैं, और अन्यथा श्रृंखला संरचना संचालन का क्रम तत्वों के क्रम को निर्धारित करता है। इस तरह, n तत्वों पर श्रृंखला-समानांतर आंशिक क्रम O(n) अंतरिक्ष में किसी भी तुलना मूल्य को निर्धारित करने के लिए O(1)) समय के साथ प्रदर्शित किया जा सकता है।[2]

दो श्रृंखला-समानांतर आंशिक क्रमों P और Q के लिए परीक्षण करने के लिए यह NP-पूर्ण है, चाहे P में Q के लिए प्रतिबंध आइसोमोर्फिक सम्मिलित हो।[3]

चूंकि इच्छानुसार आंशिक क्रम के रैखिक विस्तार की संख्या की गणना करने की समस्या #P-पूर्ण है।[11] इसे श्रृंखला-समानांतर आंशिक क्रमों के लिए बहुपद समय में हल किया जा सकता है। विशेष रूप से, यदि L(P) आंशिक क्रम P के रैखिक विस्तार की संख्या को दर्शाता है, तब L(P; Q) = L(P)L(Q) और

इसलिए दिए गए श्रृंखला-समानांतर क्रम के अपघटन ट्री के रूप में अभिव्यक्ति ट्री का उपयोग करके रैखिक विस्तार की संख्या की गणना की जा सकती है।[2]


अनुप्रयोग

मनीला & मीक (2000) समय श्रृंखला डेटा में घटनाओं के अनुक्रम के लिए मॉडल के रूप में श्रृंखला-समानांतर आंशिक क्रम का उपयोग करते हैं। वे इस प्रकार के मॉडल का अनुमान लगाने के लिए मशीन लर्निंग एल्गोरिदम का वर्णन करते हैं, और छात्र नामांकन डेटा और मॉडलिंग वेब ब्राउज़र उपयोग पैटर्न से पाठ्यक्रम की पूर्वापेक्षाओं का अनुमान लगाने में इसकी प्रभावशीलता प्रदर्शित करते हैं।[6]

आमेर et al. (1994) तर्क देते हैं कि श्रृंखला-समानांतर आंशिक क्रम मल्टीमीडिया प्रस्तुतियों की संचरण अनुक्रमण आवश्यकताओं के मॉडलिंग के लिए उपयुक्त हैं। वे मल्टीमीडिया ट्रांसमिशन एल्गोरिदम के विश्लेषण के आधार के रूप में श्रृंखला-समानांतर आंशिक क्रम के रैखिक एक्सटेंशन की संख्या की गणना करने के लिए सूत्र का उपयोग करते हैं।[7]

चौधरी et al. (1994) कंप्यूटर दृष्टि के लिए बड़े पैमाने पर डेटा प्रोसेसिंग के डेटा प्रवाह मॉडल में कार्य निर्भरताओं को मॉडल करने के लिए श्रृंखला-समानांतर आंशिक क्रम का उपयोग करते हैं। वे दिखाते हैं कि, इस समस्या के लिए श्रृंखला-समानांतर क्रमों का उपयोग करके, अनुकूलित शेड्यूल का कुशलतापूर्वक निर्माण करना संभव है, जो प्रणाली के थ्रूपुट को अनुकूलित करने के लिए समानांतर कंप्यूटिंग प्रणाली के विभिन्न प्रोसेसरों को अलग-अलग कार्य प्रदान करता है।[8]

श्रृंखला-समानांतर आंशिक क्रमों की तुलना में कुछ अधिक सामान्य क्रमों का वर्ग PQ ट्री द्वारा प्रदान किया जाता है, डेटा संरचनाएं जो एल्गोरिदम में परीक्षण के लिए प्रयुक्त की गई हैं कि क्या ग्राफ़ प्लेनर ग्राफ है और अंतराल ग्राफ को पहचानता है।[12] PQ ट्री का एपी नोड अपने चाइल्ड के सभी संभावित क्रमिंग की अनुमति देता है, जैसे आंशिक क्रम की समांतर संरचना, जबकि Q नोड को आंशिक क्रम की श्रृंखला संरचना की तरह निश्चित रैखिक क्रम में चाइल्ड की आवश्यकता होती है। चूँकि, श्रृंखला-समानांतर आंशिक क्रमों के विपरीत, PQ ट्री किसी भी Q नोड के रैखिक क्रम को उलटने की अनुमति देते हैं।

यह भी देखें

  • श्रृंखला और समांतर परिपथ

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Bechet, Denis; De Groote, Philippe; Retoré, Christian (1997), "A complete axiomatisation for the inclusion of series-parallel partial orders", Rewriting Techniques and Applications, Lecture Notes in Computer Science, vol. 1232, Springer-Verlag, pp. 230–240, doi:10.1007/3-540-62950-5_74.
  2. ↑ 2.00 2.01 2.02 2.03 2.04 2.05 2.06 2.07 2.08 2.09 2.10 2.11 2.12 2.13 2.14 Möhring, Rolf H. (1989), "Computationally tractable classes of ordered sets", in Rival, Ivan (ed.), Algorithms and Order: Proceedings of the NATO Advanced Study Institute on Algorithms and Order, Ottawa, Canada, May 31-June 13, 1987, NATO Science Series C, vol. 255, Springer-Verlag, pp. 105–194, ISBN 978-0-7923-0007-6.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L. (1982), "The recognition of series parallel digraphs", SIAM Journal on Computing, 11 (2): 298–313, doi:10.1137/0211023.
  4. ↑ 4.0 4.1 4.2 Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory, Series B, 24 (2): 125–133, doi:10.1016/0095-8956(78)90013-8, MR 0491356.
  5. ↑ Lawler, Eugene L. (1978), "Sequencing jobs to minimize total weighted completion time subject to precedence constraints", Annals of Discrete Mathematics, 2: 75–90, doi:10.1016/S0167-5060(08)70323-6, ISBN 9780720410433, MR 0495156.
  6. ↑ 6.0 6.1 Mannila, Heikki; Meek, Christopher (2000), "Global partial orders from sequential data", Proc. 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2000), pp. 161–168, doi:10.1145/347090.347122, S2CID 14735932.
  7. ↑ 7.0 7.1 7.2 7.3 Amer, Paul D.; Chassot, Christophe; Connolly, Thomas J.; Diaz, Michel; Conrad, Phillip (1994), "Partial-order transport service for multimedia and other applications", IEEE/ACM Transactions on Networking, 2 (5): 440–456, doi:10.1109/90.336326, S2CID 1974607.
  8. ↑ 8.0 8.1 Choudhary, A. N.; Narahari, B.; Nicol, D. M.; Simha, R. (1994), "Optimal processor assignment for a class of pipelined computations", IEEE Transactions on Parallel and Distributed Systems, 5 (4): 439–445, doi:10.1109/71.273050, S2CID 5588390.
  9. ↑ Furnas, George W.; Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure", Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94), pp. 330–336, doi:10.1145/191666.191778, S2CID 18710118.
  10. ↑ Ma, Tze-Heng; Spinrad, Jeremy (1991), "Transitive closure for restricted classes of partial orders", Order, 8 (2): 175–183, doi:10.1007/BF00383402, S2CID 120935610.
  11. ↑ Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order, 8 (3): 225–242, doi:10.1007/BF00383444, S2CID 119697949.
  12. ↑ Booth, Kellogg S.; Lueker, George S. (1976), "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms", Journal of Computer and System Sciences, 13 (3): 335–379, doi:10.1016/S0022-0000(76)80045-1.
Retrieved from "https://alpha.indicwiki.in/index.php?title=श्रृंखला-समानांतर_आंशिक_क्रम&oldid=170257"