गम्यता: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 6: Line 6:


== परिभाषा ==
== परिभाषा ==
एक निर्देशित ग्राफ़ <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 80: Line 80:
  | 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>.
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> जुड़ता है .

Revision as of 10:44, 10 July 2023

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

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

परिभाषा

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

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

एल्गोरिदम

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

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

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

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

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

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

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

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

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

एक ग्राफ दिया गया , एल्गोरिथ्म इच्छानुसार शीर्ष से प्रारंभ होकर शीर्षों को परतों में व्यवस्थित करने से प्रारंभ होता है . परतों को पहले पिछले चरण से पहुंच योग्य सभी शीर्षों पर विचार करके वैकल्पिक चरणों में बनाया गया है (केवल से प्रारंभ करके)।