हस्से आरेख

Not to be confused with हेस आरेख.

File:Inclusion ordering.svg

उपसमुच्चय द्वारा आदेशित 2-तत्व सबसमुच्चय का सत्ता स्थापित

क्रमबद्ध सिद्धांत में, हस्से आरेख (/ˈhæsə/; German: [ˈhasə]) एक प्रकार का गणितीय आरेख है जिसका उपयोग परिमित आंशिक रूप से क्रमबद्ध समुच्चय का प्रतिनिधित्व करने के लिए किया जाता है, इसकी सकर्मक कमी के ग्राफ आरेख के रूप में होता है । वस्तुतः, आंशिक रूप से क्रमबद्ध किए गए समुच्चय $(S,\leq )$ के लिए $S$ के प्रत्येक तत्व को समतल में एक शीर्ष (ग्राफ सिद्धांत) के रूप में प्रतिनिधित्व करता है और एक रेखा खंड या वक्र खींचता है जो एक शीर्ष $x$ से दूसरे शीर्ष $y$ तक ऊपर की ओर जाता है जब भी $x$ (अर्थात जब भी $x\neq y$, $x\leq y$ और $x\leq z\leq y$)के साथ $x$ और $y$ से अलग कोई $z$ नहीं है | ये वक्र एक दूसरे को काट सकते हैं किन्तु अपने अंतिम बिंदु के अतिरिक्त किसी भी कोने को नहीं छूना चाहिए। इस तरह का आरेख, स्तर वाले कोने के साथ, विशिष्ट रूप से इसका आंशिक क्रम निर्धारित करता है |

हस्से आरेखों का नाम हेल्मुट हास (1898-1979) के नाम पर रखा गया है; गैरेट बिरखॉफ के अनुसार, उनसे बने हस के प्रभावी उपयोग के कारण उन्हें तथाकथित कहा जाता है। चूंकि, हस्से इन आरेखों का उपयोग करने वाले पहले व्यक्ति नहीं थे। हस्से से पहले का उदाहरण हेनरी गुस्ताव वोग्ट (1895) में पाया जा सकता है . चूंकि हासे आरेखों को मूल रूप से हाथ से आदेशित समुच्चयों के चित्र बनाने के लिए एक विधि के रूप में तैयार किया गया था, वे हाल ही में ग्राफ़ आरेखण विधियों का उपयोग करके स्वचालित रूप से बनाए गए हैं।

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

आरेख रचना

चूंकि हास आरेख आंशिक रूप से समुच्चय से निपटने के लिए सरल और साथ ही ज्ञान युक्त उपकरण हैं, किन्तु यह अच्छा चित्र बनाने के लिए कठिनाई हो जाता है। इसका कारण यह है कि किसी दिए गए पॉसेट के लिए हास आरेख बनाने के लिए सामान्यतः कई संभावित विधिया होती है। आदेश के न्यूनतम तत्व के साथ प्रारंभ करने और फिर अधिक से अधिक तत्वों को बढ़ाने की सरल विधि अधिकांशतः बहुत खराब परिणाम उत्पन्न करती है: समरूपता और आदेश की आंतरिक संरचना आसानी से खो जाती है।

निम्न उदाहरण समस्या प्रदर्शित करता है। समावेशन $\subseteq$ द्वारा आदेशित 4-तत्व समुच्चय के पासेट समुच्चय पर विचार करें . इस आंशिक क्रम के लिए नीचे चार अलग-अलग हास आरेख हैं। प्रत्येक समुच्चय में एक बाइनरी एन्कोडिंग के साथ स्तर किया गया एक नोड होता है जो दिखाता है कि एक निश्चित तत्व सबसमुच्चय (1) में है या नहीं (0) है |

File:Hypercubeorder binary.svg		File:Hypercubecubes binary.svg
File:Hypercubestar binary.svg

पहला आरेख स्पष्ट करता है कि पावर समुच्चय वर्गीकृत पॉसेट है। दूसरे आरेख में एक ही श्रेणीबद्ध संरचना है, किन्तु कुछ किनारों को दूसरों की तुलना में लंबा बनाकर, यह जोर देता है कि 4-आयामी घन दो 3-आयामी क्यूब्स का संयोजन संघ है, और एक चतुष्फलक (सार 3- पॉलीटॉप) इसी तरह दो त्रिकोणों को मिलाता है |(सार 2-पॉलीटोप्स) तीसरा आरेख संरचना की कुछ आंतरिक समरूपता दिखाता है। चौथे आरेख में शीर्षों को 4×4 मैट्रिक्स (गणित) के तत्वों की तरह व्यवस्थित किया गया है।

ऊपर की ओर समतलता

Main article: ऊपर की ओर समतल आरेख

File:Dih4 subgroups.svg

डीह₄ कोई क्रॉसिंग एज नहीं है।

यदि आंशिक क्रम को हस्से आरेख के रूप में बढाया जा सकता है जिसमें कोई भी दो किनारों को पार नहीं किया जाता है, तो इसके कवरिंग ग्राफ को ऊपर की तरफ प्लानर कहा जाता है। ऊपर की ओर की योजना और क्रॉसिंग-मुक्त हस्स आरेख निर्माण पर कई परिणाम ज्ञात हैं:

• यदि बढाया जाने वाला आंशिक क्रम एक आदेश आयाम है, तो इसे क्रॉसिंग के बिना बढाया जा सकता है यदि और केवल तभी जब इसमें अधिकतम दो आयाम हों। इस स्थिति में, क्रमबद्ध आयाम को साकार करने वाले दो रैखिक आदेशों में तत्वों के लिए कार्टेशियन निर्देशांक प्राप्त करके एक गैर-क्रॉसिंग आरेख पाया जा सकता है, और फिर आरेख को 45 डिग्री के कोण से वामावर्त घुमाया जा सकता है।
• यदि आंशिक क्रम में अधिकतम एक न्यूनतम तत्व है, या इसमें अधिकतम एक अधिकतम तत्व है, तो यह रैखिक समय में परीक्षण किया जा सकता है कि क्या इसमें एक गैर-क्रॉसिंग हासे आरेख है।
• यह निर्धारित करने के लिए एनपी-पूर्ण है कि क्या कई स्रोतों और सिंक के साथ आंशिक आदेश को क्रॉसिंग-मुक्त हस आरेख के रूप में तैयार किया जा सकता है। चूंकि, एक क्रॉसिंग-मुक्त हस्स आरेख का पता लगाना फिक्स्ड-पैरामीटर ट्रैक्टेबल है, जब आर्टिक्यूलेशन पॉइंट की संख्या और आंशिक क्रमबद्ध के ट्रांजिटिव कमी के ट्राइकनेक्टेड घटकों द्वारा पैरामीट्रिज किया जाता है।
• यदि आंशिक क्रम के तत्वों के y-निर्देशांक निर्दिष्ट किए गए हैं, तो उन समन्वय कार्यों के संबंध में क्रॉसिंग-मुक्त हासे आरेख रैखिक समय में पाया जा सकता है, यदि ऐसा आरेख उपस्थित है। विशेष रूप से, यदि इनपुट पॉसेट ग्रेडेड पॉसेट है, तो रैखिक समय में यह निर्धारित करना संभव है कि क्या क्रॉसिंग-मुक्त हस आरेख है जिसमें प्रत्येक शीर्ष की ऊंचाई उसके लिए आनुपातिक है।

यूएमएल संकेतन

File:Diamond inheritance.svg

एकाधिक वंशानुक्रम को दर्शाने वाला एक वर्ग आरेख

सॉफ्टवेयर इंजीनियरिंग में, सॉफ्टवेयर प्रणाली का वर्ग (कंप्यूटर प्रोग्रामिंग) और इन वर्गों के बीच वंशानुक्रम (ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग) संबंध को अधिकांशतः एक वर्ग आरेख का उपयोग करके चित्रित किया जाता है, हस्से आरेख का एक रूप जिसमें वर्गों को जोड़ने वाले किनारों को ठोस के रूप में बढाया जाता है। सुपरक्लास अंत में खुले त्रिभुज के साथ रेखा खंड है।

संदर्भ

• Baker, Kirby A.; Fishburn, Peter C.; Roberts, Fred S. (1971), "Partial orders of dimension 2", Networks, 2 (1): 11–28, doi:10.1002/net.3230020103
• Bang-Jensen, Jørgen (2008), "2.1 Acyclic Digraphs", Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (2nd ed.), Springer-Verlag, pp. 32–34, ISBN 978-1-84800-997-4
• Bertolazzi, R; Di Battista, G.; Mannino, C.; Tamassia, R. (1993), "Optimal upward planarity testing of single-source digraphs" (PDF), Proc. 1st European Symposium on Algorithms (ESA '93), Lecture Notes in Computer Science, vol. 726, Springer-Verlag, pp. 37–48, doi:10.1007/3-540-57273-2_42, ISBN 978-3-540-57273-2
• Birkhoff, Garrett (1948), Lattice Theory (Revised ed.), American Mathematical Society
• Chan, Hubert (2004), "A parameterized algorithm for upward planarity testing", Proc. 12th European Symposium on Algorithms (ESA '04), Lecture Notes in Computer Science, vol. 3221, Springer-Verlag, pp. 157–168, doi:10.1007/978-3-540-30140-0_16
• Christofides, Nicos (1975), Graph theory: an algorithmic approach, Academic Press, pp. 170–174
• Di Battista, G.; Tamassia, R. (1988), "Algorithms for plane representation of acyclic digraphs", Theoretical Computer Science, 61 (2–3): 175–178, doi:10.1016/0304-3975(88)90123-5
• Freese, Ralph (2004), "Automated lattice drawing", Concept Lattices (PDF), Lecture Notes in Computer Science, vol. 2961, Springer-Verlag, pp. 589–590
• Garg, Ashim; Tamassia, Roberto (1995a), "Upward planarity testing", Order, 12 (2): 109–133, doi:10.1007/BF01108622, S2CID 14183717
• Garg, Ashim; Tamassia, Roberto (1995b), "On the computational complexity of upward and rectilinear planarity testing", Graph Drawing (Proc. GD '94), LectureNotes in Computer Science, vol. 894, Springer-Verlag, pp. 286–297, doi:10.1007/3-540-58950-3_384, ISBN 978-3-540-58950-1
• Jünger, Michael; Leipert, Sebastian (1999), "Level planar embedding in linear time", Graph Drawing (Proc. GD '99), Lecture Notes in Computer Science, vol. 1731, pp. 72–81, doi:10.1007/3-540-46648-7_7, ISBN 978-3-540-66904-3
• Rival, Ivan (1985), "The diagram", in Rival, Ivan (ed.), Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications, Proceedings of the NATO Advanced Study Institute held in Banff, May 18–31, 1984, NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, vol. 147, Reidel, Dordrecht, pp. 103–133, MR 0818494
• Thulasiraman, K.; Swamy, M. N. S. (1992), "5.7 Acyclic Directed Graphs", Graphs: Theory and Algorithms, John Wiley and Son, p. 118, ISBN 978-0-471-51356-8
• Vogt, Henri Gustave (1895), Leçons sur la résolution algébrique des équations, Nony, p. 91

बाहरी संबंध

• File:Commons-logo.svg Related media at Wikimedia Commons:
  • Hasse diagram (Gallery)
  • Hasse diagrams (Category)
• Weisstein, Eric W., "Hasse Diagram", MathWorld