गम्यता

ग्राफ सिद्धांत में, रीचैबिलिटी एक ग्राफ के भीतर एक वर्टेक्स (ग्राफ सिद्धांत) से दूसरे तक जाने की क्षमता को संदर्भित करती है। एक शिखर $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})$ में है $E$ सभी के लिए $1\leq i\leq k$. अगर $G$ निर्देशित अचक्रीय ग्राफ है, तो इसका रीचैबिलिटी संबंध आंशिक क्रम है; किसी भी आंशिक आदेश को इस तरह से परिभाषित किया जा सकता है, उदाहरण के लिए इसकी सकर्मक कमी के पहुंच योग्यता संबंध के रूप में। इसका एक उल्लेखनीय परिणाम यह है कि चूंकि आंशिक आदेश सममित-विरोधी हैं, यदि $s$ तक पहुँच सकते हैं $t$, तो हम उसे जानते हैं $t$ नहीं पहूंच सकता $s$. सहज रूप से, यदि हम यात्रा कर सकें $s$ को $t$ और वापस $s$, तब $G$ इसमें एक चक्र (ग्राफ़ सिद्धांत) शामिल होगा, जो इस बात का खंडन करता है कि यह चक्रीय है। अगर $G$ निर्देशित है, लेकिन चक्रीय नहीं है (अर्थात इसमें कम से कम एक चक्र शामिल है), तो इसका पहुंच योग्यता संबंध आंशिक आदेश के बजाय पूर्व आदेश के अनुरूप होगा।

एल्गोरिदम

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

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

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

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

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

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

समतलीय ग्राफ ़ निर्देशित ग्राफ़ के लिए, एक बहुत तेज़ विधि उपलब्ध है, जैसा कि 2004 में मिकेल थोरुप द्वारा वर्णित है। यह विधि एक समतलीय ग्राफ़ पर पहुंच योग्यता संबंधी प्रश्नों का उत्तर दे सकती है $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 में टी. कामेडा के कारण, पूर्व-प्रसंस्करण के लिए और भी तेज़ विधि,

यदि ग्राफ समतलीय ग्राफ, निर्देशित एसाइक्लिक ग्राफ है, तो इसका उपयोग किया जा सकता है, और निम्नलिखित अतिरिक्त गुण भी प्रदर्शित करता है: सभी 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)$ समय।

संबंधित समस्याएँ

एक संबंधित समस्या कुछ संख्याओं के साथ रीचैबिलिटी प्रश्नों को हल करना है $k$ शीर्ष विफलताओं का. उदाहरण के लिए: शीर्ष कर सकते हैं $u$ अभी भी शीर्ष पर पहुंचें $v$ भले ही शिखर $s_{1},s_{2},...,s_{k}$ विफल हो गए हैं और अब उपयोग नहीं किया जा सकता? एक समान समस्या शीर्ष विफलताओं या दोनों के मिश्रण के बजाय किनारे विफलताओं पर विचार कर सकती है। चौड़ाई-पहली खोज तकनीक ऐसे प्रश्नों पर भी उतनी ही अच्छी तरह काम करती है, लेकिन एक कुशल ओरेकल का निर्माण करना अधिक चुनौतीपूर्ण है। रीचैबिलिटी प्रश्नों से संबंधित एक अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर रीचैबिलिटी संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह कचरा संग्रहण (कंप्यूटर विज्ञान) के लिए एक प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (ताकि इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।

यह भी देखें

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