गम्यता: Difference between revisions

From Vigyanwiki
No edit summary
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>1 \leq i \leq k</math> के लिए <math>E</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>1 \leq i \leq k</math> के लिए <math>E</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 17: 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
Line 35: Line 33:
  | url = https://books.google.com/books?id=E4dREBTs5WsC&pg=PA559
  | url = https://books.google.com/books?id=E4dREBTs5WsC&pg=PA559
  | volume = 132
  | volume = 132
  | year = 2010}}.</ref>
  | year = 2010}}.</ref>                                                                                                                                                                                                                                                            


== एल्गोरिदम ==
== एल्गोरिदम ==
Line 71: 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 84: Line 82:
समग्र दृष्टिकोण प्रत्येक शीर्ष के साथ तथाकथित विभाजक पथों का अपेक्षाकृत छोटा सेट जोड़ना है जैसे कि शीर्ष से कोई भी पथ <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> का संकुचन है एक ही शीर्ष में. क्योंकि प्रत्येक द्विपथ अधिकतम दो निरंतर परतों में प्रकट होता है, और क्योंकि प्रत्येक <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> अतिरिक्त जानकारी प्रति शीर्ष पर संग्रहीत की जाती है। इस बिंदु से, ए पहुंच योग्यता के लिए लघुगणकीय समय क्वेरी प्रत्येक जोड़ी को देखने जितनी सरल है एक सामान्य, उपयुक्त के लिए लेबल की <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> प्रत्येक शीर्ष के लिए अतिरिक्त जानकारी संग्रहीत की गई थी।


=== कामेडा का एल्गोरिदम ===
=== कामेडा का एल्गोरिदम ===
Line 110: Line 108:
  | 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>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> समय सरलता से की जा सकती है ।
Line 124: Line 122:
==संबंधित समस्याएँ                                                                                                                                                                                  ==
==संबंधित समस्याएँ                                                                                                                                                                                  ==


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


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

Revision as of 10:25, 10 July 2023

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

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

परिभाषा

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