आश्रितता ग्राफ: Difference between revisions
From Vigyanwiki
(→उदाहरण) |
No edit summary |
||
| (6 intermediate revisions by 4 users not shown) | |||
| Line 4: | Line 4: | ||
== परिभाषा == | == परिभाषा == | ||
[[File:Dependencygraph.png|right]]वस्तुओं के एक समुच्चय को देखते हुए ''S'' और एक [[सकर्मक संबंध]] <math>R \subseteq S \times S</math> <math>(a,b) \in R</math> के साथ एक आश्रितता मॉडलिंग "''a'', ''b'' पर आश्रित है" (''a'' | [[File:Dependencygraph.png|right]]वस्तुओं के एक समुच्चय को देखते हुए ''S'' और एक [[सकर्मक संबंध]] <math>R \subseteq S \times S</math> <math>(a,b) \in R</math> के साथ एक आश्रितता मॉडलिंग "''a'', ''b'' पर आश्रित है" (''a'' ''से पहले'' ''b'' ''का मूल्यांकन करने की आवश्यकता है''), आश्रितता ग्राफ एक ग्राफ <math>G = (S, T)</math> है जिसमें <math>T \subseteq R</math> ''R'' का [[सकर्मक समानयन]] है| | ||
उदाहरण के लिए, एक साधारण परिकलित्र को कल्पना करते हैं। यह परिकलित्र चरों के लिए नियत मानों को निर्दिष्ट करने और तीसरे चर को ठीक दो चरों का योग निर्दिष्ट करने का समर्थन करता है। ''"A = B+C; B = 5+D; C=4; D=2;"'' जैसे कई समीकरण दिए गए हैं, तो <math>S=\{A,B,C,D\}</math> और <math>R=\{(A,B),(A,C),(B,D)\}</math> | आप इस संबंध को स्पष्ट रुप से प्राप्त कर सकते हैं: ''A'', ''B'' और ''C'' पर आश्रित है, क्योंकि आप दो चरों जोड़ सकते हैं [[यदि और केवल तभी]] जब आप दोनों चरों के मान जानते हों। इस प्रकार, ''A'' को परिकलित करने से पहले ''B'' को परिकलित करना होता है। हालाँकि, ''C'' और ''D'' के मान शीघ्र ज्ञात हो जाते हैं, क्योंकि वे संख्या शाब्दिक हैं। | उदाहरण के लिए, एक साधारण परिकलित्र को कल्पना करते हैं। यह परिकलित्र चरों के लिए नियत मानों को निर्दिष्ट करने और तीसरे चर को ठीक दो चरों का योग निर्दिष्ट करने का समर्थन करता है। ''"A = B+C; B = 5+D; C=4; D=2;"'' जैसे कई समीकरण दिए गए हैं, तो <math>S=\{A,B,C,D\}</math> और <math>R=\{(A,B),(A,C),(B,D)\}</math> | आप इस संबंध को स्पष्ट रुप से प्राप्त कर सकते हैं: ''A'', ''B'' और ''C'' पर आश्रित है, क्योंकि आप दो चरों को जोड़ सकते हैं [[यदि और केवल तभी]] जब आप दोनों चरों के मान जानते हों। इस प्रकार, ''A'' को परिकलित करने से पहले ''B'' को परिकलित करना होता है। हालाँकि, ''C'' और ''D'' के मान शीघ्र ज्ञात हो जाते हैं, क्योंकि वे संख्या शाब्दिक हैं। | ||
== असंभव मूल्यांकन को पहचानना == | == असंभव मूल्यांकन को पहचानना == | ||
आश्रितता ग्राफ में, आश्रितता का चक्र (जिसे '''वत्तीय आश्रितता''' भी कहा जाता है) ऐसी स्थिति की ओर ले जाता है जिसमें कोई वैध मूल्यांकन अनुक्रम उपस्थित नहीं होता है, क्योंकि चक्र में किसी भी वस्तु का मूल्यांकन पहले नहीं किया जा सकता है। यदि आश्रितता ग्राफ में कोई वत्तीय आश्रितता नहीं है, तो यह एक [[दिष्ट चक्रीय ग्राफ]] बनाता है, और [[ टोपोलॉजिकल छँटाई | सांस्थितिक | आश्रितता ग्राफ में, आश्रितता का चक्र (जिसे '''वत्तीय आश्रितता''' भी कहा जाता है) ऐसी स्थिति की ओर ले जाता है जिसमें कोई वैध मूल्यांकन अनुक्रम उपस्थित नहीं होता है, क्योंकि चक्र में किसी भी वस्तु का मूल्यांकन पहले नहीं किया जा सकता है। यदि आश्रितता ग्राफ में कोई वत्तीय आश्रितता नहीं है, तो यह एक [[दिष्ट चक्रीय ग्राफ]] बनाता है, और [[ टोपोलॉजिकल छँटाई |सांस्थितिक शाटन]] द्वारा एक मूल्यांकन अनुक्रम प्राप्त किया जा सकता है। अधिकांश सांस्थितिक शाटन एल्गोरिदम भी अपने इनपुट में चक्रों का पता लगाने में सक्षम हैं; हालाँकि, पता लगाए गए चक्रों के लिए उचित प्रबंधन प्रदान करने के लिए सांस्थितिक शाटन से अलग [[चक्र]] का पता लगाना वांछनीय हो सकता है। | ||
पहले से साधारण परिकलित्र को कल्पना करते हैं। समीकरण पद्धति ''"A=B; B=D+C; C=D+A; D=12'';" इसमें ''A, B'' और ''C'' द्वारा गठित एक [[वत्तीय आश्रितता]] सम्मिलित है, क्योंकि ''B'' का मूल्यांकन ''A'' से पहले किया जाना चाहिए, ''C'' का मूल्यांकन ''B'' से पहले किया जाना चाहिए'','' और ''A'' का मूल्यांकन ''C'' से पहले किया जाना चाहिए'' |'' | पहले से साधारण परिकलित्र को कल्पना करते हैं। समीकरण पद्धति ''"A=B; B=D+C; C=D+A; D=12'';" इसमें ''A, B'' और ''C'' द्वारा गठित एक [[वत्तीय आश्रितता]] सम्मिलित है, क्योंकि ''B'' का मूल्यांकन ''A'' से पहले किया जाना चाहिए, ''C'' का मूल्यांकन ''B'' से पहले किया जाना चाहिए'','' और ''A'' का मूल्यांकन ''C'' से पहले किया जाना चाहिए'' |'' | ||
== मूल्यांकन अनुक्रम व्युत्पत्ति == | == मूल्यांकन अनुक्रम व्युत्पत्ति == | ||
एक '''सही मूल्यांकन अनुक्रम''' उन वस्तुओं का संख्यांकन <math> n : S \rightarrow \mathbb{N}</math> है जो आश्रितता ग्राफ़ के नोड्स बनाते हैं ताकि निम्नलिखित समीकरण होल्ड रहे: <math> n(a) < n(b) \Rightarrow (a, b) \notin R </math> <math> a, b \in S</math> के साथ है। | एक '''सही मूल्यांकन अनुक्रम''' उन वस्तुओं का संख्यांकन <math> n : S \rightarrow \mathbb{N}</math> है जो आश्रितता ग्राफ़ के नोड्स बनाते हैं ताकि निम्नलिखित समीकरण होल्ड रहे: <math> n(a) < n(b) \Rightarrow (a, b) \notin R </math> <math> a, b \in S</math> के साथ है। इसका अर्थ है, यदि संख्यांकन दो अवयवों <math>a</math> और <math>b</math> को क्रमबद्ध करता है ताकि <math>a</math> का मूल्यांकन <math>b</math> से पहले किया जाएगा, तो <math>a</math> को <math>b</math> पर आश्रित नहीं होना चाहिए। | ||
एक से अधिक सही मूल्यांकन अनुक्रम हो सकते हैं। वास्तव में, एक सही संख्यांकन एक [[सांस्थितिक अनुक्रम]] है, और कोई भी सांस्थितिक अनुक्रम एक सही संख्यांकन है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही सांस्थितिक अनुक्रम व्युत्पन्न करता है, एक सही मूल्यांकन अनुक्रम व्युत्पन्न करता है। | एक से अधिक सही मूल्यांकन अनुक्रम हो सकते हैं। वास्तव में, एक सही संख्यांकन एक [[सांस्थितिक अनुक्रम]] है, और कोई भी सांस्थितिक अनुक्रम एक सही संख्यांकन है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही सांस्थितिक अनुक्रम व्युत्पन्न करता है, और एक सही मूल्यांकन अनुक्रम व्युत्पन्न करता है। | ||
ऊपर दिए गए साधारण परिकलित्र की एक बार फिर से कल्पना करते हैं। समीकरण पद्धति ''"A = B+C; B = 5+D; C=4; D=2;"'' को देखते हुए, एक सही मूल्यांकन अनुक्रम (''D, C, B, A'') होता है। हालाँकि, (''C, D, B, A'') भी एक सही मूल्यांकन अनुक्रम है। | ऊपर दिए गए साधारण परिकलित्र की एक बार फिर से कल्पना करते हैं। समीकरण पद्धति ''"A = B+C; B = 5+D; C=4; D=2;"'' को देखते हुए, एक सही मूल्यांकन अनुक्रम (''D, C, B, A'') होता है। हालाँकि, (''C, D, B, A'') भी एक सही मूल्यांकन अनुक्रम है। | ||
| Line 28: | Line 28: | ||
फिर एक सही मूल्यांकन अनुक्रम द्वारा क्रमित शीर्ष लेबल वाली श्रृंखला एक अनुरेख की एक श्रृंखला के संगत है। | फिर एक सही मूल्यांकन अनुक्रम द्वारा क्रमित शीर्ष लेबल वाली श्रृंखला एक अनुरेख की एक श्रृंखला के संगत है। | ||
[[मोनोइड|मोनोइडल]] प्रचालन <math>(S_{12},R_{12})=(S_1,R_1)\bullet (S_2,R_2)</math> दो | [[मोनोइड|मोनोइडल]] प्रचालन <math>(S_{12},R_{12})=(S_1,R_1)\bullet (S_2,R_2)</math> दो ग्राफों के शीर्ष समुच्चयों के [[असंयुक्त संयोग]] <math>S_{12}=S_1 \sqcup S_2</math> को लेता है, प्रत्येक ग्राफ़ में उपस्थित किनारों को संरक्षित करता है, और पहले से दूसरे तक नए किनारों को खींचता (ड्रॉ) है जहां आश्रितता संबंध अनुमति देता है,<ref name=IntroToTraceTheory/>{{rp|14}} | ||
:<math>R_{12} = R_1 \sqcup R_2 \sqcup \{(a,b)\mid a\in S_1 \land b\in S_2 \land (\phi(a),\phi(b))\in D\}</math> | :<math>R_{12} = R_1 \sqcup R_2 \sqcup \{(a,b)\mid a\in S_1 \land b\in S_2 \land (\phi(a),\phi(b))\in D\}</math> | ||
तत्समक (सर्वसमिका) रिक्त ग्राफ है| | तत्समक (सर्वसमिका) रिक्त ग्राफ है| | ||
| Line 34: | Line 34: | ||
==उदाहरण== | ==उदाहरण== | ||
आश्रितता ग्राफ़ का उपयोग इसमें किया जाता है: | आश्रितता ग्राफ़ का उपयोग इसमें किया जाता है: | ||
* स्वचालित सॉफ़्टवेयर [[ इंस्टालर | | * स्वचालित सॉफ़्टवेयर [[ इंस्टालर |अधिष्ठापक]]: वे ऐसे [[सॉफ़्टवेयर पैकगों]] की खोज में ग्राफ़ पर चलते हैं जिनकी आवश्यकता है लेकिन अभी तक अधिष्ठापित नहीं हुए हैं। आश्रितता पैकगों के [[युग्मन]] द्वारा दी जाती है। | ||
* सॉफ्टवेयर निर्माण स्क्रिप्ट जैसे [[यूनिक्स]] [[ बनाओ (सॉफ्टवेयर) |मेक]], [[नोड]] एनपीएम इंस्टाल, पीएचपी कंपोजर, [[ट्विटर]] बोवर इंस्टाल या [[अपाचे एंट]] सम्मिलित हैं। उन्हें यह जानने की आवश्यकता है कि कौन सी फाइलें बदल गई हैं, इसलिए केवल सही फाइलों को पुन:अनुभाषित करने की आवश्यकता है। | * सॉफ्टवेयर निर्माण स्क्रिप्ट जैसे [[यूनिक्स]] [[ बनाओ (सॉफ्टवेयर) |मेक]], [[नोड]] एनपीएम इंस्टाल, पीएचपी कंपोजर, [[ट्विटर]] बोवर इंस्टाल या [[अपाचे एंट]] सम्मिलित हैं। उन्हें यह जानने की आवश्यकता है कि कौन सी फाइलें बदल गई हैं, इसलिए केवल सही फाइलों को पुन:अनुभाषित करने की आवश्यकता है। | ||
* [[संकलक|अनुभाषक]] तकनीक और [[औपचारिक भाषा]] कार्यान्वयन में: | * [[संकलक|अनुभाषक]] तकनीक और [[औपचारिक भाषा]] कार्यान्वयन में: | ||
| Line 44: | Line 44: | ||
* वीडियो गेम, विशेष रूप से [[पहेली वीडियो गेम|पजल]] और [[ साहसिक खेल |एडवेंचर वीडियो गेम]], जिन्हें अधिकतर इन-गेम क्रियाओं के मध्य आश्रित संबंधों के ग्राफ के रूप में अभिकल्पित किया जाता है।<ref>{{cite web |last1=Gilbert |first1=Ron |title=पहेली निर्भरता चार्ट|url=https://grumpygamer.com/puzzle_dependency_charts |website=Grumpy Gamer |access-date=11 January 2020 |language=en}}</ref> | * वीडियो गेम, विशेष रूप से [[पहेली वीडियो गेम|पजल]] और [[ साहसिक खेल |एडवेंचर वीडियो गेम]], जिन्हें अधिकतर इन-गेम क्रियाओं के मध्य आश्रित संबंधों के ग्राफ के रूप में अभिकल्पित किया जाता है।<ref>{{cite web |last1=Gilbert |first1=Ron |title=पहेली निर्भरता चार्ट|url=https://grumpygamer.com/puzzle_dependency_charts |website=Grumpy Gamer |access-date=11 January 2020 |language=en}}</ref> | ||
आश्रितता ग्राफ़ इसका एक अभिमुखता (आस्पेक्ट) है: | आश्रितता ग्राफ़ इसका एक अभिमुखता (आस्पेक्ट) है: | ||
* विनिर्माण | * [[विनिर्माण यंत्र के प्रकार:]] अनिर्मित सामग्रियों को कई आश्रित चरणों के माध्यम से गुणनफलों में प्रक्रमित किया जाता है। | ||
* [[जॉब शॉप शेड्यूलिंग|जॉब शॉप | * [[जॉब शॉप शेड्यूलिंग|जॉब शॉप नियोजन]]: कंप्यूटर विज्ञान में संबंधित सैद्धांतिक समस्याओं का संग्रह है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
| Line 55: | Line 55: | ||
{{Reflist}} | {{Reflist}} | ||
*Balmas, Francoise (2001) ''[http://www.ai.univ-paris8.fr/~fb/version-ps/pdep.ps Displaying dependence graphs: a hierarchical approach],'' [http://doi.ieeecomputersociety.org/10.1109/WCRE.2001.957830] wcre, p. 261, Eighth Working Conference on Reverse Engineering (WCRE'01) | *Balmas, Francoise (2001) ''[http://www.ai.univ-paris8.fr/~fb/version-ps/pdep.ps Displaying dependence graphs: a hierarchical approach],'' [http://doi.ieeecomputersociety.org/10.1109/WCRE.2001.957830] wcre, p. 261, Eighth Working Conference on Reverse Engineering (WCRE'01) | ||
[[Category:All articles lacking in-text citations]] | |||
[[Category:Articles lacking in-text citations from June 2013]] | |||
[[Category: | [[Category:CS1 English-language sources (en)]] | ||
[[Category:Created On 11/07/2023]] | [[Category:Created On 11/07/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:अनुप्रयोग-विशिष्ट ग्राफ़]] | |||
[[Category:निर्देशित रेखांकन]] | |||
Latest revision as of 10:32, 18 July 2023
 | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (June 2013) (Learn how and when to remove this template message) |
गणित, कंप्यूटर विज्ञान और डिजिटल इलेक्ट्रॉनिक्स में, आश्रितता ग्राफ़ एक दिष्ट ग्राफ है जो एक दूसरे के प्रति कई वस्तुओं की आश्रितता को निरूपित करता है। मूल्यांकन अनुक्रम व्युत्पन्न करना या मूल्यांकन अनुक्रम की अनुपस्थिति संभव है जो आश्रितता ग्राफ से दी गई आश्रितता का रेस्पेक्ट करती है।
परिभाषा
वस्तुओं के एक समुच्चय को देखते हुए S और एक सकर्मक संबंध के साथ एक आश्रितता मॉडलिंग "a, b पर आश्रित है" (a से पहले b का मूल्यांकन करने की आवश्यकता है), आश्रितता ग्राफ एक ग्राफ है जिसमें R का सकर्मक समानयन है|
उदाहरण के लिए, एक साधारण परिकलित्र को कल्पना करते हैं। यह परिकलित्र चरों के लिए नियत मानों को निर्दिष्ट करने और तीसरे चर को ठीक दो चरों का योग निर्दिष्ट करने का समर्थन करता है। "A = B+C; B = 5+D; C=4; D=2;" जैसे कई समीकरण दिए गए हैं, तो और | आप इस संबंध को स्पष्ट रुप से प्राप्त कर सकते हैं: A, B और C पर आश्रित है, क्योंकि आप दो चरों को जोड़ सकते हैं यदि और केवल तभी जब आप दोनों चरों के मान जानते हों। इस प्रकार, A को परिकलित करने से पहले B को परिकलित करना होता है। हालाँकि, C और D के मान शीघ्र ज्ञात हो जाते हैं, क्योंकि वे संख्या शाब्दिक हैं।
असंभव मूल्यांकन को पहचानना
आश्रितता ग्राफ में, आश्रितता का चक्र (जिसे वत्तीय आश्रितता भी कहा जाता है) ऐसी स्थिति की ओर ले जाता है जिसमें कोई वैध मूल्यांकन अनुक्रम उपस्थित नहीं होता है, क्योंकि चक्र में किसी भी वस्तु का मूल्यांकन पहले नहीं किया जा सकता है। यदि आश्रितता ग्राफ में कोई वत्तीय आश्रितता नहीं है, तो यह एक दिष्ट चक्रीय ग्राफ बनाता है, और सांस्थितिक शाटन द्वारा एक मूल्यांकन अनुक्रम प्राप्त किया जा सकता है। अधिकांश सांस्थितिक शाटन एल्गोरिदम भी अपने इनपुट में चक्रों का पता लगाने में सक्षम हैं; हालाँकि, पता लगाए गए चक्रों के लिए उचित प्रबंधन प्रदान करने के लिए सांस्थितिक शाटन से अलग चक्र का पता लगाना वांछनीय हो सकता है।
पहले से साधारण परिकलित्र को कल्पना करते हैं। समीकरण पद्धति "A=B; B=D+C; C=D+A; D=12;" इसमें A, B और C द्वारा गठित एक वत्तीय आश्रितता सम्मिलित है, क्योंकि B का मूल्यांकन A से पहले किया जाना चाहिए, C का मूल्यांकन B से पहले किया जाना चाहिए, और A का मूल्यांकन C से पहले किया जाना चाहिए |
मूल्यांकन अनुक्रम व्युत्पत्ति
एक सही मूल्यांकन अनुक्रम उन वस्तुओं का संख्यांकन है जो आश्रितता ग्राफ़ के नोड्स बनाते हैं ताकि निम्नलिखित समीकरण होल्ड रहे: के साथ है। इसका अर्थ है, यदि संख्यांकन दो अवयवों और को क्रमबद्ध करता है ताकि का मूल्यांकन से पहले किया जाएगा, तो को पर आश्रित नहीं होना चाहिए।
एक से अधिक सही मूल्यांकन अनुक्रम हो सकते हैं। वास्तव में, एक सही संख्यांकन एक सांस्थितिक अनुक्रम है, और कोई भी सांस्थितिक अनुक्रम एक सही संख्यांकन है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही सांस्थितिक अनुक्रम व्युत्पन्न करता है, और एक सही मूल्यांकन अनुक्रम व्युत्पन्न करता है।
ऊपर दिए गए साधारण परिकलित्र की एक बार फिर से कल्पना करते हैं। समीकरण पद्धति "A = B+C; B = 5+D; C=4; D=2;" को देखते हुए, एक सही मूल्यांकन अनुक्रम (D, C, B, A) होता है। हालाँकि, (C, D, B, A) भी एक सही मूल्यांकन अनुक्रम है।
एकाभ संरचना
एक अचक्रीय आश्रितता ग्राफ एक अनुरेख एकाभ के अनुरेख से इस प्रकार संगत है:[1]: 12
- एक फलन प्रत्येक शीर्ष को वर्णाक्षर के एक प्रतीक के साथ लेबल करता है
- कोई किनारा या है यदि और केवल यदि