गम्यता

ग्राफ सिद्धांत में, गम्यता ग्राफ के अन्दर शीर्ष (ग्राफ सिद्धांत) से दूसरे तक जाने की क्षमता को संदर्भित करती है। शीर्ष $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$ में है.

यदि $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}$ विफल हो गए हैं और अब उपयोग नहीं किया जा सकता? समान समस्या शीर्ष विफलताओं या दोनों के मिश्रण के अतिरिक्त किनारे विफलताओं पर विचार कर सकती है। चौड़ाई-पहली खोज तकनीक ऐसे प्रश्नों पर भी उतनी ही अच्छी तरह काम करती है, किन्तु कुशल ओरेकल का निर्माण करना अधिक चुनौतीपूर्ण है। गम्यता प्रश्नों से संबंधित अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर गम्यता संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह कचरा संग्रहण (कंप्यूटर विज्ञान) के लिए प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (जिससे इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।

यह भी देखें

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