गम्यता: Difference between revisions

Revision as of 10:21, 10 July 2023

ग्राफ सिद्धांत में, गम्यता ग्राफ के अन्दर शीर्ष (ग्राफ सिद्धांत) से दूसरे तक जाने की क्षमता को संदर्भित करती है। शीर्ष $s$ शीर्ष $t$ तक पहुंच सकता है (और $t$ $s$ से पहुंचा जा सकता है ) यदि ग्राफ़ सिद्धांत मूल शीर्ष (अर्थात पथ (ग्राफ़ सिद्धांत)) की शब्दावली का क्रम उपस्थित है जो $s$ से प्रारंभ होता है और $t$ के साथ समाप्त होता है .

एक अप्रत्यक्ष ग्राफ़ में, शीर्षों के सभी युग्मों के बीच पहुंच को ग्राफ़ के कनेक्टेड घटक (ग्राफ़ सिद्धांत) की पहचान करके निर्धारित किया जा सकता है। ऐसे ग्राफ़ में शीर्षों का कोई भी जोड़ा दूसरे तक पहुंच सकता है यदि वे ही जुड़े हुए घटक से संबंधित हों; इसलिए, ऐसे ग्राफ़ में, पहुंच योग्यता सममित है ( $s$ पहुँचती है $t$ आईएफएफ $t$ $s$ पहुँचती है ). अप्रत्यक्ष ग्राफ़ के जुड़े घटकों को रैखिक समय में पहचाना जा सकता है। इस आलेख का शेष भाग निर्देशित ग्राफ में जोड़ीवार पहुंच योग्यता निर्धारित करने की अधिक कठिन समस्या पर केंद्रित है (जो, संयोग से, सममित होने की आवश्यकता नहीं है)।

परिभाषा

एक निर्देशित ग्राफ़ $G=(V,E)$ के लिए , शीर्ष सेट $V$ के साथ और किनारा सेट $E$ , गम्यता सम्बन्ध (गणित) का $G$ का सकर्मक समापन $E$ है , जिसका अर्थ है सभी क्रमित जोड़ियों का समुच्चय $(s,t)$ शीर्षों में से $V$ जिसके लिए शीर्षों का क्रम उपस्थित है $v_{0}=s,v_{1},v_{2},...,v_{k}=t$ ऐसे कि किनारा $(v_{i-1},v_{i})$ सभी $1\leq i\leq k$ के लिए $E$ में है.^[1]

यदि $G$ निर्देशित अचक्रीय ग्राफ है, तो इसका गम्यता संबंध आंशिक क्रम है; किसी भी आंशिक आदेश को इस तरह से परिभाषित किया जा सकता है, उदाहरण के लिए इसकी सकर्मक कमी के पहुंच योग्यता संबंध के रूप में।^[2] इसका उल्लेखनीय परिणाम यह है कि चूंकि आंशिक आदेश सममित-विरोधी हैं, यदि $s$ से $t$ तक पहुँच सकते हैं , जिससे हम उसे जानते हैं कि $t$ $s$ तक नहीं पहूंच सकता है. सहज रूप से, यदि हम यात्रा कर सकें $s$ को $t$ और वापस $s$ , तब $G$ इसमें चक्र (ग्राफ़ सिद्धांत) सम्मिलित होगा, जो इस बात का खंडन करता है कि यह चक्रीय है। यदि $G$ निर्देशित है, किन्तु चक्रीय नहीं है (अर्थात इसमें कम से कम चक्र सम्मिलित है), तो इसका पहुंच योग्यता संबंध आंशिक आदेश के अतिरिक्त पूर्व आदेश के अनुरूप होता है।^[3]

एल्गोरिदम

गम्यता निर्धारित करने के लिए एल्गोरिदम दो वर्गों में आते हैं: वे जिनमें डेटा प्री-प्रोसेसिंग की आवश्यकता होती है और वे जो नहीं करते हैं।

यदि आपके पास बनाने के लिए केवल (या कुछ) प्रश्न हैं, तो अधिक जटिल डेटा संरचनाओं का उपयोग छोड़ना और वांछित जोड़ी की पहुंच की सीधे गणना करना अधिक कुशल हो सकता है। इसे चौड़ाई पहली खोज या पुनरावृत्तीय गहनता गहराई-पहली खोज जैसे एल्गोरिदम का उपयोग करके रैखिक समय में पूरा किया जा सकता है।^[4]

यदि आप कई प्रश्न पूछ रहे होंगे, तो अधिक परिष्कृत विधि का उपयोग किया जा सकता है; विधि का स्पष्ट चुनाव विश्लेषण किए जा रहे ग्राफ़ की प्रकृति पर निर्भर करता है। प्रीप्रोसेसिंग समय और कुछ अतिरिक्त स्टोरेज स्थान के बदले में, हम डेटा संरचना बना सकते हैं जो किसी भी जोड़े पर पहुंच योग्य प्रश्नों का उत्तर कम से कम समय में दे सकती है। $O(1)$ समय तीन अलग-अलग, तेजी से विशिष्ट स्थितियों के लिए तीन अलग-अलग एल्गोरिदम और डेटा संरचनाएं नीचे उल्लिखित हैं।

फ़्लॉइड-वॉर्शल एल्गोरिथम

फ्लोयड-वॉर्शल एल्गोरिथ्म ^[5] किसी भी निर्देशित ग्राफ के ट्रांजिटिव क्लोजर की गणना करने के लिए इसका उपयोग किया जा सकता है, जो उपरोक्त परिभाषा के अनुसार गम्यता संबंध को जन्म देता है।

एल्गोरिदम की आवश्यकता है $O(|V|^{3})$ समय और $O(|V|^{2})$ सबसे व्यर्थ स्थिति में अंतरिक्ष. यह एल्गोरिदम पूरी तरह से पहुंच योग्यता में रुचि नहीं रखता है क्योंकि यह शीर्षों के सभी जोड़े के बीच सबसे छोटी पथ दूरी की भी गणना करता है। नकारात्मक चक्र वाले ग्राफ़ के लिए, सबसे छोटा पथ अपरिभाषित हो सकता है, किन्तु जोड़ियों के बीच पहुंच को अभी भी नोट किया जा सकता है।

थोरुप का एल्गोरिदम

समतलीय ग्राफ निर्देशित ग्राफ़ के लिए, बहुत तेज़ विधि उपलब्ध है, जैसा कि 2004 में मिकेल थोरुप द्वारा वर्णित है।^[6] यह विधि समतलीय ग्राफ़ पर पहुंच योग्यता संबंधी प्रश्नों का उत्तर दे सकती है $O(1)$ व्यय करने के बाद का समय $O(n\log {n})$ डेटा संरचना बनाने के लिए प्रीप्रोसेसिंग समय $O(n\log {n})$ आकार यह एल्गोरिदम अनुमानित न्यूनतम पथ दूरी के साथ-साथ मार्ग की जानकारी भी प्रदान कर सकता है।

समग्र दृष्टिकोण प्रत्येक शीर्ष के साथ तथाकथित विभाजक पथों का अपेक्षाकृत छोटा सेट जोड़ना है जैसे कि शीर्ष से कोई भी पथ $v$ किसी अन्य शीर्ष पर $w$ से जुड़े विभाजकों में से कम से कम से निकलना होगा $v$ या $w$ . पहुंच योग्यता से संबंधित अनुभागों की रूपरेखा इस प्रकार है।

एक ग्राफ दिया गया $upper G$

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 114: / Line 114: @@
 यदि <math>G</math> इन गुणों को प्रदर्शित करता है, तो हम केवल ग्राफ़ <math>O(n)</math> को प्रीप्रोसेस कर सकते हैं  केवल समय और स्टोरेज <math>O(\log{n})</math> प्रति शीर्ष अतिरिक्त बिट्स, उत्तर देता है शीर्षों के किसी भी जोड़े के लिए पहुंच योग्यता संबंधी प्रश्न <math>O(1)</math> साधारण के साथ समय तुलना करती है।
-प्रीप्रोसेसिंग निम्नलिखित चरणों का पालन करती है। हम नया शीर्ष <math>s</math> जोड़ते हैं  जिसमें प्रत्येक 0-डिग्री शीर्ष पर किनारा है, और अन्य नया शीर्ष है <math>t</math> प्रत्येक 0-आउटडिग्री शीर्ष से किनारों के साथ। ध्यान दें कि के गुण <math>G</math> हमें समतलता बनाए रखते हुए ऐसा करने की अनुमति दें, अर्थात, इन परिवर्धन के बाद भी कोई किनारा क्रॉसिंग नहीं होगा। प्रत्येक शीर्ष के लिए हम ग्राफ़ की समतलता के क्रम में आसन्नताओं (आउट-किनारों) की सूची संग्रहीत करते हैं (उदाहरण के लिए, ग्राफ़ के एम्बेडिंग के संबंध में दक्षिणावर्त)। फिर हम काउंटर आरंभ करते हैं <math>i = n + 1</math> और डेप्थ-फर्स्ट ट्रैवर्सल प्रारंभ करें <math>s</math>. इस ट्रैवर्सल के दौरान, प्रत्येक शीर्ष की आसन्न सूची को आवश्यकतानुसार बाएं से दाएं देखा जाता है। जैसे ही ट्रैवर्सल के स्टैक से कोने निकाले जाते हैं, उन्हें मान के साथ लेबल किया जाता है <math>i</math>, और <math>i</math> फिर घटाया जाता है. ध्यान दें कि <math>t</math> सदैव मूल्य के साथ लेबल किया जाता है <math>n+1</math> और <math>s</math> सदैव इसके साथ लेबल किया जाता है <math>0</math>. फिर गहराई-पहले ट्रैवर्सल को दोहराया जाता है, किन्तु इस बार प्रत्येक शीर्ष की आसन्न सूची को दाएं से बाएं ओर देखा जाता है।
+प्रीप्रोसेसिंग निम्नलिखित चरणों का पालन करती है। हम नया शीर्ष <math>s</math> जोड़ते हैं  जिसमें प्रत्येक 0-डिग्री शीर्ष पर किनारा है, और अन्य नया शीर्ष है <math>t</math> प्रत्येक 0-आउटडिग्री शीर्ष से किनारों के साथ ध्यान दें कि के गुण <math>G</math> हमें समतलता बनाए रखते हुए ऐसा करने की अनुमति दें, अर्थात, इन परिवर्धन के बाद भी कोई किनारा क्रॉसिंग नहीं होता है। प्रत्येक शीर्ष के लिए हम ग्राफ़ की समतलता के क्रम में आसन्नताओं (आउट-किनारों) की सूची संग्रहीत करते हैं (उदाहरण के लिए, ग्राफ़ के एम्बेडिंग के संबंध में दक्षिणावर्त)। फिर हम काउंटर आरंभ करते हैं <math>i = n + 1</math> और डेप्थ-फर्स्ट ट्रैवर्सल प्रारंभ करें <math>s</math>. इस ट्रैवर्सल के समय, प्रत्येक शीर्ष की आसन्न सूची को आवश्यकतानुसार बाएं से दाएं देखा जाता है। जैसे ही ट्रैवर्सल के स्टैक से कोने निकाले जाते हैं, उन्हें मान के साथ लेबल किया जाता है <math>i</math>, और <math>i</math> फिर घटाया जाता है. ध्यान दें कि <math>t</math> सदैव मूल्य के साथ लेबल किया जाता है <math>n+1</math> और <math>s</math> सदैव इसके <math>0</math> साथ लेबल किया जाता है . फिर गहराई-पहले ट्रैवर्सल को दोहराया जाता है, किन्तु इस बार प्रत्येक शीर्ष की आसन्न सूची को दाएं से बाएं ओर देखा जाता है।
-पूरा हो जाने पर, <math>s</math> और <math>t</math>, और उनके घटना किनारों को हटा दिया जाता है। प्रत्येक
-शेष शीर्ष मानों के साथ 2-आयामी लेबल संग्रहीत करता है <math>1</math> को <math>n</math>.
-दो शीर्ष दिए गए हैं <math>u</math> और <math>v</math>, और उनके लेबल <math>L(u) = (a_1, a_2)</math> और <math>L(v) =(b_1, b_2)</math>, हम ऐसा कहते हैं <math>L(u) < L(v)</math> यदि और केवल यदि <math>a_1 \leq b_1</math>, <math>a_2 \leq
-b_2</math>, और कम से कम घटक उपस्थित है <math>a_1</math> या <math>a_2</math> जो सख्ती से है
-से कम <math>b_1</math> या <math>b_2</math>, क्रमश।
-इस विधि का मुख्य परिणाम तो यही बताता है <math>v</math> से पहुंचा जा सकता है <math>u</math> यदि व
+पूरा हो जाने पर, <math>s</math> और <math>t</math>, और उनके घटना किनारों को हटा दिया जाता है। प्रत्येक शेष शीर्ष मानों के साथ 2-आयामी लेबल संग्रहीत करता है <math>1</math> को <math>n</math>.दो शीर्ष <math>u</math> और <math>v</math> दिए गए हैं , और उनके लेबल <math>L(u) = (a_1, a_2)</math> और <math>L(v) =(b_1, b_2)</math>, हम ऐसा कहते हैं <math>L(u) < L(v)</math> यदि और केवल यदि <math>a_1 \leq b_1</math>, <math>a_2 \leq
-केवल <math>L(u) < L(v)</math>जिसकी गणना आसानी से की जा सकती है <math>O(1)</math> समय।
+b_2</math>, और कम से कम घटक उपस्थित  <math>a_1</math> या <math>a_2</math> है जो कठोर क्रमश   <math>b_1</math> या <math>b_2</math>, है
-==संबंधित समस्याएँ==
+इस विधि का मुख्य परिणाम तो यही बताता है <math>v</math> से पहुंचा जा सकता है <math>u</math> यदि व केवल <math>L(u) < L(v)</math>जिसकी गणना <math>O(1)</math> समय सरलता से की जा सकती है ।
-एक संबंधित समस्या कुछ संख्याओं के साथ गम्यता प्रश्नों को हल करना है <math>k</math> शीर्ष विफलताओं का. उदाहरण के लिए: शीर्ष कर सकते हैं <math>u</math> अभी भी शीर्ष पर पहुंचें <math>v</math> भले ही शीर्ष <math>s_1, s_2, ..., s_k</math> विफल हो गए हैं और अब उपयोग नहीं किया जा सकता? समान समस्या शीर्ष विफलताओं या दोनों के मिश्रण के अतिरिक्त किनारे विफलताओं पर विचार कर सकती है। चौड़ाई-पहली खोज तकनीक ऐसे प्रश्नों पर भी उतनी ही अच्छी तरह काम करती है, किन्तु कुशल ओरेकल का निर्माण करना अधिक चुनौतीपूर्ण है।<ref>{{citation
+==संबंधित समस्याएँ                                                                                                                                                                                   ==
+एक संबंधित समस्या कुछ संख्याओं के साथ गम्यता प्रश्नों को हल करना है <math>k</math> शीर्ष विफलताओं का. उदाहरण के लिए: शीर्ष <math>u</math> कर सकते हैं  अभी भी शीर्ष पर पहुंचें <math>v</math> संभवतः शीर्ष <math>s_1, s_2, ..., s_k</math> विफल हो गए हैं और अब उपयोग नहीं किया जा सकता? समान समस्या शीर्ष विफलताओं या दोनों के मिश्रण के अतिरिक्त किनारे विफलताओं पर विचार कर सकती है। चौड़ाई-पहली खोज तकनीक ऐसे प्रश्नों पर भी उतनी ही अच्छी तरह काम करती है, किन्तु कुशल ओरेकल का निर्माण करना अधिक चुनौतीपूर्ण है।<ref>{{citation
   | last1 = Demetrescu | first1 = Camil
   | last2 = Thorup | first2 = Mikkel | author2-link = Mikkel Thorup
@@ Line 143: / Line 140: @@
   | title = Connectivity in Networks and Compact Labeling Schemes for Emergency Planning
   | location = Universite de Bordeaux
-  | url = https://tel.archives-ouvertes.fr/tel-01110316/document }}.</ref>
+  | url = https://tel.archives-ouvertes.fr/tel-01110316/document }}.</ref> गम्यता प्रश्नों से संबंधित अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर गम्यता संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] के लिए प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (जिससे इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।
-गम्यता प्रश्नों से संबंधित अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर गम्यता संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] के लिए प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (ताकि इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।
-== यह भी देखें ==
+== यह भी देखें                                                                                                                                                       ==
 * [[गैमॉइड]]
-* सेंट-कनेक्टिविटी|एसटी-कनेक्टिविटी
+* सेंट-कनेक्टिविटी
-==संदर्भ==
+==संदर्भ                                                                                                                                                                                                                                                             ==
 {{reflist}}
 [[Category: ग्राफ़ कनेक्टिविटी]]

Anonymous

Search

गम्यता: Difference between revisions

Namespaces

More

Page actions

Revision as of 10:21, 10 July 2023

Contents

परिभाषा

एल्गोरिदम

फ़्लॉइड-वॉर्शल एल्गोरिथम

थोरुप का एल्गोरिदम