गम्यता

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