हस्से आरेख: Difference between revisions
m (Abhishek moved page हस्स आरेख to हस्से आरेख without leaving a redirect) |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Visual depiction of a partially ordered set}} | {{Short description|Visual depiction of a partially ordered set}} | ||
{{confuse| | {{confuse|हेस आरेख}} | ||
[[File:Inclusion ordering.svg|thumb|उपसमुच्चय द्वारा आदेशित 2-तत्व [[सबसेट]] का [[ सत्ता स्थापित ]]]]क्रम सिद्धांत में, एक हस्से आरेख ({{IPAc-en|ˈ|h|æ|s|ə}}; {{IPA-de|ˈhasə|lang}}) एक प्रकार का [[गणितीय आरेख]] है जिसका उपयोग परिमित आंशिक रूप से क्रमबद्ध सेट का प्रतिनिधित्व करने के लिए किया जाता है, इसकी [[सकर्मक कमी]] के [[ग्राफ ड्राइंग]] के रूप में। कंक्रीट से, आंशिक रूप से ऑर्डर किए गए सेट के लिए <math>(S,\le)</math> एक के प्रत्येक तत्व का प्रतिनिधित्व करता है <math>S</math> विमान में एक शीर्ष (ग्राफ सिद्धांत) के रूप में और एक [[रेखा खंड]] या वक्र खींचता है जो एक शीर्ष से ऊपर की ओर जाता है <math>x</math> दूसरे शीर्ष पर <math>y</math> जब कभी भी <math>y</math> [[आवरण संबंध]] <math>x</math> (यानी जब भी <math>x\ne y</math>, <math>x\le y</math> और नहीं है <math>z</math> से अलग <math>x</math> और <math>y</math> साथ <math>x\le z\le y</math>). ये वक्र एक दूसरे को काट सकते हैं लेकिन अपने अंतिम बिंदु के अलावा किसी भी कोने को नहीं छूना चाहिए। इस तरह का एक आरेख, लेबल वाले कोने के साथ, विशिष्ट रूप से इसका आंशिक क्रम निर्धारित करता है। | [[File:Inclusion ordering.svg|thumb|उपसमुच्चय द्वारा आदेशित 2-तत्व [[सबसेट]] का [[ सत्ता स्थापित ]]]]क्रम सिद्धांत में, एक हस्से आरेख ({{IPAc-en|ˈ|h|æ|s|ə}}; {{IPA-de|ˈhasə|lang}}) एक प्रकार का [[गणितीय आरेख]] है जिसका उपयोग परिमित आंशिक रूप से क्रमबद्ध सेट का प्रतिनिधित्व करने के लिए किया जाता है, इसकी [[सकर्मक कमी]] के [[ग्राफ ड्राइंग]] के रूप में। कंक्रीट से, आंशिक रूप से ऑर्डर किए गए सेट के लिए <math>(S,\le)</math> एक के प्रत्येक तत्व का प्रतिनिधित्व करता है <math>S</math> विमान में एक शीर्ष (ग्राफ सिद्धांत) के रूप में और एक [[रेखा खंड]] या वक्र खींचता है जो एक शीर्ष से ऊपर की ओर जाता है <math>x</math> दूसरे शीर्ष पर <math>y</math> जब कभी भी <math>y</math> [[आवरण संबंध]] <math>x</math> (यानी जब भी <math>x\ne y</math>, <math>x\le y</math> और नहीं है <math>z</math> से अलग <math>x</math> और <math>y</math> साथ <math>x\le z\le y</math>). ये वक्र एक दूसरे को काट सकते हैं लेकिन अपने अंतिम बिंदु के अलावा किसी भी कोने को नहीं छूना चाहिए। इस तरह का एक आरेख, लेबल वाले कोने के साथ, विशिष्ट रूप से इसका आंशिक क्रम निर्धारित करता है। | ||
हस्से आरेखों का नाम [[हेल्मुट हास]] (1898-1979) के नाम पर रखा गया है; [[गैरेट बिरखॉफ]] के अनुसार, उनसे बने हस के प्रभावी उपयोग के कारण उन्हें तथाकथित कहा जाता है।{{sfnp|Birkhoff|1948}} हालांकि, हस्से इन आरेखों का उपयोग करने वाले पहले व्यक्ति नहीं थे। एक उदाहरण जो हस्से से पहले का है, में पाया जा सकता है {{harvs|txt|last=Vogt|first=Henri Gustave|year=1895}}.{{sfnp|Rival|1985|p=110}} हालांकि हासे आरेखों को मूल रूप से हाथ से आंशिक रूप से आदेशित सेटों के चित्र बनाने के लिए एक तकनीक के रूप में तैयार किया गया था, वे हाल ही में ग्राफ़ आरेखण तकनीकों का उपयोग करके स्वचालित रूप से बनाए गए हैं।<ref>E.g., see {{harvtxt|Di Battista|Tamassia|1988}} and {{harvtxt|Freese|2004}}.</ref> | हस्से आरेखों का नाम [[हेल्मुट हास]] (1898-1979) के नाम पर रखा गया है; [[गैरेट बिरखॉफ]] के अनुसार, उनसे बने हस के प्रभावी उपयोग के कारण उन्हें तथाकथित कहा जाता है। {{sfnp|Birkhoff|1948}} हालांकि, हस्से इन आरेखों का उपयोग करने वाले पहले व्यक्ति नहीं थे। एक उदाहरण जो हस्से से पहले का है, में पाया जा सकता है {{harvs|txt|last=Vogt|first=Henri Gustave|year=1895}}.{{sfnp|Rival|1985|p=110}} हालांकि हासे आरेखों को मूल रूप से हाथ से आंशिक रूप से आदेशित सेटों के चित्र बनाने के लिए एक तकनीक के रूप में तैयार किया गया था, वे हाल ही में ग्राफ़ आरेखण तकनीकों का उपयोग करके स्वचालित रूप से बनाए गए हैं।<ref>E.g., see {{harvtxt|Di Battista|Tamassia|1988}} and {{harvtxt|Freese|2004}}.</ref> | ||
वाक्यांश हस्से आरेख भी उस ग्राफ़ के किसी भी चित्र से स्वतंत्र रूप से एक अमूर्त निर्देशित एसाइक्लिक ग्राफ़ के रूप में सकर्मक कमी को संदर्भित कर सकता है, लेकिन यह उपयोग यहाँ से बचा गया है।<ref>For examples of this alternative meaning of Hasse diagrams, see {{harvtxt|Christofides|1975|pp=170–174}}; {{harvtxt|Thulasiraman|Swamy|1992}}; {{harvtxt|Bang-Jensen|2008}}</ref> | |||
वाक्यांश हस्से आरेख भी उस ग्राफ़ के किसी भी चित्र से स्वतंत्र रूप से एक अमूर्त निर्देशित एसाइक्लिक ग्राफ़ के रूप में सकर्मक कमी को संदर्भित कर सकता है, लेकिन यह उपयोग यहाँ से बचा गया है।<ref name=":0">For examples of this alternative meaning of Hasse diagrams, see {{harvtxt|Christofides|1975|pp=170–174}}; {{harvtxt|Thulasiraman|Swamy|1992}}; {{harvtxt|Bang-Jensen|2008}}</ref> | |||
'''ये वक्र एक दूसरे को काट सकते हैं लेकिन अपने अंतिम बिंदु के अलावा किसी भी कोने को नहीं छूना चाहिए। इस तरह का एक आरेख, लेबल वाले कोने के साथ, विशिष्ट रूप से इसका आंशिक क्रम निर्धारित करता है।में सकर्मक कमी को संदर्भित कर सकता है, लेकिन यह उपयोग यहाँ से बचा गया है।<ref name=":0" />''' | |||
== आरेख डिजाइन == | == आरेख डिजाइन == | ||
हालांकि हास आरेख सरल और साथ ही आंशिक रूप से आदेशित सेट से निपटने के लिए सहज ज्ञान युक्त उपकरण हैं, लेकिन यह अच्छा चित्र बनाने के लिए मुश्किल हो जाता है। इसका कारण यह है कि किसी दिए गए पॉसेट के लिए हास आरेख बनाने के लिए आम तौर पर कई संभावित तरीके होंगे। एक आदेश के [[न्यूनतम तत्व]] | हालांकि हास आरेख सरल और साथ ही आंशिक रूप से आदेशित सेट से निपटने के लिए सहज ज्ञान युक्त उपकरण हैं, लेकिन यह अच्छा चित्र बनाने के लिए मुश्किल हो जाता है। इसका कारण यह है कि किसी दिए गए पॉसेट के लिए हास आरेख बनाने के लिए आम तौर पर कई संभावित तरीके होंगे। एक आदेश के [[न्यूनतम तत्व]] के साथ शुरू करने और फिर अधिक से अधिक तत्वों को बढ़ाने की सरल तकनीक अक्सर बहुत खराब परिणाम उत्पन्न करती है: समरूपता और आदेश की आंतरिक संरचना आसानी से खो जाती है। | ||
निम्न उदाहरण समस्या प्रदर्शित करता है। समावेशन द्वारा आदेशित 4-तत्व सेट के पावर सेट पर विचार करें <math>\subseteq</math>. इस आंशिक क्रम के लिए नीचे चार अलग-अलग हास आरेख हैं। प्रत्येक सबसेट में एक बाइनरी एन्कोडिंग के साथ लेबल किया गया एक नोड होता है जो दिखाता है कि एक निश्चित तत्व सबसेट (1) में है या नहीं (0): | निम्न उदाहरण समस्या प्रदर्शित करता है। समावेशन द्वारा आदेशित 4-तत्व सेट के पावर सेट पर विचार करें <math>\subseteq</math>. इस आंशिक क्रम के लिए नीचे चार अलग-अलग हास आरेख हैं। प्रत्येक सबसेट में एक बाइनरी एन्कोडिंग के साथ लेबल किया गया एक नोड होता है जो दिखाता है कि एक निश्चित तत्व सबसेट (1) में है या नहीं (0): | ||
Revision as of 09:26, 23 April 2023
क्रम सिद्धांत में, एक हस्से आरेख (/ˈhæsə/; German: [ˈhasə]) एक प्रकार का गणितीय आरेख है जिसका उपयोग परिमित आंशिक रूप से क्रमबद्ध सेट का प्रतिनिधित्व करने के लिए किया जाता है, इसकी सकर्मक कमी के ग्राफ ड्राइंग के रूप में। कंक्रीट से, आंशिक रूप से ऑर्डर किए गए सेट के लिए एक के प्रत्येक तत्व का प्रतिनिधित्व करता है विमान में एक शीर्ष (ग्राफ सिद्धांत) के रूप में और एक रेखा खंड या वक्र खींचता है जो एक शीर्ष से ऊपर की ओर जाता है दूसरे शीर्ष पर जब कभी भी आवरण संबंध (यानी जब भी , और नहीं है से अलग और साथ ). ये वक्र एक दूसरे को काट सकते हैं लेकिन अपने अंतिम बिंदु के अलावा किसी भी कोने को नहीं छूना चाहिए। इस तरह का एक आरेख, लेबल वाले कोने के साथ, विशिष्ट रूप से इसका आंशिक क्रम निर्धारित करता है।
हस्से आरेखों का नाम हेल्मुट हास (1898-1979) के नाम पर रखा गया है; गैरेट बिरखॉफ के अनुसार, उनसे बने हस के प्रभावी उपयोग के कारण उन्हें तथाकथित कहा जाता है। [1] हालांकि, हस्से इन आरेखों का उपयोग करने वाले पहले व्यक्ति नहीं थे। एक उदाहरण जो हस्से से पहले का है, में पाया जा सकता है Henri Gustave Vogt (1895).[2] हालांकि हासे आरेखों को मूल रूप से हाथ से आंशिक रूप से आदेशित सेटों के चित्र बनाने के लिए एक तकनीक के रूप में तैयार किया गया था, वे हाल ही में ग्राफ़ आरेखण तकनीकों का उपयोग करके स्वचालित रूप से बनाए गए हैं।[3]
वाक्यांश हस्से आरेख भी उस ग्राफ़ के किसी भी चित्र से स्वतंत्र रूप से एक अमूर्त निर्देशित एसाइक्लिक ग्राफ़ के रूप में सकर्मक कमी को संदर्भित कर सकता है, लेकिन यह उपयोग यहाँ से बचा गया है।[4]
ये वक्र एक दूसरे को काट सकते हैं लेकिन अपने अंतिम बिंदु के अलावा किसी भी कोने को नहीं छूना चाहिए। इस तरह का एक आरेख, लेबल वाले कोने के साथ, विशिष्ट रूप से इसका आंशिक क्रम निर्धारित करता है।में सकर्मक कमी को संदर्भित कर सकता है, लेकिन यह उपयोग यहाँ से बचा गया है।[4]
आरेख डिजाइन
हालांकि हास आरेख सरल और साथ ही आंशिक रूप से आदेशित सेट से निपटने के लिए सहज ज्ञान युक्त उपकरण हैं, लेकिन यह अच्छा चित्र बनाने के लिए मुश्किल हो जाता है। इसका कारण यह है कि किसी दिए गए पॉसेट के लिए हास आरेख बनाने के लिए आम तौर पर कई संभावित तरीके होंगे। एक आदेश के न्यूनतम तत्व के साथ शुरू करने और फिर अधिक से अधिक तत्वों को बढ़ाने की सरल तकनीक अक्सर बहुत खराब परिणाम उत्पन्न करती है: समरूपता और आदेश की आंतरिक संरचना आसानी से खो जाती है।
निम्न उदाहरण समस्या प्रदर्शित करता है। समावेशन द्वारा आदेशित 4-तत्व सेट के पावर सेट पर विचार करें . इस आंशिक क्रम के लिए नीचे चार अलग-अलग हास आरेख हैं। प्रत्येक सबसेट में एक बाइनरी एन्कोडिंग के साथ लेबल किया गया एक नोड होता है जो दिखाता है कि एक निश्चित तत्व सबसेट (1) में है या नहीं (0):
| File:Hypercubeorder binary.svg | File:Hypercubecubes binary.svg | |
| File:Hypercubestar binary.svg |
पहला आरेख स्पष्ट करता है कि पावर सेट एक वर्गीकृत पोसेट है। दूसरे आरेख में एक ही श्रेणीबद्ध संरचना है, लेकिन कुछ किनारों को दूसरों की तुलना में लंबा बनाकर, यह जोर देता है कि tesseract | 4-आयामी घन दो 3-आयामी क्यूब्स का संयोजन संघ है, और एक टेट्राहेड्रॉन (सार पॉलीटॉप | सार 3- पॉलीटॉप) इसी तरह दो त्रिकोणों को मिलाता है (सार पॉलीटोप | सार 2-पॉलीटोप्स)। तीसरा आरेख संरचना की कुछ आंतरिक समरूपता दिखाता है। चौथे आरेख में शीर्षों को 4×4 मैट्रिक्स (गणित) के तत्वों की तरह व्यवस्थित किया गया है।
ऊपर की ओर समतलता
यदि एक आंशिक क्रम को हस्से आरेख के रूप में खींचा जा सकता है जिसमें कोई भी दो किनारों को पार नहीं किया जाता है, तो इसके कवरिंग ग्राफ को ऊपर की तरफ प्लानर कहा जाता है। ऊपर की ओर की योजना और क्रॉसिंग-फ्री हस्स आरेख निर्माण पर कई परिणाम ज्ञात हैं:
- यदि खींचा जाने वाला आंशिक क्रम एक जाली (आदेश) है, तो इसे क्रॉसिंग के बिना खींचा जा सकता है यदि और केवल तभी जब इसमें अधिकतम दो आयाम हों।[5] इस मामले में, ऑर्डर आयाम को साकार करने वाले दो रैखिक आदेशों में तत्वों के लिए कार्टेशियन निर्देशांक प्राप्त करके एक गैर-क्रॉसिंग ड्राइंग पाया जा सकता है, और फिर ड्राइंग को 45 डिग्री के कोण से वामावर्त घुमाया जा सकता है।
- यदि आंशिक क्रम में अधिकतम एक न्यूनतम तत्व है, या इसमें अधिकतम एक अधिकतम तत्व है, तो यह रैखिक समय में परीक्षण किया जा सकता है कि क्या इसमें एक गैर-क्रॉसिंग हासे आरेख है।[6]
- यह निर्धारित करने के लिए एनपी-पूर्ण है कि क्या कई स्रोतों और सिंक के साथ एक आंशिक आदेश को क्रॉसिंग-फ्री हस आरेख के रूप में तैयार किया जा सकता है।[7] हालांकि, एक क्रॉसिंग-फ्री हस्स आरेख का पता लगाना फिक्स्ड-पैरामीटर ट्रैक्टेबल है, जब आर्टिक्यूलेशन पॉइंट्स की संख्या और आंशिक ऑर्डर के ट्रांजिटिव रिडक्शन के ट्राइकनेक्टेड घटकों द्वारा पैरामीट्रिज किया जाता है।[8]
- यदि आंशिक क्रम के तत्वों के y-निर्देशांक निर्दिष्ट किए गए हैं, तो उन समन्वय कार्यों के संबंध में एक क्रॉसिंग-मुक्त हासे आरेख रैखिक समय में पाया जा सकता है, यदि ऐसा आरेख मौजूद है।[9] विशेष रूप से, यदि इनपुट पोसेट एक ग्रेडेड पॉसेट है, तो रैखिक समय में यह निर्धारित करना संभव है कि क्या क्रॉसिंग-फ्री हस आरेख है जिसमें प्रत्येक शीर्ष की ऊंचाई उसके रैंक के लिए आनुपातिक है।
यूएमएल संकेतन
सॉफ्टवेयर इंजीनियरिंग में, एक सॉफ्टवेयर सिस्टम का वर्ग (कंप्यूटर प्रोग्रामिंग) और इन वर्गों के बीच वंशानुक्रम (ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग) संबंध को अक्सर एक वर्ग आरेख का उपयोग करके चित्रित किया जाता है, हस्से आरेख का एक रूप जिसमें वर्गों को जोड़ने वाले किनारों को ठोस के रूप में खींचा जाता है। सुपरक्लास अंत में एक खुले त्रिभुज के साथ रेखा खंड।
टिप्पणियाँ
- ↑ Birkhoff (1948).
- ↑ Rival (1985), p. 110.
- ↑ E.g., see Di Battista & Tamassia (1988) and Freese (2004).
- ↑ 4.0 4.1 For examples of this alternative meaning of Hasse diagrams, see Christofides (1975, pp. 170–174); Thulasiraman & Swamy (1992); Bang-Jensen (2008)
- ↑ Garg & Tamassia (1995a), Theorem 9, p. 118; Baker, Fishburn & Roberts (1971), theorem 4.1, page 18.
- ↑ Garg & Tamassia (1995a), Theorem 15, p. 125; Bertolazzi et al. (1993).
- ↑ Garg & Tamassia (1995a), Corollary 1, p. 132; Garg & Tamassia (1995b).
- ↑ Chan (2004).
- ↑ Jünger & Leipert (1999).
संदर्भ
- 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
