आश्रितता ग्राफ: Difference between revisions

Revision as of 13:19, 15 July 2023

गणित, कंप्यूटर विज्ञान और डिजिटल इलेक्ट्रॉनिक्स में, आश्रितता ग्राफ़ एक दिष्ट ग्राफ है जो एक दूसरे के प्रति कई वस्तुओं की आश्रितता को निरूपित करता है। मूल्यांकन अनुक्रम व्युत्पन्न करना या मूल्यांकन अनुक्रम की अनुपस्थिति संभव है जो आश्रितता ग्राफ से दी गई आश्रितता का रेस्पेक्ट करती है।

परिभाषा

वस्तुओं के एक समुच्चय को देखते हुए S और एक सकर्मक संबंध $R\subseteq S\times S$ $(a,b)\in R$ के साथ एक आश्रितता मॉडलिंग "a, b पर आश्रित है" (a को पहले b का मूल्यांकन करने की आवश्यकता है), आश्रितता ग्राफ एक ग्राफ $G=(S,T)$ है जिसमें $T\subseteq R$ R का सकर्मक समानयन है|

उदाहरण के लिए, एक साधारण परिगणक को कल्पना करते हैं। यह परिगणक चरों के लिए नियत मानों को निर्दिष्ट करने और तीसरे चर को ठीक दो चरों का योग निर्दिष्ट करने का समर्थन करता है। "A = B+C; B = 5+D; C=4; D=2;" जैसे कई समीकरण दिए गए हैं, तो $S=\{A,B,C,D\}$ और $R=\{(A,B),(A,C),(B,D)\}$ | आप इस संबंध को स्पष्ट रुप से प्राप्त कर सकते हैं: 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 से पहले किया जाना चाहिए |

मूल्यांकन अनुक्रम व्युत्पत्ति

एक सही मूल्यांकन अनुक्रम उन वस्तुओं का संख्यांकन $n:S\rightarrow \mathbb {N}$ है जो आश्रितता ग्राफ़ के नोड्स बनाते हैं ताकि निम्नलिखित समीकरण होल्ड रहे: $n(a)<n(b)\Rightarrow (a,b)\notin R$ $a,b\in S$ के साथ है। इसका अर्थ है, यदि संख्यांकन दो अवयवों $a$ और $b$ को क्रमबद्ध करता है ताकि $a$ का मूल्यांकन $b$ से पहले किया जाएगा, तो $a$ को $b$ पर आश्रित नहीं होना चाहिए।

एक से अधिक सही मूल्यांकन अनुक्रम हो सकते हैं। वास्तव में, एक सही संख्यांकन एक सांस्थितिक अनुक्रम है, और कोई भी सांस्थितिक अनुक्रम एक सही संख्यांकन है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही सांस्थितिक अनुक्रम व्युत्पन्न करता है, एक सही मूल्यांकन अनुक्रम व्युत्पन्न करता है।

ऊपर दिए गए साधारण परिगणक की एक बार फिर से कल्पना करते हैं। समीकरण पद्धति "A = B+C; B = 5+D; C=4; D=2;" को देखते हुए, एक सही मूल्यांकन अनुक्रम (D, C, B, A) होता है। हालाँकि, (C, D, B, A) भी एक सही मूल्यांकन अनुक्रम है।

एकाभ संरचना

एक अचक्रीय आश्रितता ग्राफ एक अनुरेख एकाभ के अनुरेख से इस प्रकार संगत है:^[1]^: 12

एक फलन $\phi :S\to \Sigma$ प्रत्येक शीर्ष को वर्णाक्षर $\Sigma$ के एक प्रतीक के साथ लेबल करता है
कोई किनारा $a\to b$ या $b\to a$ है यदि और केवल यदि $(\phi (a),\phi (b))$ आश्रितता संबंध $D$ में है|
दो ग्राफ़ समान माने जाते हैं यदि उनके लेबल और किनारे संगत होते है।

फिर एक सही मूल्यांकन अनुक्रम द्वारा क्रमित शीर्ष लेबल वाली श्रृंखला एक अनुरेख की एक श्रृंखला के संगत है।

मोनोइडल प्रचालन $(S_{12},R_{12})=(S_{1},R_{1})\bullet (S_{2},R_{2})$ दो ग्राफ़ के शीर्ष समुच्चयों के असंयुक्त संयोग $S_{12}=S_{1}\sqcup S_{2}$ को लेता है, प्रत्येक ग्राफ़ में उपस्थित किनारों को संरक्षित करता है, और पहले से दूसरे तक नए किनारों को खींचता (ड्रॉ) है जहां आश्रितता संबंध अनुमति देता है,^[1]^: 14

upper R 12 equals upper R 1 square cup upper R 2 square cup StartSet left parenthesis a comma b right parenthesis vertical bar a element of upper S 1 and b element of upper S 2 and left parenthesis phi left parenthesis a right parenthesis comma phi left parenthesis b right parenthesis right parenthesis element of upper D EndSet

[1]

@@ Line 20: / Line 20: @@
 ऊपर दिए गए साधारण परिगणक की एक बार फिर से कल्पना करते हैं। समीकरण पद्धति ''"A = B+C; B = 5+D; C=4; D=2;"'' को देखते हुए, एक सही मूल्यांकन अनुक्रम (''D, C, B, A'') होता है। हालाँकि, (''C, D, B, A'') भी एक सही मूल्यांकन अनुक्रम है।
-== मोनोइड संरचना ==
+== एकाभ संरचना ==
-एक एसाइक्लिक आश्रितता ग्राफ एक [[ट्रेस मोनॉइड]] के ट्रेस से इस प्रकार मेल खाता है:<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}}
+एक अचक्रीय आश्रितता ग्राफ एक [[ट्रेस मोनॉइड|अनुरेख एकाभ]] के अनुरेख से इस प्रकार संगत है:<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> दो ग्राफ़ के शीर्ष सेटों में से, प्रत्येक ग्राफ़ में मौजूदा किनारों को संरक्षित करता है, और पहले से दूसरे तक नए किनारों को खींचता है जहां आश्रितता संबंध अनुमति देता है,<ref name=IntroToTraceTheory/>{{rp|14}}
+[[मोनोइड|मोनोइडल]] प्रचालन <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>
-पहचान खाली ग्राफ है.
+तत्समक (सर्वसमिका) रिक्त ग्राफ है|
 ==उदाहरण==

Anonymous

Search

आश्रितता ग्राफ: Difference between revisions

Namespaces

More

Page actions

Revision as of 13:19, 15 July 2023

Contents

परिभाषा

असंभव मूल्यांकन को पहचानना

मूल्यांकन अनुक्रम व्युत्पत्ति

एकाभ संरचना