श्रृंखला-समानांतर आंशिक क्रम
आदेश सिद्धांत | ऑर्डर-सैद्धांतिक गणित में, एक श्रृंखला-समानांतर आंशिक क्रम एक आंशिक रूप से क्रमबद्ध सेट है जो दो सरल रचना संचालन द्वारा छोटी श्रृंखला-समानांतर आंशिक आदेशों से निर्मित होता है।[1][2]
श्रृंखला-समानांतर आंशिक आदेशों को एन-मुक्त परिमित आंशिक आदेशों के रूप में वर्णित किया जा सकता है; उनके पास आदेश आयाम अधिकतम दो हैं।[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]
निषिद्ध सबऑर्डर लक्षण वर्णन
आंशिक आदेश N चार तत्वों के साथ a, b, c, और d और बिल्कुल तीन क्रम संबंध a ≤ b ≥ c ≤ d फेंस (गणित) या ज़िगज़ैग पॉसेट का एक उदाहरण है; इसके हस्से आरेख में बड़े अक्षर N का आकार है। यह श्रृंखला-समानांतर नहीं है, क्योंकि इसे दो छोटे आंशिक आदेशों की श्रृंखला या समानांतर संरचना में विभाजित करने का कोई तरीका नहीं है। एक आंशिक आदेश P को एन-फ्री कहा जाता है अगर इसमें चार तत्वों का एक सेट मौजूद नहीं है P जैसे कि का प्रतिबंध P उन तत्वों के लिए ऑर्डर-आइसोमॉर्फिक है N. श्रृंखला-समानांतर आंशिक आदेश बिल्कुल गैर-रिक्त परिमित एन-मुक्त आंशिक आदेश हैं।[1][2][3]
यह इससे तुरंत अनुसरण करता है (हालांकि यह सीधे भी सिद्ध किया जा सकता है) कि श्रृंखला-समानांतर आंशिक क्रम का कोई भी गैर-रिक्त प्रतिबंध स्वयं एक श्रृंखला-समानांतर आंशिक आदेश है।[1]
आदेश आयाम
आंशिक आदेश का आदेश आयाम P के एक बोधकर्ता का न्यूनतम आकार है P, के रैखिक विस्तार का एक सेट P संपत्ति के साथ, प्रत्येक दो अलग-अलग तत्वों के लिए x और y का P, 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. अर्थात्, यह प्रत्येक किनारे के अभिविन्यास (ग्राफ सिद्धांत) को भूलकर एक न्यूनतम वर्टेक्स श्रृंखला समानांतर ग्राफ से बनता है। श्रृंखला-समानांतर आंशिक क्रम का तुलनीयता ग्राफ एक कॉग्राफ है: आंशिक क्रम की श्रृंखला और समानांतर रचना संचालन तुलनात्मकता ग्राफ पर संचालन को जन्म देते हैं जो दो सबग्राफ के असंयुक्त संघ का निर्माण करते हैं या जो सभी संभावित किनारों से दो सबग्राफ को जोड़ते हैं; ये दो ऑपरेशन मूल ऑपरेशन हैं जिनसे कोग्राफ परिभाषित किए गए हैं। इसके विपरीत, प्रत्येक कोग्राफ एक श्रृंखला-समानांतर आंशिक क्रम का तुलनात्मक ग्राफ है। यदि एक आंशिक क्रम में इसकी तुलनात्मकता ग्राफ के रूप में एक कोग्राफ है, तो यह एक श्रृंखला-समानांतर आंशिक क्रम होना चाहिए, क्योंकि हर दूसरे प्रकार के आंशिक क्रम में एक एन उप-क्रम होता है जो इसकी तुलनात्मकता ग्राफ में एक प्रेरित चार-वर्टेक्स पथ के अनुरूप होगा, और कोग्राफ में ऐसे रास्ते प्रतिबंधित हैं।[2][4]
कम्प्यूटेशनल जटिलता
श्रृंखला-समानांतर आंशिक आदेशों के निषिद्ध उप-आदेश लक्षण वर्णन को एक एल्गोरिथ्म के आधार के रूप में इस्तेमाल किया जा सकता है जो परीक्षण करता है कि क्या एक दिया गया द्विआधारी संबंध एक श्रृंखला-समानांतर आंशिक क्रम है, जो संबंधित जोड़े की संख्या में रैखिक है।[2][3]वैकल्पिक रूप से, यदि एक आंशिक आदेश को एक निर्देशित एसाइक्लिक ग्राफ के रीचैबिलिटी ऑर्डर के रूप में वर्णित किया गया है, तो यह परीक्षण करना संभव है कि क्या यह एक श्रृंखला-समानांतर आंशिक क्रम है, और यदि ऐसा है, तो इसके सकर्मक बंद होने की गणना करें, समय में वर्टिकल की संख्या के अनुपात में और सकर्मक बंद होने में किनारों; यह खुला रहता है कि क्या श्रृंखला-समानांतर पुन: योग्यता आदेशों को पहचानने का समय इनपुट ग्राफ के आकार में रैखिक होने के लिए सुधारा जा सकता है।[10] यदि एक श्रृंखला-समानांतर आंशिक क्रम को एक अभिव्यक्ति वृक्ष के रूप में दर्शाया जाता है जो श्रृंखला और समानांतर रचना संचालन का वर्णन करता है, तो आंशिक क्रम के तत्वों को अभिव्यक्ति वृक्ष की पत्तियों द्वारा दर्शाया जा सकता है। किसी भी दो तत्वों के बीच तुलना संबंधित दो पत्तियों के सबसे कम सामान्य पूर्वज की खोज करके एल्गोरिथम द्वारा की जा सकती है; यदि वह पूर्वज एक समानांतर रचना है, तो दो तत्व अतुलनीय हैं, और अन्यथा श्रृंखला रचना संचालन का क्रम तत्वों के क्रम को निर्धारित करता है। इस तरह, एक श्रृंखला-समानांतर आंशिक क्रम पर n तत्वों में प्रतिनिधित्व किया जा सकता है O(n) स्पेस के साथ O(1) किसी भी तुलना मान को निर्धारित करने का समय।[2]
दो श्रृंखला-समानांतर आंशिक आदेशों के लिए परीक्षण करने के लिए यह एनपी-पूर्ण है P और Q, चाहे P में एक आइसोमोर्फिक प्रतिबंध शामिल है Q.[3]
हालांकि एक मनमानी आंशिक क्रम के रैखिक विस्तार की संख्या की गणना करने की समस्या तीव्र-पी-पूर्ण है|#पी-पूर्ण,[11] इसे श्रृंखला-समानांतर आंशिक आदेशों के लिए बहुपद समय में हल किया जा सकता है। विशेष रूप से, अगर L(P) आंशिक क्रम के रैखिक विस्तार की संख्या को दर्शाता है P, तब L(P; Q) = L(P)L(Q) और
इसलिए दिए गए श्रृंखला-समानांतर क्रम के अपघटन वृक्ष के रूप में एक अभिव्यक्ति वृक्ष का उपयोग करके रैखिक विस्तार की संख्या की गणना की जा सकती है।[2]
अनुप्रयोग
Mannila & Meek (2000) समय श्रृंखला डेटा में घटनाओं के अनुक्रम के लिए एक मॉडल के रूप में श्रृंखला-समानांतर आंशिक आदेश का उपयोग करें। वे इस प्रकार के मॉडल का अनुमान लगाने के लिए मशीन लर्निंग एल्गोरिदम का वर्णन करते हैं, और छात्र नामांकन डेटा और मॉडलिंग वेब ब्राउज़र उपयोग पैटर्न से पाठ्यक्रम की पूर्वापेक्षाओं का अनुमान लगाने में इसकी प्रभावशीलता प्रदर्शित करते हैं।[6]
Amer et al. (1994) तर्क देते हैं कि श्रृंखला-समानांतर आंशिक आदेश मल्टीमीडिया प्रस्तुतियों की संचरण अनुक्रमण आवश्यकताओं के मॉडलिंग के लिए उपयुक्त हैं। वे मल्टीमीडिया ट्रांसमिशन एल्गोरिदम के विश्लेषण के आधार के रूप में श्रृंखला-समानांतर आंशिक क्रम के रैखिक एक्सटेंशन की संख्या की गणना करने के लिए सूत्र का उपयोग करते हैं।[7]
Choudhary et al. (1994) कंप्यूटर दृष्टि के लिए बड़े पैमाने पर डेटा प्रोसेसिंग के डेटा प्रवाह मॉडल में कार्य निर्भरताओं को मॉडल करने के लिए श्रृंखला-समानांतर आंशिक ऑर्डर का उपयोग करें। वे दिखाते हैं कि, इस समस्या के लिए श्रृंखला-समानांतर आदेशों का उपयोग करके, एक अनुकूलित शेड्यूल का कुशलतापूर्वक निर्माण करना संभव है जो सिस्टम के थ्रूपुट को अनुकूलित करने के लिए समानांतर कंप्यूटिंग सिस्टम के विभिन्न प्रोसेसरों को अलग-अलग कार्य प्रदान करता है।[8] श्रृंखला-समानांतर आंशिक आदेशों की तुलना में कुछ अधिक सामान्य क्रमों का एक वर्ग PQ ट्री द्वारा प्रदान किया जाता है, डेटा संरचनाएं जो एल्गोरिदम में परीक्षण के लिए लागू की गई हैं कि क्या एक ग्राफ़ प्लेनर ग्राफ है और अंतराल ग्राफ़ को पहचानता है।[12] एक पीक्यू पेड़ का एपी नोड अपने बच्चों के सभी संभावित ऑर्डरिंग की अनुमति देता है, जैसे आंशिक ऑर्डर की समांतर संरचना, जबकि एक क्यू नोड को आंशिक ऑर्डर की श्रृंखला संरचना की तरह एक निश्चित रैखिक क्रम में बच्चों की आवश्यकता होती है। हालाँकि, श्रृंखला-समानांतर आंशिक आदेशों के विपरीत, PQ पेड़ किसी भी Q नोड के रैखिक क्रम को उलटने की अनुमति देते हैं।
यह भी देखें
- श्रृंखला और समांतर सर्किट
संदर्भ
- ↑ 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.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.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.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.
- ↑ 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.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.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.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.
- ↑ 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.
- ↑ 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.
- ↑ Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order, 8 (3): 225–242, doi:10.1007/BF00383444, S2CID 119697949.
- ↑ 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.
