आश्रितता ग्राफ: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Directed graph representing dependencies}} {{more footnotes|date=June 2013}} गणित, कंप्यूटर विज्ञान और ड...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Directed graph representing dependencies}} | {{Short description|Directed graph representing dependencies}} | ||
{{more footnotes|date=June 2013}} | {{more footnotes|date=June 2013}} | ||
गणित, [[कंप्यूटर विज्ञान]] और [[डिजिटल इलेक्ट्रॉनिक्स]] में, | [[गणित]], [[कंप्यूटर विज्ञान]] और [[डिजिटल इलेक्ट्रॉनिक्स]] में, '''आश्रितता ग्राफ़''' एक [[निर्देशित ग्राफ|दिष्ट ग्राफ]] है जो एक दूसरे के प्रति कई वस्तुओं की आश्रितता को निरूपित करता है। मूल्यांकन अनुक्रम व्युत्पन्न करना या मूल्यांकन अनुक्रम की अनुपस्थिति संभव है जो आश्रितता ग्राफ से दी गई आश्रितता का रेस्पेक्ट करती है। | ||
== परिभाषा == | == परिभाषा == | ||
[[File:Dependencygraph.png|right]]वस्तुओं का एक सेट दिया गया <math>S</math> और एक [[सकर्मक संबंध]] <math>R \subseteq S \times S</math> साथ <math>(a,b) \in R</math> | [[File:Dependencygraph.png|right]]वस्तुओं का एक सेट दिया गया <math>S</math> और एक [[सकर्मक संबंध]] <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> आर की [[सकर्मक कमी]] | ||
उदाहरण के लिए, एक साधारण कैलकुलेटर मान लें। यह कैलकुलेटर वेरिएबल्स के लिए स्थिर मानों को निर्दिष्ट करने और तीसरे वेरिएबल को ठीक दो वेरिएबल्स का योग निर्दिष्ट करने का समर्थन करता है। A = B+C जैसे कई समीकरण दिए गए हैं; बी = 5+डी; सी=4; डी=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 जैसे कई समीकरण दिए गए हैं; बी = 5+डी; सी=4; डी=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''; ''बी''=''डी''+''सी''; ''सी''=''डी''+''ए''; ''डी''=12; ''ए'', ''बी'' और ''सी'' द्वारा बनाई गई एक गोलाकार | पहले से सरल कैलकुलेटर मान लें। समीकरण प्रणाली ''A''=''B''; ''बी''=''डी''+''सी''; ''सी''=''डी''+''ए''; ''डी''=12; ''ए'', ''बी'' और ''सी'' द्वारा बनाई गई एक गोलाकार आश्रितता शामिल है, क्योंकि ''बी'' का मूल्यांकन ''ए'' से पहले किया जाना चाहिए, ''सी'' का मूल्यांकन '' से पहले किया जाना चाहिए 'बी', और 'ए' का मूल्यांकन 'सी' से पहले किया जाना चाहिए। | ||
== मूल्यांकन आदेश निकालना == | == मूल्यांकन आदेश निकालना == | ||
एक सही मूल्यांकन क्रम एक क्रमांकन है <math> n : S \rightarrow \mathbb{N}</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>. | ||
एक से अधिक सही मूल्यांकन क्रम हो सकते हैं। वास्तव में, एक सही नंबरिंग एक टोपोलॉजिकल सॉर्टिंग है, और कोई भी टोपोलॉजिकल ऑर्डर एक सही नंबरिंग है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही टोपोलॉजिकल ऑर्डर प्राप्त करता है, एक सही मूल्यांकन क्रम प्राप्त करता है। | एक से अधिक सही मूल्यांकन क्रम हो सकते हैं। वास्तव में, एक सही नंबरिंग एक टोपोलॉजिकल सॉर्टिंग है, और कोई भी टोपोलॉजिकल ऑर्डर एक सही नंबरिंग है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही टोपोलॉजिकल ऑर्डर प्राप्त करता है, एक सही मूल्यांकन क्रम प्राप्त करता है। | ||
| Line 22: | Line 22: | ||
== मोनोइड संरचना == | == मोनोइड संरचना == | ||
एक एसाइक्लिक | एक एसाइक्लिक आश्रितता ग्राफ एक [[ट्रेस मोनॉइड]] के ट्रेस से इस प्रकार मेल खाता है:<ref name=IntroToTraceTheory>{{cite book |last1=Mazurkiewicz |first1=Antoni |editor1-last=Rozenberg |editor1-first=G. |editor2-last=Diekert |editor2-first=V. |title=निशानों की किताब|date=1995 |publisher=World Scientific |location=Singapore |isbn=981-02-2058-8 |chapter-url=http://www.cas.mcmaster.ca/~cas724/2007/paper2.pdf |access-date=18 April 2021 |chapter=Introduction to Trace Theory}}</ref>{{rp|12}} | ||
* एक समारोह <math>\phi : S \to \Sigma</math> प्रत्येक शीर्ष को वर्णमाला के एक प्रतीक के साथ लेबल करें <math>\Sigma</math> | * एक समारोह <math>\phi : S \to \Sigma</math> प्रत्येक शीर्ष को वर्णमाला के एक प्रतीक के साथ लेबल करें <math>\Sigma</math> | ||
*एक किनारा है <math>a \to b</math> या <math>b \to a</math> अगर और केवल अगर <math>(\phi(a),\phi(b))</math> [[निर्भरता संबंध]] में है <math>D</math>. | *एक किनारा है <math>a \to b</math> या <math>b \to a</math> अगर और केवल अगर <math>(\phi(a),\phi(b))</math> [[निर्भरता संबंध|आश्रितता संबंध]] में है <math>D</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> दो ग्राफ़ के शीर्ष सेटों में से, प्रत्येक ग्राफ़ में मौजूदा किनारों को संरक्षित करता है, और पहले से दूसरे तक नए किनारों को खींचता है जहां | [[मोनोइड]]ल ऑपरेशन <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> | ||
पहचान खाली ग्राफ है. | पहचान खाली ग्राफ है. | ||
==उदाहरण== | ==उदाहरण== | ||
आश्रितता ग्राफ़ का उपयोग इसमें किया जाता है: | |||
* स्वचालित सॉफ़्टवेयर [[ इंस्टालर ]]: वे सॉफ़्टवेयर पैकेज (इंस्टॉलेशन) की तलाश में ग्राफ़ पर चलते हैं जो आवश्यक हैं लेकिन अभी तक इंस्टॉल नहीं हुए हैं। | * स्वचालित सॉफ़्टवेयर [[ इंस्टालर ]]: वे सॉफ़्टवेयर पैकेज (इंस्टॉलेशन) की तलाश में ग्राफ़ पर चलते हैं जो आवश्यक हैं लेकिन अभी तक इंस्टॉल नहीं हुए हैं। आश्रितता पैकेजों के [[युग्मन (कंप्यूटर विज्ञान)]] द्वारा दी जाती है। | ||
* सॉफ्टवेयर बिल्ड स्क्रिप्ट जैसे [[यूनिक्स]] [[ बनाओ (सॉफ्टवेयर) ]], नोड.जेएस एनपीएम इंस्टाल, पीएचपी कंपोजर, [[ट्विटर]] बोवर इंस्टाल या अपाचे एंट। उन्हें यह जानने की जरूरत है कि कौन सी फाइलें बदल गई हैं, इसलिए केवल सही फाइलों को फिर से संकलित करने की जरूरत है। | * सॉफ्टवेयर बिल्ड स्क्रिप्ट जैसे [[यूनिक्स]] [[ बनाओ (सॉफ्टवेयर) ]], नोड.जेएस एनपीएम इंस्टाल, पीएचपी कंपोजर, [[ट्विटर]] बोवर इंस्टाल या अपाचे एंट। उन्हें यह जानने की जरूरत है कि कौन सी फाइलें बदल गई हैं, इसलिए केवल सही फाइलों को फिर से संकलित करने की जरूरत है। | ||
* [[संकलक]] प्रौद्योगिकी और [[औपचारिक भाषा]] कार्यान्वयन में: | * [[संकलक]] प्रौद्योगिकी और [[औपचारिक भाषा]] कार्यान्वयन में: | ||
**निर्देश शेड्यूलिंग: | **निर्देश शेड्यूलिंग: आश्रितता ग्राफ़ की गणना [[असेंबली कोड]] या मध्यवर्ती निर्देशों के ऑपरेंड के लिए की जाती है और निर्देशों के लिए इष्टतम क्रम निर्धारित करने के लिए उपयोग किया जाता है। | ||
** डेड कोड उन्मूलन: यदि कोई दुष्प्रभावित ऑपरेशन किसी वेरिएबल पर निर्भर नहीं करता है, तो इस वेरिएबल को डेड माना जाता है और इसे हटाया जा सकता है। | ** डेड कोड उन्मूलन: यदि कोई दुष्प्रभावित ऑपरेशन किसी वेरिएबल पर निर्भर नहीं करता है, तो इस वेरिएबल को डेड माना जाता है और इसे हटाया जा सकता है। | ||
* डायनामिक ग्राफ एनालिटिक्स: ग्राफबोल्ट<ref>{{cite conference |author1=Mugilan Mariappan |author2=Keval Vora |title=GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs |book-title=In European Conference on Computer Systems (EuroSys'19)|pages=25:1–25:16|year=2019|doi=10.1145/3302424.3303974 }}</ref> और किकस्टार्टर<ref>{{cite conference |author1=Keval Vora |author2=Rajiv Gupta |author3=Guoqing Xu |title=KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations |book-title=In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'17)|pages=237–251|year=2017|doi=10.1145/3093337.3037748 |doi-access=free }}</ref> ग्राफ़ संरचना में परिवर्तन होने पर [[वृद्धिशील कंप्यूटिंग]] के लिए मूल्य | * डायनामिक ग्राफ एनालिटिक्स: ग्राफबोल्ट<ref>{{cite conference |author1=Mugilan Mariappan |author2=Keval Vora |title=GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs |book-title=In European Conference on Computer Systems (EuroSys'19)|pages=25:1–25:16|year=2019|doi=10.1145/3302424.3303974 }}</ref> और किकस्टार्टर<ref>{{cite conference |author1=Keval Vora |author2=Rajiv Gupta |author3=Guoqing Xu |title=KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations |book-title=In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'17)|pages=237–251|year=2017|doi=10.1145/3093337.3037748 |doi-access=free }}</ref> ग्राफ़ संरचना में परिवर्तन होने पर [[वृद्धिशील कंप्यूटिंग]] के लिए मूल्य आश्रितताएँ कैप्चर करें। | ||
* [[स्प्रेडशीट]] कैलकुलेटर। उन्हें इस आलेख में उपयोग किए गए उदाहरण के समान एक सही गणना क्रम प्राप्त करने की आवश्यकता है। | * [[स्प्रेडशीट]] कैलकुलेटर। उन्हें इस आलेख में उपयोग किए गए उदाहरण के समान एक सही गणना क्रम प्राप्त करने की आवश्यकता है। | ||
* मॉडल में डेटा बदलने पर कौन से विज़ुअल तत्वों को अपडेट करना है, यह जानने के लिए [[XForms]] जैसे वेब फॉर्म मानक। | * मॉडल में डेटा बदलने पर कौन से विज़ुअल तत्वों को अपडेट करना है, यह जानने के लिए [[XForms]] जैसे वेब फॉर्म मानक। | ||
* वीडियो गेम, विशेष रूप से [[पहेली वीडियो गेम]] और [[ साहसिक खेल ]], जिन्हें अक्सर इन-गेम क्रियाओं के बीच निर्भर संबंधों के ग्राफ के रूप में डिज़ाइन किया जाता है।<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 50: | Line 50: | ||
* [[कॉल ग्राफ़]] | * [[कॉल ग्राफ़]] | ||
* [[टोपोलॉजिकल सॉर्ट]] | * [[टोपोलॉजिकल सॉर्ट]] | ||
* [[डेटा निर्भरता]] | * [[डेटा निर्भरता|डेटा आश्रितता]] | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 10:13, 15 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) |
गणित, कंप्यूटर विज्ञान और डिजिटल इलेक्ट्रॉनिक्स में, आश्रितता ग्राफ़ एक दिष्ट ग्राफ है जो एक दूसरे के प्रति कई वस्तुओं की आश्रितता को निरूपित करता है। मूल्यांकन अनुक्रम व्युत्पन्न करना या मूल्यांकन अनुक्रम की अनुपस्थिति संभव है जो आश्रितता ग्राफ से दी गई आश्रितता का रेस्पेक्ट करती है।
परिभाषा
वस्तुओं का एक सेट दिया गया और एक सकर्मक संबंध साथ आश्रितता का मॉडलिंग a, b पर निर्भर करता है (a को पहले b का मूल्यांकन करने की आवश्यकता है), आश्रितता ग्राफ एक ग्राफ है साथ आर की सकर्मक कमी
उदाहरण के लिए, एक साधारण कैलकुलेटर मान लें। यह कैलकुलेटर वेरिएबल्स के लिए स्थिर मानों को निर्दिष्ट करने और तीसरे वेरिएबल को ठीक दो वेरिएबल्स का योग निर्दिष्ट करने का समर्थन करता है। A = B+C जैसे कई समीकरण दिए गए हैं; बी = 5+डी; सी=4; डी=2; , तब और . आप इस संबंध को सीधे प्राप्त कर सकते हैं: A, B और C पर निर्भर करता है, क्योंकि आप दो चर जोड़ सकते हैं यदि और केवल तभी जब आप दोनों चर के मान जानते हों। इस प्रकार, A की गणना करने से पहले B की गणना की जानी चाहिए। हालाँकि, C और D के मान तुरंत ज्ञात हो जाते हैं, क्योंकि वे संख्या शाब्दिक हैं।
असंभव मूल्यांकन को पहचानना
आश्रितता ग्राफ में, आश्रितता के चक्र (जिसे परिपत्र आश्रितता भी कहा जाता है) ऐसी स्थिति की ओर ले जाता है जिसमें कोई वैध मूल्यांकन आदेश मौजूद नहीं होता है, क्योंकि चक्र में किसी भी वस्तु का मूल्यांकन पहले नहीं किया जा सकता है। यदि आश्रितता ग्राफ में कोई परिपत्र आश्रितता नहीं है, तो यह एक दिष्ट चक्रीय ग्राफ बनाता है, और टोपोलॉजिकल छँटाई द्वारा एक मूल्यांकन क्रम पाया जा सकता है। अधिकांश टोपोलॉजिकल सॉर्टिंग एल्गोरिदम भी अपने इनपुट में चक्रों का पता लगाने में सक्षम हैं; हालाँकि, पता लगाए गए चक्रों के लिए उचित हैंडलिंग प्रदान करने के लिए टोपोलॉजिकल सॉर्टिंग से अलग चक्र का पता लगाना (ग्राफ सिद्धांत) करना वांछनीय हो सकता है।
पहले से सरल कैलकुलेटर मान लें। समीकरण प्रणाली A=B; बी=डी+सी; सी=डी+ए; डी=12; ए, बी और सी द्वारा बनाई गई एक गोलाकार आश्रितता शामिल है, क्योंकि बी का मूल्यांकन ए से पहले किया जाना चाहिए, सी का मूल्यांकन से पहले किया जाना चाहिए 'बी', और 'ए' का मूल्यांकन 'सी' से पहले किया जाना चाहिए।
मूल्यांकन आदेश निकालना
एक सही मूल्यांकन क्रम एक क्रमांकन है वे वस्तुएँ जो आश्रितता ग्राफ़ के नोड्स बनाती हैं ताकि निम्नलिखित समीकरण कायम रहे: साथ . इसका मतलब है, यदि क्रमांकन दो तत्वों का आदेश देता है और ताकि पहले मूल्यांकन किया जाएगा , तब पर निर्भर नहीं रहना चाहिए .
एक से अधिक सही मूल्यांकन क्रम हो सकते हैं। वास्तव में, एक सही नंबरिंग एक टोपोलॉजिकल सॉर्टिंग है, और कोई भी टोपोलॉजिकल ऑर्डर एक सही नंबरिंग है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही टोपोलॉजिकल ऑर्डर प्राप्त करता है, एक सही मूल्यांकन क्रम प्राप्त करता है।
ऊपर दिए गए सरल कैलकुलेटर को एक बार फिर से मान लें। समीकरण प्रणाली A = B+C दिया गया है; बी = 5+डी; सी=4; डी=2; , एक सही मूल्यांकन क्रम होगा (डी, सी, बी, ए)। हालाँकि, (सी, डी, बी, ए) भी एक सही मूल्यांकन क्रम है।
मोनोइड संरचना
एक एसाइक्लिक आश्रितता ग्राफ एक ट्रेस मोनॉइड के ट्रेस से इस प्रकार मेल खाता है:[1]: 12
- एक समारोह प्रत्येक शीर्ष को वर्णमाला के एक प्रतीक के साथ लेबल करें
- एक किनारा है या अगर और केवल अगर आश्रितता संबंध में है .
- दो ग्राफ़ समान माने जाते हैं यदि उनके लेबल और किनारे मेल खाते हों।
फिर एक सही मूल्यांकन क्रम द्वारा क्रमित शीर्ष लेबल वाली स्ट्रिंग एक ट्रेस की एक स्ट्रिंग से मेल खाती है।
मोनोइडल ऑपरेशन असंयुक्त संघ लेता है दो ग्राफ़ के शीर्ष सेटों में से, प्रत्येक ग्राफ़ में मौजूदा किनारों को संरक्षित करता है, और पहले से दूसरे तक नए किनारों को खींचता है जहां आश्रितता संबंध अनुमति देता है,[1]: 14
पहचान खाली ग्राफ है.
उदाहरण
आश्रितता ग्राफ़ का उपयोग इसमें किया जाता है:
- स्वचालित सॉफ़्टवेयर इंस्टालर : वे सॉफ़्टवेयर पैकेज (इंस्टॉलेशन) की तलाश में ग्राफ़ पर चलते हैं जो आवश्यक हैं लेकिन अभी तक इंस्टॉल नहीं हुए हैं। आश्रितता पैकेजों के युग्मन (कंप्यूटर विज्ञान) द्वारा दी जाती है।
- सॉफ्टवेयर बिल्ड स्क्रिप्ट जैसे यूनिक्स बनाओ (सॉफ्टवेयर) , नोड.जेएस एनपीएम इंस्टाल, पीएचपी कंपोजर, ट्विटर बोवर इंस्टाल या अपाचे एंट। उन्हें यह जानने की जरूरत है कि कौन सी फाइलें बदल गई हैं, इसलिए केवल सही फाइलों को फिर से संकलित करने की जरूरत है।
- संकलक प्रौद्योगिकी और औपचारिक भाषा कार्यान्वयन में:
- निर्देश शेड्यूलिंग: आश्रितता ग्राफ़ की गणना असेंबली कोड या मध्यवर्ती निर्देशों के ऑपरेंड के लिए की जाती है और निर्देशों के लिए इष्टतम क्रम निर्धारित करने के लिए उपयोग किया जाता है।
- डेड कोड उन्मूलन: यदि कोई दुष्प्रभावित ऑपरेशन किसी वेरिएबल पर निर्भर नहीं करता है, तो इस वेरिएबल को डेड माना जाता है और इसे हटाया जा सकता है।
- डायनामिक ग्राफ एनालिटिक्स: ग्राफबोल्ट[2] और किकस्टार्टर[3] ग्राफ़ संरचना में परिवर्तन होने पर वृद्धिशील कंप्यूटिंग के लिए मूल्य आश्रितताएँ कैप्चर करें।
- स्प्रेडशीट कैलकुलेटर। उन्हें इस आलेख में उपयोग किए गए उदाहरण के समान एक सही गणना क्रम प्राप्त करने की आवश्यकता है।
- मॉडल में डेटा बदलने पर कौन से विज़ुअल तत्वों को अपडेट करना है, यह जानने के लिए XForms जैसे वेब फॉर्म मानक।
- वीडियो गेम, विशेष रूप से पहेली वीडियो गेम और साहसिक खेल , जिन्हें अक्सर इन-गेम क्रियाओं के बीच निर्भर संबंधों के ग्राफ के रूप में डिज़ाइन किया जाता है।[4]
आश्रितता ग्राफ़ इसका एक पहलू है:
- बाधाओं का सिद्धांत#पौधे के प्रकार: कच्चे माल को कई निर्भर चरणों के माध्यम से उत्पादों में संसाधित किया जाता है।
- जॉब शॉप शेड्यूलिंग: कंप्यूटर विज्ञान में संबंधित सैद्धांतिक समस्याओं का संग्रह।
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PDF). In Rozenberg, G.; Diekert, V. (eds.). निशानों की किताब. Singapore: World Scientific. ISBN 981-02-2058-8. Retrieved 18 April 2021.
- ↑ Mugilan Mariappan; Keval Vora (2019). "GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs". In European Conference on Computer Systems (EuroSys'19). pp. 25:1–25:16. doi:10.1145/3302424.3303974.
- ↑ Keval Vora; Rajiv Gupta; Guoqing Xu (2017). "KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations". In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'17). pp. 237–251. doi:10.1145/3093337.3037748.
- ↑ Gilbert, Ron. "पहेली निर्भरता चार्ट". Grumpy Gamer (in English). Retrieved 11 January 2020.
- Balmas, Francoise (2001) Displaying dependence graphs: a hierarchical approach, [1] wcre, p. 261, Eighth Working Conference on Reverse Engineering (WCRE'01)
