गम्यता: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Whether one vertex can be reached from another in a graph}} ग्राफ सिद्धांत में, रीचैबिलिटी एक...")
 
No edit summary
Line 1: Line 1:
{{Short description|Whether one vertex can be reached from another in a graph}}
{{Short description|Whether one vertex can be reached from another in a graph}}


[[ग्राफ सिद्धांत]] में, रीचैबिलिटी एक ग्राफ के भीतर एक वर्टेक्स (ग्राफ सिद्धांत) से दूसरे तक जाने की क्षमता को संदर्भित करती है। एक शिखर <math>s</math> एक शिखर तक पहुंच सकता है <math>t</math> (और <math>t</math> से पहुंचा जा सकता है <math>s</math>) यदि ग्राफ़ सिद्धांत # मूल शीर्ष (अर्थात एक पथ (ग्राफ़ सिद्धांत)) की शब्दावली का एक क्रम मौजूद है जो से शुरू होता है <math>s</math> और के साथ समाप्त होता है <math>t</math>.
[[ग्राफ सिद्धांत]] में, गम्यता ग्राफ के भीतर वर्टेक्स (ग्राफ सिद्धांत) से दूसरे तक जाने की क्षमता को संदर्भित करती है। शिखर <math>s</math> शिखर तक पहुंच सकता है <math>t</math> (और <math>t</math> से पहुंचा जा सकता है <math>s</math>) यदि ग्राफ़ सिद्धांत # मूल शीर्ष (अर्थात पथ (ग्राफ़ सिद्धांत)) की शब्दावली का क्रम मौजूद है जो से शुरू होता है <math>s</math> और के साथ समाप्त होता है <math>t</math>.


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


== परिभाषा ==
== परिभाषा ==
एक निर्देशित ग्राफ़ के लिए <math>G = (V, E)</math>, वर्टेक्स सेट के साथ <math>V</math> और किनारा सेट <math>E</math>, रीचैबिलिटी रिलेशन (गणित) का <math>G</math> का [[सकर्मक समापन]] है <math>E</math>, जिसका अर्थ है सभी क्रमित जोड़ियों का समुच्चय <math>(s,t)</math> शीर्षों में से <math>V</math> जिसके लिए शीर्षों का एक क्रम मौजूद है <math>v_0 = s, v_1, v_2, ..., v_k = t</math> ऐसे कि किनारा <math>(v_{i-1},v_i)</math> में है <math>E</math> सभी के लिए <math>1 \leq i \leq k</math>.<ref name="skiena">{{citation
एक निर्देशित ग्राफ़ के लिए <math>G = (V, E)</math>, वर्टेक्स सेट के साथ <math>V</math> और किनारा सेट <math>E</math>, गम्यता रिलेशन (गणित) का <math>G</math> का [[सकर्मक समापन]] है <math>E</math>, जिसका अर्थ है सभी क्रमित जोड़ियों का समुच्चय <math>(s,t)</math> शीर्षों में से <math>V</math> जिसके लिए शीर्षों का क्रम मौजूद है <math>v_0 = s, v_1, v_2, ..., v_k = t</math> ऐसे कि किनारा <math>(v_{i-1},v_i)</math> में है <math>E</math> सभी के लिए <math>1 \leq i \leq k</math>.<ref name="skiena">{{citation
  | last = Skiena | first = Steven S.
  | last = Skiena | first = Steven S.
  | contribution = 15.5 Transitive Closure and Reduction
  | contribution = 15.5 Transitive Closure and Reduction
Line 16: Line 16:
  | url = https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA495
  | url = https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA495
  | year = 2011}}.</ref>
  | year = 2011}}.</ref>
अगर <math>G</math> [[निर्देशित अचक्रीय ग्राफ]] है, तो इसका रीचैबिलिटी संबंध आंशिक क्रम है; किसी भी [[आंशिक आदेश]] को इस तरह से परिभाषित किया जा सकता है, उदाहरण के लिए इसकी [[सकर्मक कमी]] के पहुंच योग्यता संबंध के रूप में।<ref>{{citation
अगर <math>G</math> [[निर्देशित अचक्रीय ग्राफ]] है, तो इसका गम्यता संबंध आंशिक क्रम है; किसी भी [[आंशिक आदेश]] को इस तरह से परिभाषित किया जा सकता है, उदाहरण के लिए इसकी [[सकर्मक कमी]] के पहुंच योग्यता संबंध के रूप में।<ref>{{citation
  | last = Cohn | first = Paul Moritz
  | last = Cohn | first = Paul Moritz
  | isbn = 9781852335878
  | isbn = 9781852335878
Line 23: Line 23:
  | title = Basic Algebra: Groups, Rings, and Fields
  | title = Basic Algebra: Groups, Rings, and Fields
  | url = https://books.google.com/books?id=VESm0MJOiDQC&pg=PA17
  | url = https://books.google.com/books?id=VESm0MJOiDQC&pg=PA17
  | year = 2003}}.</ref> इसका एक उल्लेखनीय परिणाम यह है कि चूंकि आंशिक आदेश सममित-विरोधी हैं, यदि <math>s</math> तक पहुँच सकते हैं <math>t</math>, तो हम उसे जानते हैं <math>t</math> नहीं पहूंच सकता <math>s</math>. सहज रूप से, यदि हम यात्रा कर सकें <math>s</math> को <math>t</math> और वापस <math>s</math>, तब <math>G</math> इसमें एक चक्र (ग्राफ़ सिद्धांत) शामिल होगा, जो इस बात का खंडन करता है कि यह चक्रीय है।
  | year = 2003}}.</ref> इसका उल्लेखनीय परिणाम यह है कि चूंकि आंशिक आदेश सममित-विरोधी हैं, यदि <math>s</math> तक पहुँच सकते हैं <math>t</math>, तो हम उसे जानते हैं <math>t</math> नहीं पहूंच सकता <math>s</math>. सहज रूप से, यदि हम यात्रा कर सकें <math>s</math> को <math>t</math> और वापस <math>s</math>, तब <math>G</math> इसमें चक्र (ग्राफ़ सिद्धांत) शामिल होगा, जो इस बात का खंडन करता है कि यह चक्रीय है।
अगर <math>G</math> निर्देशित है, लेकिन चक्रीय नहीं है (अर्थात इसमें कम से कम एक चक्र शामिल है), तो इसका पहुंच योग्यता संबंध आंशिक आदेश के बजाय [[पूर्व आदेश]] के अनुरूप होगा।<ref>{{citation
अगर <math>G</math> निर्देशित है, लेकिन चक्रीय नहीं है (अर्थात इसमें कम से कम चक्र शामिल है), तो इसका पहुंच योग्यता संबंध आंशिक आदेश के बजाय [[पूर्व आदेश]] के अनुरूप होगा।<ref>{{citation
  | last = Schmidt | first = Gunther
  | last = Schmidt | first = Gunther
  | isbn = 9780521762687
  | isbn = 9780521762687
Line 37: Line 37:


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


यदि आपके पास बनाने के लिए केवल एक (या कुछ) प्रश्न हैं, तो अधिक जटिल डेटा संरचनाओं का उपयोग छोड़ना और वांछित जोड़ी की पहुंच की सीधे गणना करना अधिक कुशल हो सकता है। इसे चौड़ाई पहली खोज या [[पुनरावृत्तीय गहनता गहराई-पहली खोज]] जैसे एल्गोरिदम का उपयोग करके [[रैखिक समय]] में पूरा किया जा सकता है।<ref>{{citation
यदि आपके पास बनाने के लिए केवल (या कुछ) प्रश्न हैं, तो अधिक जटिल डेटा संरचनाओं का उपयोग छोड़ना और वांछित जोड़ी की पहुंच की सीधे गणना करना अधिक कुशल हो सकता है। इसे चौड़ाई पहली खोज या [[पुनरावृत्तीय गहनता गहराई-पहली खोज]] जैसे एल्गोरिदम का उपयोग करके [[रैखिक समय]] में पूरा किया जा सकता है।<ref>{{citation
  | last = Gersting | first = Judith L. | author-link = Judith Gersting
  | last = Gersting | first = Judith L. | author-link = Judith Gersting
  | edition = 6th
  | edition = 6th
Line 48: Line 48:
  | url = https://books.google.com/books?id=lvAo3AeJikQC&pg=PA519
  | url = https://books.google.com/books?id=lvAo3AeJikQC&pg=PA519
  | year = 2006}}.</ref>
  | year = 2006}}.</ref>
यदि आप कई प्रश्न पूछ रहे होंगे, तो अधिक परिष्कृत विधि का उपयोग किया जा सकता है; विधि का सटीक चुनाव विश्लेषण किए जा रहे ग्राफ़ की प्रकृति पर निर्भर करता है। प्रीप्रोसेसिंग समय और कुछ अतिरिक्त भंडारण स्थान के बदले में, हम एक डेटा संरचना बना सकते हैं जो किसी भी जोड़े पर पहुंच योग्य प्रश्नों का उत्तर कम से कम समय में दे सकती है। <math>O(1)</math> समय। तीन अलग-अलग, तेजी से विशिष्ट स्थितियों के लिए तीन अलग-अलग एल्गोरिदम और डेटा संरचनाएं नीचे उल्लिखित हैं।
यदि आप कई प्रश्न पूछ रहे होंगे, तो अधिक परिष्कृत विधि का उपयोग किया जा सकता है; विधि का सटीक चुनाव विश्लेषण किए जा रहे ग्राफ़ की प्रकृति पर निर्भर करता है। प्रीप्रोसेसिंग समय और कुछ अतिरिक्त भंडारण स्थान के बदले में, हम डेटा संरचना बना सकते हैं जो किसी भी जोड़े पर पहुंच योग्य प्रश्नों का उत्तर कम से कम समय में दे सकती है। <math>O(1)</math> समय। तीन अलग-अलग, तेजी से विशिष्ट स्थितियों के लिए तीन अलग-अलग एल्गोरिदम और डेटा संरचनाएं नीचे उल्लिखित हैं।


=== फ़्लॉइड-वॉर्शल एल्गोरिथम ===
=== फ़्लॉइड-वॉर्शल एल्गोरिथम ===
Line 63: Line 63:
  | publisher = MIT Press and McGraw-Hill
  | publisher = MIT Press and McGraw-Hill
  | title = [[Introduction to Algorithms]]
  | title = [[Introduction to Algorithms]]
  | year = 2001}}.</ref> किसी भी निर्देशित ग्राफ के ट्रांजिटिव क्लोजर की गणना करने के लिए इसका उपयोग किया जा सकता है, जो उपरोक्त परिभाषा के अनुसार रीचैबिलिटी संबंध को जन्म देता है।
  | year = 2001}}.</ref> किसी भी निर्देशित ग्राफ के ट्रांजिटिव क्लोजर की गणना करने के लिए इसका उपयोग किया जा सकता है, जो उपरोक्त परिभाषा के अनुसार गम्यता संबंध को जन्म देता है।


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


[[ समतलीय ग्राफ ]]़ निर्देशित ग्राफ़ के लिए, एक बहुत तेज़ विधि उपलब्ध है, जैसा कि 2004 में [[मिकेल थोरुप]] द्वारा वर्णित है।<ref>{{citation
[[ समतलीय ग्राफ ]]़ निर्देशित ग्राफ़ के लिए, बहुत तेज़ विधि उपलब्ध है, जैसा कि 2004 में [[मिकेल थोरुप]] द्वारा वर्णित है।<ref>{{citation
  | last = Thorup | first = Mikkel | author-link = Mikkel Thorup
  | last = Thorup | first = Mikkel | author-link = Mikkel Thorup
  | doi = 10.1145/1039488.1039493
  | doi = 10.1145/1039488.1039493
Line 78: Line 78:
  | title = Compact oracles for reachability and approximate distances in planar digraphs
  | title = Compact oracles for reachability and approximate distances in planar digraphs
  | volume = 51
  | volume = 51
  | year = 2004| s2cid = 18864647 }}.</ref> यह विधि एक समतलीय ग्राफ़ पर पहुंच योग्यता संबंधी प्रश्नों का उत्तर दे सकती है <math>O(1)</math> खर्च करने के बाद का समय <math>O(n \log{n})</math> डेटा संरचना बनाने के लिए प्रीप्रोसेसिंग समय <math>O(n \log{n})</math> आकार। यह एल्गोरिदम अनुमानित न्यूनतम पथ दूरी के साथ-साथ मार्ग की जानकारी भी प्रदान कर सकता है।
  | year = 2004| s2cid = 18864647 }}.</ref> यह विधि समतलीय ग्राफ़ पर पहुंच योग्यता संबंधी प्रश्नों का उत्तर दे सकती है <math>O(1)</math> खर्च करने के बाद का समय <math>O(n \log{n})</math> डेटा संरचना बनाने के लिए प्रीप्रोसेसिंग समय <math>O(n \log{n})</math> आकार। यह एल्गोरिदम अनुमानित न्यूनतम पथ दूरी के साथ-साथ मार्ग की जानकारी भी प्रदान कर सकता है।


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


एक ग्राफ दिया गया <math>G</math>, एल्गोरिथ्म एक मनमाना शीर्ष से शुरू होकर शीर्षों को परतों में व्यवस्थित करने से शुरू होता है <math>v_0</math>. परतों को पहले पिछले चरण से पहुंच योग्य सभी शीर्षों पर विचार करके वैकल्पिक चरणों में बनाया गया है (केवल से शुरू करके)। <math>v_0</math>) और फिर सभी शीर्ष जो पिछले चरण तक पहुंचते हैं जब तक कि सभी शीर्षों को एक परत को नहीं सौंपा जाता है। परतों के निर्माण से, प्रत्येक शीर्ष अधिकतम दो परतों में दिखाई देता है, और प्रत्येक पथ (ग्राफ़ सिद्धांत)#विभिन्न प्रकार के पथ, या डिपाथ, में <math>G</math> दो आसन्न परतों के भीतर समाहित है <math>L_i</math> और <math>L_{i+1}</math>. होने देना <math>k</math> बनाई गई अंतिम परत बनें, अर्थात, इसके लिए सबसे कम मान <math>k</math> ऐसा है कि <math>\bigcup_{i=0}^{k} L_i = V</math>.
एक ग्राफ दिया गया <math>G</math>, एल्गोरिथ्म मनमाना शीर्ष से शुरू होकर शीर्षों को परतों में व्यवस्थित करने से शुरू होता है <math>v_0</math>. परतों को पहले पिछले चरण से पहुंच योग्य सभी शीर्षों पर विचार करके वैकल्पिक चरणों में बनाया गया है (केवल से शुरू करके)। <math>v_0</math>) और फिर सभी शीर्ष जो पिछले चरण तक पहुंचते हैं जब तक कि सभी शीर्षों को परत को नहीं सौंपा जाता है। परतों के निर्माण से, प्रत्येक शीर्ष अधिकतम दो परतों में दिखाई देता है, और प्रत्येक पथ (ग्राफ़ सिद्धांत)#विभिन्न प्रकार के पथ, या डिपाथ, में <math>G</math> दो आसन्न परतों के भीतर समाहित है <math>L_i</math> और <math>L_{i+1}</math>. होने देना <math>k</math> बनाई गई अंतिम परत बनें, अर्थात, इसके लिए सबसे कम मान <math>k</math> ऐसा है कि <math>\bigcup_{i=0}^{k} L_i = V</math>.


ग्राफ को फिर से डिग्राफ की एक श्रृंखला के रूप में व्यक्त किया जाता है <math>G_0, G_1, \ldots,
ग्राफ को फिर से डिग्राफ की श्रृंखला के रूप में व्यक्त किया जाता है <math>G_0, G_1, \ldots,
G_{k-1}</math> जहां प्रत्येक <math>G_i = r_i \cup L_i \cup L_{i+1}</math> और कहाँ <math>r_i</math> पिछले सभी स्तरों का संकुचन है <math>L_0 \ldots L_{i-1}</math> एक ही शिखर में. क्योंकि प्रत्येक द्विपथ अधिकतम दो लगातार परतों में प्रकट होता है, और क्योंकि
G_{k-1}</math> जहां प्रत्येक <math>G_i = r_i \cup L_i \cup L_{i+1}</math> और कहाँ <math>r_i</math> पिछले सभी स्तरों का संकुचन है <math>L_0 \ldots L_{i-1}</math> ही शिखर में. क्योंकि प्रत्येक द्विपथ अधिकतम दो लगातार परतों में प्रकट होता है, और क्योंकि
प्रत्येक <math>G_i</math> प्रत्येक द्विपथ में दो लगातार परतों द्वारा निर्मित होता है <math>G</math> कम से कम एक में अपनी संपूर्णता में प्रकट होता है <math>G_i</math> (और लगातार 2 से अधिक ऐसे ग्राफ़ नहीं)
प्रत्येक <math>G_i</math> प्रत्येक द्विपथ में दो लगातार परतों द्वारा निर्मित होता है <math>G</math> कम से कम में अपनी संपूर्णता में प्रकट होता है <math>G_i</math> (और लगातार 2 से अधिक ऐसे ग्राफ़ नहीं)


प्रत्येक के लिए <math>G_i</math>, तीन विभाजकों की पहचान की जाती है, जिन्हें हटाए जाने पर, ग्राफ़ को तीन घटकों में तोड़ देते हैं, जिनमें से प्रत्येक में अधिकतम होते हैं <math>1/2</math> मूल के शीर्ष. जैसा <math>G_i</math> विपरीत डिपाथ की दो परतों से बनाया गया है, प्रत्येक विभाजक में 2 डिपाथ तक हो सकते हैं, सभी विभाजकों पर कुल मिलाकर 6 डिपाथ हो सकते हैं। होने देना <math>S</math> दीपपथों का यह सेट हो। इस बात का प्रमाण कि ऐसे विभाजक हमेशा पाए जा सकते हैं, लिप्टन और टार्जन के समतल विभाजक प्रमेय से संबंधित है, और ये विभाजक रैखिक समय में स्थित हो सकते हैं।
प्रत्येक के लिए <math>G_i</math>, तीन विभाजकों की पहचान की जाती है, जिन्हें हटाए जाने पर, ग्राफ़ को तीन घटकों में तोड़ देते हैं, जिनमें से प्रत्येक में अधिकतम होते हैं <math>1/2</math> मूल के शीर्ष. जैसा <math>G_i</math> विपरीत डिपाथ की दो परतों से बनाया गया है, प्रत्येक विभाजक में 2 डिपाथ तक हो सकते हैं, सभी विभाजकों पर कुल मिलाकर 6 डिपाथ हो सकते हैं। होने देना <math>S</math> दीपपथों का यह सेट हो। इस बात का प्रमाण कि ऐसे विभाजक हमेशा पाए जा सकते हैं, लिप्टन और टार्जन के समतल विभाजक प्रमेय से संबंधित है, और ये विभाजक रैखिक समय में स्थित हो सकते हैं।
Line 112: Line 112:
=== कामेडा का एल्गोरिदम ===
=== कामेडा का एल्गोरिदम ===


[[File:Graph suitable for Kameda's method.svg|thumb|right|200px|कामेडा की विधि के लिए एक उपयुक्त डिग्राफ <math>s</math> और <math>t</math> जोड़ा गया.]]
[[File:Graph suitable for Kameda's method.svg|thumb|right|200px|कामेडा की विधि के लिए उपयुक्त डिग्राफ <math>s</math> और <math>t</math> जोड़ा गया.]]


[[File:Kameda's algorithm run.svg|thumb|right|200px|कामेडा के एल्गोरिथ्म के चलने के बाद ऊपर जैसा ही ग्राफ, प्रत्येक शीर्ष के लिए डीएफएस लेबल दिखा रहा है]]1975 में टी. कामेडा के कारण, पूर्व-प्रसंस्करण के लिए और भी तेज़ विधि,<ref>{{citation
[[File:Kameda's algorithm run.svg|thumb|right|200px|कामेडा के एल्गोरिथ्म के चलने के बाद ऊपर जैसा ही ग्राफ, प्रत्येक शीर्ष के लिए डीएफएस लेबल दिखा रहा है]]1975 में टी. कामेडा के कारण, पूर्व-प्रसंस्करण के लिए और भी तेज़ विधि,<ref>{{citation
Line 123: Line 123:
  | year = 1975
  | year = 1975
  | doi=10.1016/0020-0190(75)90019-8}}.</ref>
  | doi=10.1016/0020-0190(75)90019-8}}.</ref>
यदि ग्राफ [[समतलीय ग्राफ]], निर्देशित एसाइक्लिक ग्राफ है, तो इसका उपयोग किया जा सकता है, और निम्नलिखित अतिरिक्त गुण भी प्रदर्शित करता है: सभी 0-निर्देशित ग्राफ # इंडिग्री और आउटडिग्री और सभी 0-निर्देशित ग्राफ # इंडिग्री और आउटडिग्री शीर्ष ग्राफ सिद्धांत की एक ही शब्दावली पर दिखाई देते हैं #चेहरा (अक्सर बाहरी चेहरा माना जाता है), और उस चेहरे की सीमा को दो भागों में विभाजित करना संभव है जैसे कि सभी 0-डिग्री कोने एक भाग पर दिखाई देते हैं, और सभी
यदि ग्राफ [[समतलीय ग्राफ]], निर्देशित एसाइक्लिक ग्राफ है, तो इसका उपयोग किया जा सकता है, और निम्नलिखित अतिरिक्त गुण भी प्रदर्शित करता है: सभी 0-निर्देशित ग्राफ # इंडिग्री और आउटडिग्री और सभी 0-निर्देशित ग्राफ # इंडिग्री और आउटडिग्री शीर्ष ग्राफ सिद्धांत की ही शब्दावली पर दिखाई देते हैं #चेहरा (अक्सर बाहरी चेहरा माना जाता है), और उस चेहरे की सीमा को दो भागों में विभाजित करना संभव है जैसे कि सभी 0-डिग्री कोने भाग पर दिखाई देते हैं, और सभी
0-आउटडिग्री शीर्ष दूसरे पर दिखाई देते हैं (अर्थात दो प्रकार के शीर्ष वैकल्पिक नहीं होते हैं)।
0-आउटडिग्री शीर्ष दूसरे पर दिखाई देते हैं (अर्थात दो प्रकार के शीर्ष वैकल्पिक नहीं होते हैं)।


अगर <math>G</math> इन गुणों को प्रदर्शित करता है, तो हम केवल ग्राफ़ को प्रीप्रोसेस कर सकते हैं
अगर <math>G</math> इन गुणों को प्रदर्शित करता है, तो हम केवल ग्राफ़ को प्रीप्रोसेस कर सकते हैं
<math>O(n)</math> केवल समय और भंडारण <math>O(\log{n})</math> प्रति शीर्ष अतिरिक्त बिट्स, उत्तर देना
<math>O(n)</math> केवल समय और भंडारण <math>O(\log{n})</math> प्रति शीर्ष अतिरिक्त बिट्स, उत्तर देना
शीर्षों के किसी भी जोड़े के लिए पहुंच योग्यता संबंधी प्रश्न <math>O(1)</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>, और उनके घटना किनारों को हटा दिया जाता है। प्रत्येक
पूरा हो जाने पर, <math>s</math> और <math>t</math>, और उनके घटना किनारों को हटा दिया जाता है। प्रत्येक
शेष शीर्ष मानों के साथ 2-आयामी लेबल संग्रहीत करता है <math>1</math> को <math>n</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>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> जो सख्ती से है
b_2</math>, और कम से कम घटक मौजूद है <math>a_1</math> या <math>a_2</math> जो सख्ती से है
से कम <math>b_1</math> या <math>b_2</math>, क्रमश।
से कम <math>b_1</math> या <math>b_2</math>, क्रमश।


Line 144: Line 144:
==संबंधित समस्याएँ==
==संबंधित समस्याएँ==


एक संबंधित समस्या कुछ संख्याओं के साथ रीचैबिलिटी प्रश्नों को हल करना है <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
  | last1 = Demetrescu | first1 = Camil
  | last2 = Thorup | first2 = Mikkel | author2-link = Mikkel Thorup
  | last2 = Thorup | first2 = Mikkel | author2-link = Mikkel Thorup
Line 161: Line 161:
  | location = Universite de Bordeaux  
  | location = Universite de Bordeaux  
  | url = https://tel.archives-ouvertes.fr/tel-01110316/document }}.</ref>
  | url = https://tel.archives-ouvertes.fr/tel-01110316/document }}.</ref>
रीचैबिलिटी प्रश्नों से संबंधित एक अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर रीचैबिलिटी संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] के लिए एक प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (ताकि इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।
गम्यता प्रश्नों से संबंधित अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर गम्यता संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] के लिए प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (ताकि इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।


== यह भी देखें ==
== यह भी देखें ==

Revision as of 09:36, 10 July 2023

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

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

परिभाषा

एक निर्देशित ग्राफ़ के लिए , वर्टेक्स सेट के साथ और किनारा सेट , गम्यता रिलेशन (गणित) का का सकर्मक समापन है , जिसका अर्थ है सभी क्रमित जोड़ियों का समुच्चय शीर्षों में से जिसके लिए शीर्षों का क्रम मौजूद है