गम्यता: Difference between revisions

Revision as of 10:03, 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$ . पहुंच योग्यता से संबंधित अनुभागों की रूपरेखा इस प्रकार है।

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

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

प्रत्येक के लिए $G_{i}$ , तीन विभाजकों की पहचान की जाती है, जिन्हें हटाए जाने पर, ग्राफ़ को तीन घटकों में तोड़ देते हैं, जिनमें से प्रत्येक में अधिकतम होते हैं $1/2$ मूल के शीर्ष. जैसा $G_{i}$ विपरीत डिपाथ की दो परतों से बनाया गया है, प्रत्येक विभाजक में 2 डिपाथ तक हो सकते हैं, सभी विभाजकों पर कुल मिलाकर 6 डिपाथ हो सकते हैं। माना $S$ दीपपथों का यह सेट हो। इस बात का प्रमाण कि ऐसे विभाजक सदैव पाए जा सकते हैं, लिप्टन और टार्जन के समतल विभाजक प्रमेय से संबंधित है, और ये विभाजक रैखिक समय में स्थित हो सकते हैं।

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

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

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

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

कामेडा की विधि के लिए उपयुक्त डिग्राफ

s

और

t

जोड़ा गया.

कामेडा के एल्गोरिथ्म के चलने के बाद ऊपर जैसा ही ग्राफ, प्रत्येक शीर्ष के लिए डीएफएस लेबल दिखा रहा है

1975 में टी. कामेडा के कारण, पूर्व-प्रसंस्करण के लिए और भी तेज़ विधि है,^[7]

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

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

प्रीप्रोसेसिंग निम्नलिखित चरणों का पालन करती है। हम नया शीर्ष $s$ जोड़ते हैं जिसमें प्रत्येक 0-डिग्री शीर्ष पर किनारा है, और अन्य नया शीर्ष है $t$ प्रत्येक 0-आउटडिग्री शीर्ष से किनारों के साथ। ध्यान दें कि के गुण $G$ हमें समतलता बनाए रखते हुए ऐसा करने की अनुमति दें, अर्थात, इन परिवर्धन के बाद भी कोई किनारा क्रॉसिंग नहीं होगा। प्रत्येक शीर्ष के लिए हम ग्राफ़ की समतलता के क्रम में आसन्नताओं (आउट-किनारों) की सूची संग्रहीत करते हैं (उदाहरण के लिए, ग्राफ़ के एम्बेडिंग के संबंध में दक्षिणावर्त)। फिर हम काउंटर आरंभ करते हैं $i=n+1$ और डेप्थ-फर्स्ट ट्रैवर्सल प्रारंभ करें $s$ . इस ट्रैवर्सल के दौरान, प्रत्येक शीर्ष की आसन्न सूची को आवश्यकतानुसार बाएं से दाएं देखा जाता है। जैसे ही ट्रैवर्सल के स्टैक से कोने निकाले जाते हैं, उन्हें मान के साथ लेबल किया जाता है $i$ , और $i$ फिर घटाया जाता है. ध्यान दें कि $t$ सदैव मूल्य के साथ लेबल किया जाता है $n+1$ और $s$ सदैव इसके साथ लेबल किया जाता है $0$ . फिर गहराई-पहले ट्रैवर्सल को दोहराया जाता है, किन्तु इस बार प्रत्येक शीर्ष की आसन्न सूची को दाएं से बाएं ओर देखा जाता है।

पूरा हो जाने पर, $s$ और $t$ , और उनके घटना किनारों को हटा दिया जाता है। प्रत्येक शेष शीर्ष मानों के साथ 2-आयामी लेबल संग्रहीत करता है $1$ को $n$ . दो शीर्ष दिए गए हैं $u$ और $v$ , और उनके लेबल $L(u)=(a_{1},a_{2})$ और $L(v)=(b_{1},b_{2})$ , हम ऐसा कहते हैं $L(u)<L(v)$ यदि और केवल यदि $a_{1}\leq b_{1}$ , $a_{2}\leq b_{2}$ , और कम से कम घटक उपस्थित है $a_{1}$ या $a_{2}$ जो सख्ती से है से कम $b_{1}$ या $b_{2}$ , क्रमश।

इस विधि का मुख्य परिणाम तो यही बताता है $v$ से पहुंचा जा सकता है $u$ यदि व केवल $L(u)<L(v)$ जिसकी गणना आसानी से की जा सकती है $O(1)$ समय।

यह भी देखें

गैमॉइड
सेंट-कनेक्टिविटी|एसटी-कनेक्टिविटी

संदर्भ

↑ Skiena, Steven S. (2011), "15.5 Transitive Closure and Reduction", The Algorithm Design Manual (2nd ed.), Springer, pp. 495–497, ISBN 9781848000698.
↑ Cohn, Paul Moritz (2003), Basic Algebra: Groups, Rings, and Fields, Springer, p. 17, ISBN 9781852335878.
↑ Schmidt, Gunther (2010), Relational Mathematics, Encyclopedia of Mathematics and Its Applications, vol. 132, Cambridge University Press, p. 77, ISBN 9780521762687.
↑ Gersting, Judith L. (2006), Mathematical Structures for Computer Science (6th ed.), Macmillan, p. 519, ISBN 9780716768647.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Transitive closure of a directed graph", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 632–634, ISBN 0-262-03293-7.
↑ Thorup, Mikkel (2004), "Compact oracles for reachability and approximate distances in planar digraphs", Journal of the ACM, 51 (6): 993–1024, doi:10.1145/1039488.1039493, MR 2145261, S2CID 18864647.
↑ Kameda, T (1975), "On the vector representation of the reachability in planar directed graphs", Information Processing Letters, 3 (3): 75–77, doi:10.1016/0020-0190(75)90019-8.
↑ Demetrescu, Camil; Thorup, Mikkel; Chowdhury, Rezaul Alam; Ramachandran, Vijaya (2008), "Oracles for distances avoiding a failed node or link", SIAM Journal on Computing, 37 (5): 1299–1318, CiteSeerX 10.1.1.329.5435, doi:10.1137/S0097539705429847, MR 2386269.
↑ Halftermeyer, Pierre, Connectivity in Networks and Compact Labeling Schemes for Emergency Planning, Universite de Bordeaux.

[skiena-1] Skiena, Steven S. (2011), "15.5 Transitive Closure and Reduction", The Algorithm Design Manual (2nd ed.), Springer, pp. 495–497, ISBN 9781848000698.

[2] Cohn, Paul Moritz (2003), Basic Algebra: Groups, Rings, and Fields, Springer, p. 17, ISBN 9781852335878.

[3] Schmidt, Gunther (2010), Relational Mathematics, Encyclopedia of Mathematics and Its Applications, vol. 132, Cambridge University Press, p. 77, ISBN 9780521762687.

[4] Gersting, Judith L. (2006), Mathematical Structures for Computer Science (6th ed.), Macmillan, p. 519, ISBN 9780716768647.

[5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Transitive closure of a directed graph", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 632–634, ISBN 0-262-03293-7.

[6] Thorup, Mikkel (2004), "Compact oracles for reachability and approximate distances in planar digraphs", Journal of the ACM, 51 (6): 993–1024, doi:10.1145/1039488.1039493, MR 2145261, S2CID 18864647.

[7] Kameda, T (1975), "On the vector representation of the reachability in planar directed graphs", Information Processing Letters, 3 (3): 75–77, doi:10.1016/0020-0190(75)90019-8.

[8] Demetrescu, Camil; Thorup, Mikkel; Chowdhury, Rezaul Alam; Ramachandran, Vijaya (2008), "Oracles for distances avoiding a failed node or link", SIAM Journal on Computing, 37 (5): 1299–1318, CiteSeerX 10.1.1.329.5435, doi:10.1137/S0097539705429847, MR 2386269.

[9] Halftermeyer, Pierre, Connectivity in Networks and Compact Labeling Schemes for Emergency Planning, Universite de Bordeaux.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
 {{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>1 \leq i \leq k</math> के लिए <math>E</math> में है.<ref name="skiena">{{citation
   | last = Skiena | first = Steven S.
   | contribution = 15.5 Transitive Closure and Reduction
@@ Line 16: / Line 17: @@
   | url = https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA495
   | year = 2011}}.</ref>
-अगर <math>G</math> [[निर्देशित अचक्रीय ग्राफ]] है, तो इसका गम्यता संबंध आंशिक क्रम है; किसी भी [[आंशिक आदेश]] को इस तरह से परिभाषित किया जा सकता है, उदाहरण के लिए इसकी [[सकर्मक कमी]] के पहुंच योग्यता संबंध के रूप में।<ref>{{citation
+यदि <math>G</math> [[निर्देशित अचक्रीय ग्राफ]] है, तो इसका गम्यता संबंध आंशिक क्रम है; किसी भी [[आंशिक आदेश]] को इस तरह से परिभाषित किया जा सकता है, उदाहरण के लिए इसकी [[सकर्मक कमी]] के पहुंच योग्यता संबंध के रूप में।<ref>{{citation
   | last = Cohn | first = Paul Moritz
   | isbn = 9781852335878
@@ Line 23: / Line 26: @@
   | title = Basic Algebra: Groups, Rings, and Fields
   | 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
   | isbn = 9780521762687
@@ Line 34: / Line 36: @@
   | volume = 132
   | year = 2010}}.</ref>
 == एल्गोरिदम ==
@@ Line 48: / Line 49: @@
   | url = https://books.google.com/books?id=lvAo3AeJikQC&pg=PA519
   | year = 2006}}.</ref>
-यदि आप कई प्रश्न पूछ रहे होंगे, तो अधिक परिष्कृत विधि का उपयोग किया जा सकता है; विधि का सटीक चुनाव विश्लेषण किए जा रहे ग्राफ़ की प्रकृति पर निर्भर करता है। प्रीप्रोसेसिंग समय और कुछ अतिरिक्त भंडारण स्थान के बदले में, हम डेटा संरचना बना सकते हैं जो किसी भी जोड़े पर पहुंच योग्य प्रश्नों का उत्तर कम से कम समय में दे सकती है। <math>O(1)</math> समय। तीन अलग-अलग, तेजी से विशिष्ट स्थितियों के लिए तीन अलग-अलग एल्गोरिदम और डेटा संरचनाएं नीचे उल्लिखित हैं।
+यदि आप कई प्रश्न पूछ रहे होंगे, तो अधिक परिष्कृत विधि का उपयोग किया जा सकता है; विधि का स्पष्ट चुनाव विश्लेषण किए जा रहे ग्राफ़ की प्रकृति पर निर्भर करता है। प्रीप्रोसेसिंग समय और कुछ अतिरिक्त स्टोरेज स्थान के बदले में, हम डेटा संरचना बना सकते हैं जो किसी भी जोड़े पर पहुंच योग्य प्रश्नों का उत्तर कम से कम समय में दे सकती है। <math>O(1)</math> समय तीन अलग-अलग, तेजी से विशिष्ट स्थितियों के लिए तीन अलग-अलग एल्गोरिदम और डेटा संरचनाएं नीचे उल्लिखित हैं।
 === फ़्लॉइड-वॉर्शल एल्गोरिथम ===
-फ्लोयड-वॉर्शल एल्गोरिथ्म<ref>{{citation
+फ्लोयड-वॉर्शल एल्गोरिथ्म <ref>{{citation
   | last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen
   | last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson
@@ Line 65: / Line 67: @@
   | 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
   | last = Thorup | first = Mikkel | author-link = Mikkel Thorup
   | doi = 10.1145/1039488.1039493
@@ Line 78: / Line 80: @@
   | title = Compact oracles for reachability and approximate distances in planar digraphs
   | 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> दीपपथों का यह सेट हो। इस बात का प्रमाण कि ऐसे विभाजक सदैव पाए जा सकते हैं, लिप्टन और टार्जन के समतल विभाजक प्रमेय से संबंधित है, और ये विभाजक रैखिक समय में स्थित हो सकते हैं।
-प्रत्येक के लिए <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 \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</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 114: / Line 101: @@
 [[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
   | journal = [[Information Processing Letters]]
@@ Line 123: / Line 110: @@
   | year = 1975
   | doi=10.1016/0020-0190(75)90019-8}}.</ref>
-यदि ग्राफ [[समतलीय ग्राफ]], निर्देशित एसाइक्लिक ग्राफ है, तो इसका उपयोग किया जा सकता है, और निम्नलिखित अतिरिक्त गुण भी प्रदर्शित करता है: सभी 0-निर्देशित ग्राफ # इंडिग्री और आउटडिग्री और सभी 0-निर्देशित ग्राफ # इंडिग्री और आउटडिग्री शीर्ष ग्राफ सिद्धांत की ही शब्दावली पर दिखाई देते हैं #चेहरा (अक्सर बाहरी चेहरा माना जाता है), और उस चेहरे की सीमा को दो भागों में विभाजित करना संभव है जैसे कि सभी 0-डिग्री कोने भाग पर दिखाई देते हैं, और सभी
+यदि ग्राफ [[समतलीय ग्राफ]], निर्देशित एसाइक्लिक ग्राफ है, जिससे इसका उपयोग किया जा सकता है, और निम्नलिखित अतिरिक्त गुण भी प्रदर्शित करता है: सभी 0-निर्देशित ग्राफ इंडिग्री और आउटडिग्री और सभी 0-निर्देशित ग्राफ इंडिग्री और आउटडिग्री शीर्ष ग्राफ सिद्धांत की ही शब्दावली पर दिखाई देते हैं  (अधिकांशतः बाहरी चेहरा माना जाता है), और उस प्रतिरूप की सीमा को दो भागों में विभाजित करना संभव है जैसे कि सभी 0-डिग्री कोने भाग पर दिखाई देते हैं, और सभी 0-आउटडिग्री शीर्ष दूसरे पर दिखाई देते हैं (अर्थात दो प्रकार के शीर्ष वैकल्पिक नहीं होते हैं)।
--आउटडिग्री शीर्ष दूसरे पर दिखाई देते हैं (अर्थात दो प्रकार के शीर्ष वैकल्पिक नहीं होते हैं)।
-अगर <math>G</math> इन गुणों को प्रदर्शित करता है, तो हम केवल ग्राफ़ को प्रीप्रोसेस कर सकते हैं
+यदि <math>G</math> इन गुणों को प्रदर्शित करता है, तो हम केवल ग्राफ़ <math>O(n)</math> को प्रीप्रोसेस कर सकते हैं  केवल समय और स्टोरेज <math>O(\log{n})</math> प्रति शीर्ष अतिरिक्त बिट्स, उत्तर देता है शीर्षों के किसी भी जोड़े के लिए पहुंच योग्यता संबंधी प्रश्न <math>O(1)</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>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>v</math> से पहुंचा जा सकता है <math>u</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

Anonymous

Search

गम्यता: Difference between revisions

Namespaces

More

Page actions

Revision as of 10:03, 10 July 2023

Contents

परिभाषा