गम्यता: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 3: Line 3:
[[ग्राफ सिद्धांत]] में, '''गम्यता''' ग्राफ के अन्दर शीर्ष (ग्राफ सिद्धांत) से दूसरे तक जाने की क्षमता को संदर्भित करती है। शीर्ष <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> पहुँचती है ). अप्रत्यक्ष ग्राफ़ के जुड़े अवयवों को रैखिक समय में पहचाना जा सकता है। इस आलेख का शेष भाग [[निर्देशित ग्राफ]] में जोड़ीवार पहुंच योग्यता निर्धारित करने की अधिक कठिन समस्या पर केंद्रित है (जो, संयोग से, सममित होने की आवश्यकता नहीं है)।                                                                                                                                                                             


== परिभाषा ==
== परिभाषा ==
Line 35: Line 35:
  | year = 2010}}.</ref>                                                                                                                                                                                                                                                             
  | year = 2010}}.</ref>                                                                                                                                                                                                                                                             


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


यदि आपके पास बनाने के लिए केवल (या कुछ) प्रश्न हैं, तो अधिक जटिल डेटा संरचनाओं का उपयोग छोड़ना और वांछित जोड़ी की पहुंच की सीधे गणना करना अधिक कुशल हो सकता है। इसे चौड़ाई पहली खोज या [[पुनरावृत्तीय गहनता गहराई-पहली खोज]] जैसे एल्गोरिदम का उपयोग करके [[रैखिक समय]] में पूरा किया जा सकता है।<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:
  | year = 2006}}.</ref>
  | year = 2006}}.</ref>


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


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


फ्लोयड-वॉर्शल एल्गोरिथ्म <ref>{{citation
फ्लोयड-वॉर्शल एल्गोरिथ्म <ref>{{citation
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> सबसे व्यर्थ स्थिति में आवश्यकता है अंतरिक्ष. यह एल्गोरिदम पूरी तरह से पहुंच योग्यता में रुचि नहीं रखता है क्योंकि यह शीर्षों के सभी जोड़े के बीच सबसे छोटी पथ दूरी की भी गणना करता है। ऋणात्मक  चक्र वाले ग्राफ़ के लिए, सबसे छोटा पथ अपरिभाषित हो सकता है, किन्तु जोड़ियों के बीच पहुंच को अभी भी नोट किया जा सकता है।


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


[[ समतलीय ग्राफ | समतलीय ग्राफ]] निर्देशित ग्राफ़ के लिए, बहुत तेज़ विधि उपलब्ध है, जैसा कि 2004 में [[मिकेल थोरुप]] द्वारा वर्णित है।<ref>{{citation
[[ समतलीय ग्राफ | समतलीय ग्राफ]] निर्देशित ग्राफ़ के लिए, बहुत तेज़ विधि उपलब्ध है, जैसा कि 2004 में [[मिकेल थोरुप]] द्वारा वर्णित है।<ref>{{citation
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>. पहुंच योग्यता से संबंधित अनुभागों की रूपरेखा इस प्रकार है।
Line 87: Line 87:
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 से अधिक ऐसे ग्राफ़ नहीं)
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>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> दीपपथों का यह समुच्चय हो। इस बात का प्रमाण कि ऐसे विभाजक सदैव पाए जा सकते हैं, लिप्टन और टार्जन के समतल विभाजक प्रमेय से संबंधित है, और ये विभाजक रैखिक समय में स्थित हो सकते हैं।


प्रत्येक के लिए <math>Q \in S</math>, की निर्देशित प्रकृति <math>Q</math> पथ के आरंभ से अंत तक इसके शीर्षों का प्राकृतिक अनुक्रमण प्रदान करता है। प्रत्येक शीर्ष के लिए <math>v</math> में <math>G_i</math>, हम पहले शीर्ष का पता लगाते हैं <math>Q</math> द्वारा पहुंच योग्य <math>v</math>, और अंतिम शीर्ष <math>Q</math> जो <math>v</math> पहुँच जाता है . अर्थात हम देख रहे हैं कि कितनी जल्दी <math>Q</math> हम से प्राप्त कर सकते हैं <math>v</math>, और कितनी दूर हम <math>Q</math> अंदर रह सकते हैं और अभी भी वापस आएँ <math>v</math>. यह जानकारी संग्रहित की जाती है प्रत्येक <math>v</math>. फिर शीर्षों के किसी भी जोड़े के लिए <math>u</math> और <math>w</math>, <math>u</math> तक पहुँच सकते हैं <math>w</math> के जरिए <math>Q</math> यदि <math>u</math> से जुड़ता है <math>Q</math> से जल्दी <math>w</math> से <math>Q</math> जुड़ता है .
प्रत्येक के लिए <math>Q \in S</math>, की निर्देशित प्रकृति <math>Q</math> पथ के आरंभ से अंत तक इसके शीर्षों का प्राकृतिक अनुक्रमण प्रदान करता है। प्रत्येक शीर्ष के लिए <math>v</math> में <math>G_i</math>, हम पहले शीर्ष का पता लगाते हैं <math>Q</math> द्वारा पहुंच योग्य <math>v</math>, और अंतिम शीर्ष <math>Q</math> जो <math>v</math> पहुँच जाता है . अर्थात हम देख रहे हैं कि कितनी जल्दी <math>Q</math> हम से प्राप्त कर सकते हैं <math>v</math>, और कितनी दूर हम <math>Q</math> अंदर रह सकते हैं और अभी भी वापस आएँ <math>v</math>. यह जानकारी संग्रहित की जाती है प्रत्येक <math>v</math>. फिर शीर्षों के किसी भी जोड़े के लिए <math>u</math> और <math>w</math>, <math>u</math> तक पहुँच सकते हैं <math>w</math> के जरिए <math>Q</math> यदि <math>u</math> से जुड़ता है <math>Q</math> से जल्दी <math>w</math> से <math>Q</math> जुड़ता है .


प्रत्येक शीर्ष को रिकर्सन के प्रत्येक चरण के लिए उपरोक्त <math>G_0 \ldots, G_k</math> के रूप में लेबल किया गया है जो बनाता है . चूँकि इस पुनरावृत्ति में लघुगणकीय गहराई है, कुल <math>O(\log{n})</math> अतिरिक्त जानकारी प्रति शीर्ष पर संग्रहीत की जाती है। इस बिंदु से, ए पहुंच योग्यता के लिए लघुगणकीय समय क्वेरी प्रत्येक जोड़ी को देखने जितनी सरल है एक सामान्य, उपयुक्त के लिए लेबल की <math>Q</math>. फिर मूल पेपर को ट्यून करने का काम करता है क्वेरी समय नीचे तक <math>O(1)</math>. किया जाता है
प्रत्येक शीर्ष को रिकर्सन के प्रत्येक चरण के लिए उपरोक्त <math>G_0 \ldots, G_k</math> के रूप में लेबल किया गया है जो बनाता है . चूँकि इस पुनरावृत्ति में लघुगणकीय गहराई है, कुल <math>O(\log{n})</math> अतिरिक्त जानकारी प्रति शीर्ष पर संग्रहीत की जाती है। इस बिंदु से, a पहुंच योग्यता के लिए लघुगणकीय समय क्वेरी प्रत्येक जोड़ी को देखने जितनी सरल है एक सामान्य, उपयुक्त के लिए लेबल की <math>Q</math>. फिर मूल पेपर को ट्यून करने का कार्य  करता है क्वेरी समय नीचे तक <math>O(1)</math>. किया जाता है


इस पद्धति के विश्लेषण को संक्षेप में प्रस्तुत करने में, पहले लेयरिंग पर विचार करें शीर्षों को विभाजित करने का प्रयास करें ताकि प्रत्येक शीर्ष पर केवल विचार किया जा सके <math>O(1)</math> एल्गोरिदम का विभाजक चरण ग्राफ़ को घटकों में तोड़ देता है जो कि अधिकतम <math>1/2</math> हैं मूल ग्राफ़ का आकार, जिसके परिणामस्वरूप a लघुगणक पुनरावर्तन गहराई. प्रत्यावर्तन के प्रत्येक स्तर पर, केवल रैखिक कार्य विभाजकों के साथ-साथ उनके बीच संभावित कनेक्शन की पहचान करने की आवश्यकता है शीर्ष. समग्र परिणाम <math>O(n \log n)</math> है केवल प्रीप्रोसेसिंग समय के साथ <math>O(\log{n})</math> प्रत्येक शीर्ष के लिए अतिरिक्त जानकारी संग्रहीत की गई थी।
इस पद्धति के विश्लेषण को संक्षेप में प्रस्तुत करने में, पहले लेयरिंग पर विचार करें शीर्षों को विभाजित करने का प्रयास करें ताकि प्रत्येक शीर्ष पर केवल विचार किया जा सके <math>O(1)</math> एल्गोरिदम का विभाजक चरण ग्राफ़ को अवयव में तोड़ देता है जो कि अधिकतम <math>1/2</math> हैं मूल ग्राफ़ का आकार, जिसके परिणामस्वरूप a लघुगणक पुनरावर्तन गहराई. प्रत्यावर्तन के प्रत्येक स्तर पर, केवल रैखिक कार्य विभाजकों के साथ-साथ उनके बीच संभावित कनेक्शन की पहचान करने की आवश्यकता है शीर्ष. समग्र परिणाम <math>O(n \log n)</math> है केवल प्रीप्रोसेसिंग समय के साथ <math>O(\log{n})</math> प्रत्येक शीर्ष के लिए अतिरिक्त जानकारी संग्रहीत की गई थी।


=== कामेडा का एल्गोरिदम ===
=== कामेडा का एल्गोरिदम                                                             ===


[[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
  | last = Kameda | first = T  
  | last = Kameda | first = T  
  | journal = [[Information Processing Letters]]
  | journal = [[Information Processing Letters]]
Line 112: Line 112:
यदि <math>G</math> इन गुणों को प्रदर्शित करता है, तो हम केवल ग्राफ़ <math>O(n)</math> को प्रीप्रोसेस कर सकते हैं केवल समय और स्टोरेज <math>O(\log{n})</math> प्रति शीर्ष अतिरिक्त बिट्स, उत्तर देता है शीर्षों के किसी भी जोड़े के लिए पहुंच योग्यता संबंधी प्रश्न <math>O(1)</math> साधारण के साथ समय तुलना करती है।
यदि <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
पूरा हो जाने पर, <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>, है
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>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
Line 140: Line 141:
  | url = https://tel.archives-ouvertes.fr/tel-01110316/document }}.</ref> गम्यता प्रश्नों से संबंधित अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर गम्यता संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] के लिए प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (जिससे इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।
  | url = https://tel.archives-ouvertes.fr/tel-01110316/document }}.</ref> गम्यता प्रश्नों से संबंधित अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर गम्यता संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] के लिए प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (जिससे इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।


== यह भी देखें                                             ==
== यह भी देखें ==
* [[गैमॉइड]]
* [[गैमॉइड]]
* सेंट-कनेक्टिविटी
* सेंट-कनेक्टिविटी

Revision as of 21:38, 30 July 2023

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

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

परिभाषा

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