डायनमिक कनेक्टिविटी: Difference between revisions

Latest revision as of 12:49, 8 September 2023

कम्प्यूटिंग और ग्राफ़ सिद्धांत में डायनमिक कनेक्टिविटी संरचना एक डेटा संरचना है जो ग्राफ़ के संबद्ध घटकों के विषय में जानकारी को सक्रिय रूप से बनाए रखती है।

ग्राफ़ के शीर्षों का सेट V निश्चित होता है परन्तु किनारों का सेट E परिवर्तित हो सकता है। इस जटिलता में क्रम की तीन स्थितियां हैं:

किनारों को केवल ग्राफ़ में संबद्ध जाता है (इसे वृद्धिशील संबद्धता कहा जा सकता है);
किनारों को केवल ग्राफ़ से पृथक किया जाता है (इसे डिक्रीमेंटल संबद्धता कहा जा सकता है);
किनारों को या तो संबद्ध या पृथक किया जा सकता है (इसे पूर्ण रूप से से डायनमिक कनेक्टिविटी कहा जा सकता है)।

किसी किनारे के प्रत्येक जोड़/ पृथक करने के पश्चात डायनमिक कनेक्टिविटी संरचना को स्वयं को इस प्रकार से अनुकूलित करना चाहिए कि यह फॉर्म के प्रश्नों का त्वरित उत्तर दे सके कि क्या x और y के मध्य कोई मार्ग है? (समान रूप से: क्या शीर्ष x और y एक ही जुड़े हुए घटक से संबंधित हैं?)।

वृद्धिशील संबद्धता

यदि किनारों को केवल संबद्ध किया जा सकता है तो डायनमिक कनेक्टिविटी की समस्या को असंयुक्त-सेट डेटा संरचना द्वारा हल किया जा सकता है। प्रत्येक सेट एक जुड़े हुए घटक का प्रतिनिधित्व करता है जहाँ x और y के मध्य एक पथ है यदि वे एक ही सेट से संबंधित हों। प्रति संचालन परिशोधन विश्लेषण समय $\Theta (\alpha (n))$ है जहां n शीर्षों की संख्या है और α इनवर्स एकरमैन फ़ंक्शन है।^[1]^[2]

घटती संबद्धता

वह स्थिति जिसमें किनारों को केवल पृथक किया जा सकता है जिसे शिमोन भी और योसी शिलोच द्वारा हल किया गया था।^[3] यह संरचना तालिका का उपयोग करती है जो प्रत्येक शीर्ष के लिए उस घटक का नाम निर्दिष्ट करती है जिससे वह संबंधित है। इस प्रकार संबद्धता प्रश्नों में निरंतर समय लगता है। जब कोई किनारा हटा दिया जाता है तो तालिका को अद्यतन करना चुनौती है।

चक्रीय ग्राफ़ (फारेस्ट)

जब चक्रीय ग्राफ़ में u-v किनारे को हटा दिया जाता है तो उस किनारे वाला ट्री दो ट्री में विभक्त हो जाता है: उनमें से एक में u और दूसरे में v होता है। तालिका को निम्नलिखित उपाय से सामयिक किया जाता है।

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

चूँकि हम सदैव छोटे उप-घटक का नाम परिवर्तित करते हैं जहाँ डिलीट संचालन के लिए परिशोधन समय $O(\log(n))$ होता है।

सामान्य ग्राफ़

जब किसी सामान्य ग्राफ़ में एक किनारे को हटा दिया जाता है तो हम नहीं जानते कि उसका घटक एकल घटक (अन्य किनारों से जुड़ा हुआ) रहता है या दो घटकों में विभक्त हो जाता है। इसलिए हम दो प्रक्रियाओं का उपयोग करते हैं जो समानांतर (या इंटरलीव्ड प्रकार से) चलती हैं। प्रक्रिया A यह जाँचती है कि क्या किनारे का विलोपन एक घटक को विभक्त करता है और यदि ऐसा होता है तो दोनों प्रक्रियाएँ रुक जाती हैं। प्रक्रिया B यह जाँचती है कि क्या किनारा विलोपन उस घटक को विभक्त नहीं करता है जिससे वह संबंधित है और यदि ऐसा नहीं होता है तो दोनों प्रक्रियाएँ पुनः से रुक जाती हैं।

प्रक्रिया A: एसाइक्लिक-ग्राफ स्थिति के समान : दो उप-प्रक्रियाएं हैं जो पृथक किये गए किनारे के दोनों सिरों से स्कैन करती हैं। यदि उप-प्रक्रियाओं में से एक दूसरे छोर तक पहुंचने से पहले समाप्त हो जाती है, तो इसका मतलब है कि घटक दो उप-घटकों में विभक्त हो गया है, और छोटे उप-घटक का नाम पहले की तरह अपडेट किया गया है। इस प्रकार डिलीट संचालन के लिए परिशोधन समय पुनः $O(\log(n))$ है।

प्रक्रिया B: चौड़ाई-पहली खोज|चौड़ाई-पहली संरचना (BFS) का उपयोग करती है, जिसे निम्नानुसार आरंभ किया गया है। एक शीर्ष r चुना जाता है और BFS उससे प्रारम्भ होता है। स्तर 0 में एकमात्र शीर्ष r है। जड़ से दूरी i के सभी शीर्ष स्तर i में हैं। यदि G कनेक्ट नहीं है तो कुछ अनस्कैन वर्टेक्स v पर नया स्कैन आरम्भ किया जाता है एवं v को लेवल 1 में रखा जाता है और कृत्रिम किनारे v को रूट r से सम्बद्ध करता है; i से v की दूरी के सभी शीर्ष अब स्तर i+1 आदि में हैं। सभी जुड़े हुए घटकों को एक BFS संरचना में रखने के लिए कृत्रिम किनारों को प्रस्तुत किया गया है और केवल इस उद्देश्य के लिए उपयोग किया जाता है। स्पष्ट रूप से, कृत्रिम किनारों का उपयोग केवल प्रक्रिया बी में किया जाता है।

संरचना में निम्नलिखित गुण हैं। स्तर i, i>0 में एक शीर्ष v में केवल तीन प्रकार के किनारे होते हैं: पिछड़े किनारे जो इसे स्तर i−1 से जोड़ते हैं (कम से कम एक ऐसा किनारा होता है, जो कृत्रिम हो सकता है), स्थानीय किनारे जो इसे दूसरे से जोड़ते हैं स्तर I में किनारे (शून्य या अधिक ऐसे किनारे हैं), या आगे के किनारे जो इसे स्तर i+1 में किनारों से जोड़ते हैं (शून्य या अधिक ऐसे किनारे हैं)। इसलिए प्रत्येक शीर्ष v के लिए, हम किनारों के तीन सेट (पिछड़े, स्थानीय और आगे) बनाए रखते हैं।

जब कोई किनारा u-v हटा दिया जाता है, तो दो विकल्प होते हैं: या तो u और v एक ही स्तर पर होते हैं, या वे ऐसे स्तर में होते हैं जिनकी संख्या 1 से भिन्न होती है।

स्थिति 1: यू और वी दोनों समान स्तर पर हैं। इस स्थिति में, किनारा विलोपन घटकों को नहीं परिवर्तित सकता है। किनारे को बस यू और वी के स्थानीय किनारों के सेट से हटा दिया जाता है, और प्रक्रिया बी रुक जाती है (और इसलिए प्रक्रिया ए भी रुक जाती है)। हमारी BFS संरचना अभी भी वैध है।

स्थिति 2

u और v विभिन्न स्तरों पर हैं। व्यापकता की हानि के बिना मान लें कि u स्तर i−1 में है और v स्तर i में है; इसलिए किनारे को आगे (u) और पीछे (v) से हटा दिया जाना चाहिए।

स्थिति 2.1: यदि नया बैकवर्ड (v) रिक्त नहीं है तो घटक परिवर्तित नहीं हैं: अन्य किनारे हैं जो v को पीछे की ओर जोड़ते हैं। प्रक्रिया B रुक जाती है (और प्रक्रिया A भी रुक जाती है)।
स्थिति 2.2: यदि नया बैकवर्ड (v) रिक्त है तो v अब लेवल i−1 से सम्बद्ध नहीं है और इसलिए रूट से इसकी दूरी अब i नहीं है; यह कम से कम i+1 होना चाहिए। इसके अतिरिक्त v से जुड़े अन्य शीर्ष भी हो सकते हैं जिनकी मूल से दूरी विलोपन के परिणामस्वरूप बढ़ जाती है। अद्यतन दूरियों की गणना करने के लिए हम कतार Q का उपयोग करते हैं जिसमें प्रारंभ में केवल शीर्ष v होता है।

जबकि Q रिक्त नहीं है:

w:= डीक्यू (Q)
w को उसके स्तर (जैसे, j) से हटा दें, और उसे अगले स्तर (j+1) में डाल दें।
स्थानीय पड़ोसियों को अपडेट करें:
- लोकल(w) में प्रत्येक किनारे w−x के लिए इसे लोकल(x) से पृथक कियें और इसे आगे (x) में रखें।
- पिछड़ा(w):= स्थानीय(w)
अग्रिम पड़ोसियों को अपडेट करें:
- आगे (w) में प्रत्येक किनारे w-x के लिए इसे पीछे (x) से हटा दें और इसे स्थानीय (x) में डालें; यदि नया बैकवर्ड (x) रिक्त है तो x को Q पर पंक्तिबद्ध करें।
- स्थानीय(w):= आगे(w)
- आगे(w):= रिक्त सेट
यदि नया बैकवर्ड (w) रिक्त है तो Q पर पुनः से w कतार में लगाएं।

यदि किनारे पृथक करने से कोई घटक नहीं टूटता है और हम स्थिति 2.2 में हों तो अंततः प्रक्रिया रुक जाएगी। इस स्थिति में यह देखना सरल है कि BFS संरचना सही प्रकार से बनाए रखी गई है। यदि इसके विलोपन से कोई घटक विभक्त हो जाता है तो प्रक्रिया अपने आप नहीं रुकेगी। जबकि प्रक्रिया A ब्रेक को पहचानते हुए रुक जाएगी और दोनों प्रक्रियाएँ रुक जाएँगी। इस स्थिति में BFS संरचना में किए गए सभी परिवर्तनों की अवहेलना कर देता है और हम उस BFS संरचना पर वापस चले जाते हैं जो हमारे पास विलोपन से ठीक पहले थी सिवाय इसके कि पृथक किये गए किनारे को अब कृत्रिम किनारे से परिवर्तित दिया गया है। स्पष्ट रूप से इस स्थिति में v अब ट्री की जड़ है जिसमें कुछ अन्य कृत्रिम किनारों के माध्यम से नया घटक और संभवतः अतिरिक्त घटक सम्मिलित हैं। साथ ही $v$ के वंशजों को जोड़ने वाला कोई किनारा नहीं है।

$v$ के वंशज जो कृत्रिम किनारे $u-v$ ^[4] को छोड़कर किसी भी शीर्ष के साथ नहीं है।

जब भी प्रक्रिया में किसी किनारे को संसाधित किया जाता है तो उसका समापन बिंदु एक स्तर तक गिर जाता है। चूंकि प्रक्रिया B द्वारा समाप्त किए गए संचालनों में शीर्ष तक पहुंचने वाला निम्नतम स्तर $|V|-1$ है एवं प्रति किनारा लागत $2|V|$ सीमाबद्ध है इसलिए प्रति विलोपन कार्रवाई में परिशोधन समय $O(n)$ है।

पूर्ण रूप से डायनमिक कनेक्टिविटी

चक्रीय ग्राफ़ (फारेस्ट)

किसी फ़ॉरेस्ट को लिंक-कट ट्री या यूलर टूर ट्री के संग्रह का उपयोग करके दर्शाया जा सकता है। तब डायनमिक कनेक्टिविटी समस्या को सरलता से हल किया जा सकता है क्योंकि प्रत्येक दो नोड्स के लिए x,y, x, y से जुड़ा होता है यदि और केवल यदि FindRoot(x)=FindRoot(y)। परिशोधित अद्यतन समय और क्वेरी समय दोनों O(log(n)) हैं।

सामान्य ग्राफ़

सामान्य ग्राफ़ को उसके फैले हुए फ़ॉरेस्ट द्वारा दर्शाया जा सकता है - एक फ़ॉरेस्ट जिसमें ग्राफ़ के प्रत्येक जुड़े घटक के लिए ट्री होता है। हम इस फैले हुए फ़ॉरेस्ट को F कहते हैं। F को यूलर टूर ट्री के फ़ॉरेस्ट द्वारा दर्शाया जा सकता है।

क्वेरी और इंसर्ट संचालनों को F का प्रतिनिधित्व करने वाले ET ट्री पर संबंधित संचालनों का उपयोग करके कार्यान्वित किया जाता है। चुनौतीपूर्ण संचालन डिलीट है और विशेष रूप से एक किनारे को हटाना जो F के स्पैनिंग ट्री में से एक में निहित है। यह स्पैनिंग ट्री को दो में विभक्त कर देता है लेकिन यह संभव है कि कोई और किनारा हो जो उन्हें सम्बद्ध करता हो। चुनौती यह है कि यदि ऐसा कोई प्रतिस्थापन किनारा उपस्थित है तो उसे तुरंत खोजा जाए। इसके लिए अधिक जटिल डेटा संरचना की आवश्यकता होती है। ऐसी कई संरचनाओं का वर्णन नीचे किया गया है।

स्तर संरचना

ग्राफ़ में प्रत्येक किनारे को एक स्तर तक निर्दिष्ट किया गया है। माना L=lg n ग्राफ़ में डाले गए प्रत्येक किनारे का स्तर L से प्रारंभ किया गया है और डिलीट संचालन के समय 0 तक घट सकता है।

0 और L के मध्य प्रत्येक i के लिए Gi को उस सबग्राफ के रूप में परिभाषित करें जिसमें किनारों का स्तर i या उससे कम है और Fi Gi का फैला हुआ फ़ॉरेस्ट है। हमारा पहले का फ़ॉरेस्ट F अब FL कहलाता है। हम वनों का घटता क्रम FL ⊇ ... ⊇ F0 रखेंगे।^[5]^[6]

परिचालन

क्वेरी और इंसर्ट संचालन केवल सबसे बड़े फ़ॉरेस्ट FL का उपयोग करते हैं। छोटे सबग्राफ से केवल डिलीट संचालन के समय सलाह ली जाती है और विशेष रूप से उस किनारे को हटाना जो FL के फैले हुए ट्री में से एक में निहित है।

जब इस प्रकार के किनारे e = x−y को हटा दिया जाता है तो इसे सबसे पहले FL से और उन सभी छोटे फैले हुए फ़ॉरेस्टों से हटा दिया जाता है अर्थात i ≥ स्तर (e) वाले प्रत्येक Fi से। पुनः हम प्रतिस्थापन किनारे की खोज करते हैं।

सबसे छोटे फैले फ़ॉरेस्ट से प्रारम्भ करें जिसमें e, अर्थात् Fi के साथ i = स्तर (e) सम्मिलित है। किनारा e एक निश्चित ट्री T⊆Fi से संबंधित है। e को पृथक करने के बाद ट्री T दो छोटे ट्री में विभक्त हो जाता है: Tx जिसमें नोड x होता है और Ty जिसमें नोड y होता है। Gi का किनारा प्रतिस्थापन किनारा होता है यदि और केवल यदि यह Tx में नोड को Ty में नोड से सम्बद्ध करता है। मान लीजिए कि Tx छोटा ट्री है (अर्थात इसमें टी के अधिकतम आधे नोड होते हैं; हम यूलर ट्री में जोड़े गए एनोटेशन द्वारा प्रत्येक उपट्री का आकार बता सकते हैं)।

हम पहले Tx के प्रत्येक किनारे के स्तर को 1 से कम करते हैं। पुनः हम सभी किनारों ε पर स्तर i और Tx में कम से कम एक नोड के साथ लूप करते हैं:

यदि ε का दूसरा नोड Ty में है तो एक प्रतिस्थापन किनारा मिल जाता है! इस किनारे को Fi और FL तक के सभी वनों में जोड़ें, और समाप्त करें। फैले हुए फ़ॉरेस्ट निश्चित हैं। ध्यान दें कि इस खोज के लिए भुगतान करने के लिए हम खोज के समय देखे गए किनारों के स्तर को कम कर देते हैं।
यदि ε का दूसरा नोड Tx में है तो यह प्रतिस्थापन किनारा नहीं है और हमारा समय नष्ट करने के परिणामस्वरूप हम इसके स्तर को 1 से कम कर देते हैं।

विश्लेषण

प्रत्येक किनारे का स्तर अधिकतम lg n बार कम हो जाएगा। क्यों? क्योंकि प्रत्येक कमी के साथ यह ऐसे ट्री में गिरता है जिसका आकार पिछले स्तर में इसके ट्री के आकार का अधिकतम आधा होता है। इसलिए प्रत्येक स्तर i में प्रत्येक जुड़े घटक में नोड्स की संख्या अधिकतम 2ⁱ है इसलिए किनारे का स्तर सदैव कम से कम 0 होता है।

प्रत्येक किनारा जिसका स्तर कम हो जाता है एवं खोजने का समय (ईटी ट्री संचालनों का उपयोग करके) $O(\lg n)$ मानते है। कुल मिलाकर प्रत्येक सम्मिलित किनारा इसे पृथक किये जाने तक का समय $O(\lg ^{2}n)$ लेता है इसलिए पृथक करने के लिए परिशोधन समय $O(\lg ^{2}n)$ है एवं डिलीट का शेष भाग $O(\lg ^{2}n)$ समय भी लेता है चूँकि हमें अधिक से अधिक $O(\lg n)$ स्तर किनारे को हटाना है और प्रत्येक स्तर से पृथक करने में $O(\lg n)$ (पुनः से ईटी संचालनों का उपयोग करके) लगता है।

कुल मिलाकर प्रति अद्यतन परिशोधन समय $O(\lg ^{2}n)$ है एवं प्रति प्रश्न समय में सुधार $O(\lg n/\lg \lg n)$ किया जा सकता है।

जबकि प्रति अद्यतन सबसे दोषपूर्ण स्थिति वाला समय $O(n)$ हो सकता है एवं यह प्रश्न कि क्या सबसे दोषपूर्ण स्थिति में सुधार किया जा सकता है यह एक खुला प्रश्न था जब तक कि इसे कटसेट संरचना द्वारा सकारात्मक रूप से हल नहीं किया गया था।

कटसेट संरचना

ग्राफ G(V,E) और उपसमुच्चय T⊆V को देखते हुए Cutset(T) को किनारों के सेट के रूप में परिभाषित करते हैं जो T को V\T से जोड़ते हैं। कटसेट संरचना डेटा संरचना है जो पूरे ग्राफ़ को मेमोरी में रखे बिना कटसेट में तुरंत किनारा खोज सकती है यदि ऐसा कोई किनारा उपस्थित होता है। ^[7]

प्रत्येक शीर्ष को एक संख्या देकर प्रारंभ करें। मान लीजिए कि n शीर्ष हैं; पुनः प्रत्येक शीर्ष को lg(n) बिट्स वाली एक संख्या द्वारा दर्शाया जा सकता है। इसके पश्चात प्रत्येक किनारे को एक संख्या दें जो इसके शीर्षों की संख्याओं का संयोजन - 2 lg(n) बिट्स वाली एक संख्या है।

प्रत्येक शीर्ष v के लिए xor(v) की गणना करें और रखें जो कि उसके निकटवर्ती सभी किनारों की संख्याओं का xor है।

अब प्रत्येक उपसमुच्चय T⊆V के लिए 'xor(T)' = T में सभी शीर्षों के मानों के xor की गणना करना संभव है। किनारे e = u−v पर विचार करें जो T का आंतरिक किनारा है (अर्थात दोनों u और v T में हैं)। e की संख्या को xor(T) में दो बार सम्मिलित किया गया है - एक बार u के लिए और एक बार v के लिए। चूँकि प्रत्येक संख्या का xor स्वयं 0 है तथा e गायब हो जाता है और xor(T) को प्रभावित नहीं करता है। इस प्रकार xor(T) वास्तव में कटसेट(T) में सभी किनारों का xor है। कई विकल्प हैं:

यदि xor(T)=0, तो हम आत्मविश्वास से उत्तर दे सकते हैं कि कटसेट(T) रिक्त है।
यदि xor(T) वास्तविक किनारे e की संख्या है तो संभवतः कटसेट(T) में e ही एकमात्र किनारा है, और हम e वापस कर सकते हैं। हम ई की संख्या से ई के अंतिम बिंदुओं को एलजी (एन) सबसे बाएं बिट्स और एलजी (एन) सबसे दाएं बिट्स में विभाजित करके भी पढ़ सकते हैं।
तीसरा विकल्प यह है कि xor(T) एक गैर-शून्य संख्या है जो वास्तविक किनारे का प्रतिनिधित्व नहीं करती है। यह केवल तभी हो सकता है जब कटसेट (T) में दो या दो से अधिक किनारे हों, क्योंकि उस स्थिति में xor(T) कई संख्या में किनारों का xor है। इस मामले में, हम विफलता की रिपोर्ट करते हैं, क्योंकि हम जानते हैं कि कटसेट में किनारे हैं लेकिन किसी एक किनारे की पहचान नहीं कर सकते हैं। ^[8]

अब हमारा लक्ष्य इस तीसरे विकल्प को संभालना है।

सबसे पहले कटसेट संरचनाओं के lg (n) स्तरों का एक अनुक्रम बनाएं जिनमें से प्रत्येक में ऊपरी स्तर से लगभग आधे किनारे होते हैं (अर्थात प्रत्येक स्तर के लिए संभावना 1/2 के साथ ऊपरी स्तर से प्रत्येक किनारे को चुनें)। यदि पहले स्तर में xor(T) एक अवैध मान लौटाता है जिसका अर्थ है कि कटसेट(T) में दो या दो से अधिक किनारे हैं तो संभावना है कि अगले स्तर में जिसमें कम किनारे हैं, xor(T) वैध मान लौटाएगा क्योंकि कटसेट(T) में एक ही किनारा होगा। यदि xor(T) अभी भी अवैध मान लौटाता है तो अगले स्तर पर जारी रखें, आदि। चूंकि किनारों की संख्या कम हो रही है इसलिए दो स्थितियां हैं:

अनुकूल स्थिति यह है कि अंततः हमें एक ऐसा स्तर प्राप्त हो जाता है जिसमें कटसेट(टी) में एक ही किनारा होता है; पुनः हम उस किनारे को लौटाते हैं और समाप्त करते हैं।
बुरी स्थिति यह है कि अंततः हमें एक ऐसा स्तर मिलता है जिसमें कटसेट(टी) में कोई किनारा नहीं होता है तब हम विफलता की रिपोर्ट करते हैं क्योंकि हम जानते हैं कि कटसेट में किनारे हैं लेकिन किसी एक किनारे की पहचान नहीं कर सकते हैं।

यह सिद्ध करना संभव है कि सफलता की संभावना कम से कम 1/9 है।

इसके पश्चात स्तर संरचना के स्वतंत्र संस्करणों C lg(n) का एक संग्रह बनाएं जहां C एक स्थिरांक है। प्रत्येक संस्करण में स्तर से स्तर तक किनारों की एक स्वतंत्र यादृच्छिक कमी करें। प्रत्येक संस्करण पर प्रत्येक क्वेरी का प्रयास करें जब तक कि उनमें से कोई एक सफल न हो जाए। सभी संस्करणों के विफल होने की संभावना अधिकतम है:

(1-1/9)^{C\lg {n}}=2^{-0.17C\lg {n}}=n^{-0.17C}

C के उचित चयन से हम विफलता की संभावना को मनमाने ढंग से 0 के निकट बना सकते हैं।

परिचालन

हम एक डायनमिक कनेक्टिविटी संरचना में कटसेट संरचना जोड़ सकते हैं।

कटसेट संरचना पर इन्सर्ट और डिलीट संचालन बिल्कुल उसी प्रकार से किए जाते हैं: डाले गए /पृथक किये गए किनारे को इसके दोनों एंडपॉइंट्स में XORed किया जाता है।

जब डायनमिक कनेक्टिविटी संरचना के लिए उपयोग किए जाने वाले स्पैनिंग फ़ॉरेस्ट से एक किनारे को हटा दिया जाता है तो प्रतिस्थापन किनारे को खोजने के लिए कटसेट संरचना का उपयोग किया जाता है।

विश्लेषण

एकल कटसेट संरचना के लिए केवल O(n lg n) मेमोरी की आवश्यकता होती है - प्रत्येक n शीर्ष के लिए 2 lg n बिट्स के साथ केवल एक संख्या। हमें किनारों को स्वयं नहीं रखना है। घने ग्राफ़ के लिए, यह पूरे ग्राफ़ को मेमोरी में रखने की तुलना में अधिक सस्ता है।

हमें lg(n) संस्करण रखना होगा जिनमें से प्रत्येक में lg(n) स्तर होंगे। इसलिए कुल मेमोरी आवश्यकता $O(n\lg ^{3}n)$ है।

सबसे खराब स्थिति में क्वेरी का समय O(polylog(n)) है। यह डायनामिक संबद्धता, लेवल संरचना के विपरीत है जिसमें क्वेरी का समय O(polylog(n)) परिशोधित है लेकिन सबसे खराब स्थिति का समय O(n) है।

ऑफ़लाइन डायनमिक कनेक्टिविटी

यदि किनारों को जिस क्रम में पृथक किया जाएगा वह समय से पहले ज्ञात है, तो हम प्रति क्वेरी लॉग (एन) में डायनमिक कनेक्टिविटी समस्या को हल कर सकते हैं। यदि हम एक अधिकतम फैले हुए वन को बनाए रख सकते हैं जहां किनारों को उनके विलोपन समय के अनुसार क्रमबद्ध किया जाता है, तो हम जानते हैं कि जब हम फ़ॉरेस्ट में उपस्थित कुछ किनारों को हटाते हैं, तो कोई संभावित किनारा नहीं है जो इसे प्रतिस्थापित कर सके। यदि कोई किनारा होता जो पृथक किये गए किनारे के समान दो घटकों को सम्बद्ध करता है, तो यह दूसरा किनारा हमारे द्वारा पृथक किये गए किनारे के स्थान पर अधिकतम फैले हुए फ़ॉरेस्ट का भाग होता। यह डिलीट संचालन को तुच्छ बना देता है: यदि डिलीट किया जाने वाला किनारा हमारे फ़ॉरेस्ट का भाग है तो हमें बस ट्री को उसके दो भागों में विभाजित करना होगा या अन्यथा संचालन को अनदेखा करना होगा।

किनारों को सम्बद्ध करना थोड़ा अधिक जटिल है। यदि हम u से v तक एक किनारा किनारा e जोड़ते हैं तो यदि u और v जुड़े नहीं हैं तो यह किनारा अधिकतम स्पैनिंग फ़ॉरेस्ट का भाग होगा। यदि वे जुड़े हुए हैं तो हम अपने फ़ॉरेस्ट में u->v सम्बद्ध करना चाहते हैं यदि यह हमारे अधिकतम फैले हुए फ़ॉरेस्ट में सुधार कर सकता है। ऐसा करने के लिए, हमें तुरंत यह जांचने की आवश्यकता है कि यू से वी तक के पथ पर किस किनारे को पृथक करने का समय सबसे कम है। यदि इस किनारे को पृथक करने का समय E के पृथक करने के समय के बाद आता है, तो ई हमारे अधिकतम फैले हुए फ़ॉरेस्ट में सुधार नहीं कर सकता है। अन्यथा, दूसरे किनारे को हटा दिया जाना चाहिए और उसे ई से परिवर्तित दिया जाना चाहिए।

इसके लिए हमें निम्नलिखित संचालन करने की आवश्यकता है: एक किनारा जोड़ें, एक किनारा काटें और पथ पर न्यूनतम किनारे की क्वेरी करें जिसे प्रति संचालन log(n) में लिंक-कट ट्री के साथ सरलता से किया जा सकता है।

यह भी देखें

गतिशील समस्या (एल्गोरिदम)
विभाजन शोधन

संदर्भ

↑ Tarjan, Robert Endre (1975). "एक अच्छे लेकिन रैखिक सेट यूनियन एल्गोरिदम की दक्षता". Journal of the ACM. 22 (2): 215–225. CiteSeerX 10.1.1.399.6704. doi:10.1145/321879.321884. S2CID 11105749.
↑ Tarjan, Robert Endre (1979). "एल्गोरिदम का एक वर्ग जिसे असंयुक्त सेटों को बनाए रखने के लिए गैर-रेखीय समय की आवश्यकता होती है". Journal of Computer and System Sciences. 18 (2): 110–127. doi:10.1016/0022-0000(79)90042-4.
↑ Shiloach, Y.; Even, S. (1981). "एक ऑन-लाइन एज-डिलीशन समस्या". Journal of the ACM. 28: 1–4. doi:10.1145/322234.322235. S2CID 207746822.
↑ One way to realize the return to the structure preceding the deletion of e without having to copy the whole structure is to keep on a stack all the changes that took place in the BFS structure since the deletion of e and undo them one by one. This way the processing time is only multiplied by a constant.
↑ Holm, J.; De Lichtenberg, K.; Thorup, M. (2001). "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity". Journal of the ACM. 48 (4): 723. doi:10.1145/502090.502095. S2CID 7273552.
↑ Dynamic Graph Problems - in Lecture Notes in Advanced Data Structures. Prof. Erik Demaine; Scribe: Katherine Lai.
↑ Kapron, B. M.; King, V.; Mountjoy, B. (2013). पॉलीलॉगरिदमिक सबसे खराब स्थिति में गतिशील ग्राफ़ कनेक्टिविटी. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1131. doi:10.1137/1.9781611973105.81. ISBN 978-1-61197-251-1.
↑ There is a small probability that the xor of several different edges will result in a number which happens to be the number of another edge. This might lead to a false positive. In order to reduce the probability of this event, we can enlarge the domain of the numbers of vertices to, say, n³ instead of n. Then, if there is more than one edge in cutset(T), xor(T) will almost certainly be a meaningless value, as stated above.

See also: Thorup, M. (2000). Near-optimal fully-dynamic graph connectivity. Proceedings of the thirty-second annual ACM symposium on Theory of computing - STOC '00. p. 343. doi:10.1145/335305.335345. ISBN 1581131844.

[tarjan1975-1] Tarjan, Robert Endre (1975). "एक अच्छे लेकिन रैखिक सेट यूनियन एल्गोरिदम की दक्षता". Journal of the ACM. 22 (2): 215–225. CiteSeerX 10.1.1.399.6704. doi:10.1145/321879.321884. S2CID 11105749.

[Tarjan1979-2] Tarjan, Robert Endre (1979). "एल्गोरिदम का एक वर्ग जिसे असंयुक्त सेटों को बनाए रखने के लिए गैर-रेखीय समय की आवश्यकता होती है". Journal of Computer and System Sciences. 18 (2): 110–127. doi:10.1016/0022-0000(79)90042-4.

[3] Shiloach, Y.; Even, S. (1981). "एक ऑन-लाइन एज-डिलीशन समस्या". Journal of the ACM. 28: 1–4. doi:10.1145/322234.322235. S2CID 207746822.

[4] One way to realize the return to the structure preceding the deletion of e without having to copy the whole structure is to keep on a stack all the changes that took place in the BFS structure since the deletion of e and undo them one by one. This way the processing time is only multiplied by a constant.

[5] Holm, J.; De Lichtenberg, K.; Thorup, M. (2001). "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity". Journal of the ACM. 48 (4): 723. doi:10.1145/502090.502095. S2CID 7273552.

[6] Dynamic Graph Problems - in Lecture Notes in Advanced Data Structures. Prof. Erik Demaine; Scribe: Katherine Lai.

[7] Kapron, B. M.; King, V.; Mountjoy, B. (2013). पॉलीलॉगरिदमिक सबसे खराब स्थिति में गतिशील ग्राफ़ कनेक्टिविटी. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1131. doi:10.1137/1.9781611973105.81. ISBN 978-1-61197-251-1.

[8] There is a small probability that the xor of several different edges will result in a number which happens to be the number of another edge. This might lead to a false positive. In order to reduce the probability of this event, we can enlarge the domain of the numbers of vertices to, say, n³ instead of n. Then, if there is more than one edge in cutset(T), xor(T) will almost certainly be a meaningless value, as stated above.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
-[[ कम्प्यूटिंग ]] और ग्राफ़ सिद्धांत में, एक गतिशील कनेक्टिविटी संरचना एक डेटा संरचना है जो ग्राफ़ के जुड़े घटकों के बारे में जानकारी को गतिशील रूप से बनाए रखती है।
+[[ कम्प्यूटिंग |कम्प्यूटिंग]] और ग्राफ़ सिद्धांत में '''डायनमिक कनेक्टिविटी''' संरचना एक डेटा संरचना है जो ग्राफ़ के संबद्ध घटकों के विषय में जानकारी को सक्रिय रूप से बनाए रखती है।
-ग्राफ़ के शीर्षों का सेट ''V'' निश्चित है, लेकिन किनारों का सेट ''E'' बदल सकता है। कठिनाई के क्रम में तीन मामले हैं:
+ग्राफ़ के शीर्षों का सेट ''V'' निश्चित होता है परन्तु किनारों का सेट ''E'' परिवर्तित हो सकता है। इस जटिलता में क्रम की तीन स्थितियां हैं:
-* किनारों को केवल ग्राफ़ में जोड़ा जाता है (इसे ''वृद्धिशील कनेक्टिविटी'' कहा जा सकता है);
+* किनारों को केवल ग्राफ़ में संबद्ध जाता है (इसे ''वृद्धिशील संबद्धता'' कहा जा सकता है);
-* किनारों को केवल ग्राफ़ से हटाया जाता है (इसे ''डिक्रीमेंटल कनेक्टिविटी'' कहा जा सकता है);
+* किनारों को केवल ग्राफ़ से पृथक किया जाता है (इसे ''डिक्रीमेंटल संबद्धता'' कहा जा सकता है);
-* किनारों को या तो जोड़ा या हटाया जा सकता है (इसे ''पूरी तरह से गतिशील कनेक्टिविटी'' कहा जा सकता है)।
+* किनारों को या तो संबद्ध या पृथक किया जा सकता है (इसे ''पूर्ण रूप से से डायनमिक कनेक्टिविटी'' कहा जा सकता है)।
-किसी किनारे के प्रत्येक जोड़/हटाने के बाद, गतिशील कनेक्टिविटी संरचना को खुद को इस तरह से अनुकूलित करना चाहिए कि यह फॉर्म के प्रश्नों का त्वरित उत्तर दे सके कि क्या ''x'' और ''y'' के बीच कोई रास्ता है? (समान रूप से: क्या शीर्ष ''x'' और ''y'' एक ही जुड़े हुए घटक से संबंधित हैं?)।
+किसी किनारे के प्रत्येक जोड़/ पृथक करने के पश्चात डायनमिक कनेक्टिविटी संरचना को स्वयं को इस प्रकार से अनुकूलित करना चाहिए कि यह फॉर्म के प्रश्नों का त्वरित उत्तर दे सके कि क्या ''x'' और ''y'' के मध्य कोई मार्ग है? (समान रूप से: क्या शीर्ष ''x'' और ''y'' एक ही जुड़े हुए घटक से संबंधित हैं?)।
-== वृद्धिशील कनेक्टिविटी ==
+== वृद्धिशील संबद्धता ==
-यदि किनारों को केवल जोड़ा जा सकता है, तो गतिशील कनेक्टिविटी समस्या को [[असंयुक्त-सेट डेटा संरचना]] द्वारा हल किया जा सकता है। प्रत्येक सेट एक जुड़े हुए घटक का प्रतिनिधित्व करता है; x और y के बीच एक पथ है यदि और केवल यदि वे एक ही सेट से संबंधित हों। प्रति ऑपरेशन [[परिशोधन विश्लेषण]] समय है <math>\Theta(\alpha(n))</math>, जहां n शीर्षों की संख्या है और α एकरमैन फ़ंक्शन#इनवर्स है।<ref name="tarjan1975">{{cite journal |last1=Tarjan |first1=Robert Endre |author1-link=Robert E. Tarjan |year=1975 |title=एक अच्छे लेकिन रैखिक सेट यूनियन एल्गोरिदम की दक्षता|journal=Journal of the ACM |volume=22 |issue=2 |pages=215&ndash;225 |doi=10.1145/321879.321884 |citeseerx=10.1.1.399.6704 |s2cid=11105749 }}</ref><ref name="Tarjan1979">{{cite journal |first=Robert Endre |last=Tarjan |authorlink=Robert E. Tarjan |year=1979 |title=एल्गोरिदम का एक वर्ग जिसे असंयुक्त सेटों को बनाए रखने के लिए गैर-रेखीय समय की आवश्यकता होती है|journal=Journal of Computer and System Sciences |volume=18 |issue=2 |pages=110&ndash;127 |doi=10.1016/0022-0000(79)90042-4|doi-access=free }}</ref>
+यदि किनारों को केवल संबद्ध किया जा सकता है तो डायनमिक कनेक्टिविटी की समस्या को [[असंयुक्त-सेट डेटा संरचना]] द्वारा हल किया जा सकता है। प्रत्येक सेट एक जुड़े हुए घटक का प्रतिनिधित्व करता है जहाँ x और y के मध्य एक पथ है यदि वे एक ही सेट से संबंधित हों। प्रति संचालन [[परिशोधन विश्लेषण]] समय  <math>\Theta(\alpha(n))</math> है जहां n शीर्षों की संख्या है और α इनवर्स एकरमैन फ़ंक्शन है।<ref name="tarjan1975">{{cite journal |last1=Tarjan |first1=Robert Endre |author1-link=Robert E. Tarjan |year=1975 |title=एक अच्छे लेकिन रैखिक सेट यूनियन एल्गोरिदम की दक्षता|journal=Journal of the ACM |volume=22 |issue=2 |pages=215&ndash;225 |doi=10.1145/321879.321884 |citeseerx=10.1.1.399.6704 |s2cid=11105749 }}</ref><ref name="Tarjan1979">{{cite journal |first=Robert Endre |last=Tarjan |authorlink=Robert E. Tarjan |year=1979 |title=एल्गोरिदम का एक वर्ग जिसे असंयुक्त सेटों को बनाए रखने के लिए गैर-रेखीय समय की आवश्यकता होती है|journal=Journal of Computer and System Sciences |volume=18 |issue=2 |pages=110&ndash;127 |doi=10.1016/0022-0000(79)90042-4|doi-access=free }}</ref>
+== घटती संबद्धता ==
+वह स्थिति जिसमें किनारों को केवल पृथक किया जा सकता है जिसे [[शिमोन भी]] और [[योसी शिलोच]] द्वारा हल किया गया था।<ref>{{Cite journal | doi = 10.1145/322234.322235| title = एक ऑन-लाइन एज-डिलीशन समस्या| journal = Journal of the ACM| volume = 28| pages = 1–4| year = 1981| last1 = Shiloach | first1 = Y. | last2 = Even | first2 = S. | s2cid = 207746822}}</ref> यह संरचना तालिका का उपयोग करती है जो प्रत्येक शीर्ष के लिए उस घटक का नाम निर्दिष्ट करती है जिससे वह संबंधित है। इस प्रकार संबद्धता प्रश्नों में निरंतर समय लगता है। जब कोई किनारा हटा दिया जाता है तो तालिका को अद्यतन करना चुनौती है।
+=== चक्रीय ग्राफ़ (फारेस्ट) ===
-== घटती कनेक्टिविटी ==
+जब चक्रीय ग्राफ़ में u-v किनारे को हटा दिया जाता है तो उस किनारे वाला ट्री दो ट्री में विभक्त हो जाता है: उनमें से एक में u और दूसरे में v होता है। तालिका को निम्नलिखित उपाय से सामयिक किया जाता है।
-वह मामला जिसमें किनारों को केवल हटाया जा सकता है, [[शिमोन भी]] और [[योसी शिलोच]] द्वारा हल किया गया था।<ref>{{Cite journal | doi = 10.1145/322234.322235| title = एक ऑन-लाइन एज-डिलीशन समस्या| journal = Journal of the ACM| volume = 28| pages = 1–4| year = 1981| last1 = Shiloach | first1 = Y. | last2 = Even | first2 = S. | s2cid = 207746822}}</ref> संरचना एक तालिका का उपयोग करती है जो प्रत्येक शीर्ष के लिए उस घटक का नाम निर्दिष्ट करती है जिससे वह संबंधित है। इस प्रकार कनेक्टिविटी क्वेरी में निरंतर समय लगता है। जब कोई किनारा हटा दिया जाता है तो तालिका को अद्यतन करना चुनौती है।
+* u से प्रारम्भ करके ट्री को स्कैन करें (किसी भी ट्री स्कैन एल्गोरिदम का उपयोग करके, जैसे [[गहराई-पहली खोज|गहराई-प्रथम खोज]])।
+* v से प्रारम्भ करके ट्री को स्कैन करें।
+* उपरोक्त दो प्रक्रियाओं को समानांतर में करें अर्थात या तो दो समानांतर प्रक्रियाओं का उपयोग करके या उनके चरणों को आपस में जोड़कर (प्रथम स्कैन का एक चरण बनाएं इसके पश्चात दूसरे स्कैन का एक चरण पुनः प्रथम स्कैन का एक चरण, आदि)।
+* मान लीजिए कि जो पहला स्कैन समाप्त होता है वह u से स्कैन है (इसलिए हम जानते हैं कि u वाला ट्री छोटा है)। u के उप-ट्री में प्रत्येक नोड को नया घटक नाम निर्दिष्ट करें।
-=== चक्रीय ग्राफ़ (वन) ===
+चूँकि हम सदैव छोटे उप-घटक का नाम परिवर्तित करते हैं जहाँ डिलीट संचालन के लिए परिशोधन समय <math>O(\log(n))</math> होता है।
-जब Tree_(graph_theory)#Forest में किनारे u-v को हटा दिया जाता है, तो उस किनारे वाला पेड़ दो पेड़ों में टूट जाता है: उनमें से एक में u होता है और दूसरे में v होता है। तालिका को निम्नलिखित तरीके से अपडेट किया जाता है।
-* आप से शुरू करके पेड़ को स्कैन करें (किसी भी पेड़ स्कैन एल्गोरिदम का उपयोग करके, जैसे [[गहराई-पहली खोज]])।
-* वी से शुरू करके पेड़ को स्कैन करें।
-* उपरोक्त दो प्रक्रियाओं को समानांतर में करें, यानी, या तो दो समानांतर प्रक्रियाओं का उपयोग करके, या उनके चरणों को आपस में जोड़कर (पहले स्कैन का एक चरण बनाएं, फिर दूसरे स्कैन का एक चरण, फिर पहले स्कैन का एक चरण, आदि)।
-* मान लीजिए कि जो पहला स्कैन समाप्त होता है वह यू से स्कैन है (इसलिए हम जानते हैं कि यू वाला पेड़ छोटा है)। यू के सबट्री में प्रत्येक नोड को एक नया घटक नाम निर्दिष्ट करें।
-चूँकि हम हमेशा छोटे उप-घटक का नाम बदलते हैं, डिलीट ऑपरेशन के लिए परिशोधन समय होता है <math>O(\log(n))</math>.
 === सामान्य ग्राफ़ ===
-जब किसी सामान्य ग्राफ़ में एक किनारे को हटा दिया जाता है, तो हम नहीं जानते कि उसका घटक एक एकल घटक (अन्य किनारों से जुड़ा हुआ) रहता है या दो घटकों में टूट जाता है। इसलिए हम दो प्रक्रियाओं का उपयोग करते हैं जो समानांतर (या इंटरलीव्ड तरीके से) चलती हैं। प्रक्रिया ए यह जाँचती है कि क्या किनारा विलोपन एक घटक को तोड़ता है, और यदि ऐसा होता है, तो दोनों प्रक्रियाएँ रुक जाती हैं। प्रक्रिया बी यह जाँचती है कि क्या किनारा विलोपन उस घटक को नहीं तोड़ता है जिससे वह संबंधित है, और यदि ऐसा नहीं होता है, तो दोनों प्रक्रियाएँ फिर से रुक जाती हैं।
+जब किसी सामान्य ग्राफ़ में एक किनारे को हटा दिया जाता है तो हम नहीं जानते कि उसका घटक एकल घटक (अन्य किनारों से जुड़ा हुआ) रहता है या दो घटकों में विभक्त हो जाता है। इसलिए हम दो प्रक्रियाओं का उपयोग करते हैं जो समानांतर (या इंटरलीव्ड प्रकार से) चलती हैं। प्रक्रिया A यह जाँचती है कि क्या किनारे का विलोपन एक घटक को विभक्त करता है और यदि ऐसा होता है तो दोनों प्रक्रियाएँ रुक जाती हैं। प्रक्रिया B यह जाँचती है कि क्या किनारा विलोपन उस घटक को विभक्त नहीं करता है जिससे वह संबंधित है और यदि ऐसा नहीं होता है तो दोनों प्रक्रियाएँ पुनः से रुक जाती हैं।
-;प्रक्रिया ए: एसाइक्लिक-ग्राफ केस के समान है: दो उप-प्रक्रियाएं हैं जो हटाए गए किनारे के दोनों सिरों से स्कैन करती हैं। यदि उप-प्रक्रियाओं में से एक दूसरे छोर तक पहुंचने से पहले समाप्त हो जाती है, तो इसका मतलब है कि घटक दो उप-घटकों में टूट गया है, और छोटे उप-घटक का नाम पहले की तरह अपडेट किया गया है। इस प्रकार डिलीट ऑपरेशन के लिए परिशोधन समय फिर से है <math>O(\log(n))</math>.
+;प्रक्रिया A: एसाइक्लिक-ग्राफ स्थिति के समान : दो उप-प्रक्रियाएं हैं जो पृथक किये गए किनारे के दोनों सिरों से स्कैन करती हैं। यदि उप-प्रक्रियाओं में से एक दूसरे छोर तक पहुंचने से पहले समाप्त हो जाती है, तो इसका मतलब है कि घटक दो उप-घटकों में विभक्त हो गया है, और छोटे उप-घटक का नाम पहले की तरह अपडेट किया गया है। इस प्रकार डिलीट संचालन के लिए परिशोधन समय पुनः <math>O(\log(n))</math> है।
-;प्रक्रिया बी: चौड़ाई-पहली खोज|चौड़ाई-पहली संरचना (बीएफएस) का उपयोग करती है, जिसे निम्नानुसार आरंभ किया गया है। एक शीर्ष r चुना जाता है और BFS उससे शुरू होता है। स्तर 0 में एकमात्र शीर्ष r है। जड़ से दूरी i के सभी शीर्ष स्तर i में हैं। यदि G कनेक्ट नहीं है, तो कुछ अनस्कैन वर्टेक्स v पर एक नया स्कैन शुरू किया जाता है, v को लेवल 1 में रखा जाता है, और एक कृत्रिम किनारा v को रूट r से जोड़ता है; i से v की दूरी के सभी शीर्ष अब स्तर i+1 आदि में हैं। सभी जुड़े हुए घटकों को एक BFS संरचना में रखने के लिए कृत्रिम किनारों को पेश किया गया है और केवल इस उद्देश्य के लिए उपयोग किया जाता है। स्पष्ट रूप से, कृत्रिम किनारों का उपयोग केवल प्रक्रिया बी में किया जाता है।
+;प्रक्रिया B: चौड़ाई-पहली खोज|चौड़ाई-पहली संरचना (BFS) का उपयोग करती है, जिसे निम्नानुसार आरंभ किया गया है। एक शीर्ष r चुना जाता है और BFS उससे प्रारम्भ होता है। स्तर 0 में एकमात्र शीर्ष r है। जड़ से दूरी i के सभी शीर्ष स्तर i में हैं। यदि G कनेक्ट नहीं है तो कुछ अनस्कैन वर्टेक्स v पर नया स्कैन आरम्भ किया जाता है एवं v को लेवल 1 में रखा जाता है और कृत्रिम किनारे v को रूट r से सम्बद्ध करता है; i से v की दूरी के सभी शीर्ष अब स्तर i+1 आदि में हैं। सभी जुड़े हुए घटकों को एक BFS संरचना में रखने के लिए कृत्रिम किनारों को प्रस्तुत किया गया है और केवल इस उद्देश्य के लिए उपयोग किया जाता है। स्पष्ट रूप से, कृत्रिम किनारों का उपयोग केवल प्रक्रिया बी में किया जाता है।
 संरचना में निम्नलिखित गुण हैं। स्तर i, i>0 में एक शीर्ष v में केवल तीन प्रकार के किनारे होते हैं: पिछड़े किनारे जो इसे स्तर i−1 से जोड़ते हैं (कम से कम एक ऐसा किनारा होता है, जो कृत्रिम हो सकता है), स्थानीय किनारे जो इसे दूसरे से जोड़ते हैं स्तर I में किनारे (शून्य या अधिक ऐसे किनारे हैं), या आगे के किनारे जो इसे स्तर i+1 में किनारों से जोड़ते हैं (शून्य या अधिक ऐसे किनारे हैं)। इसलिए प्रत्येक शीर्ष v के लिए, हम किनारों के तीन सेट (पिछड़े, स्थानीय और आगे) बनाए रखते हैं।
@@ Line 36: / Line 34: @@
 जब कोई किनारा u-v हटा दिया जाता है, तो दो विकल्प होते हैं: या तो u और v एक ही स्तर पर होते हैं, या वे ऐसे स्तर में होते हैं जिनकी संख्या 1 से भिन्न होती है।
-;केस 1: यू और वी दोनों समान स्तर पर हैं। इस स्थिति में, किनारा विलोपन घटकों को नहीं बदल सकता है। किनारे को बस यू और वी के स्थानीय किनारों के सेट से हटा दिया जाता है, और प्रक्रिया बी रुक जाती है (और इसलिए प्रक्रिया ए भी रुक जाती है)। हमारी बीएफएस संरचना अभी भी वैध है।
+;स्थिति 1: यू और वी दोनों समान स्तर पर हैं। इस स्थिति में, किनारा विलोपन घटकों को नहीं परिवर्तित सकता है। किनारे को बस यू और वी के स्थानीय किनारों के सेट से हटा दिया जाता है, और प्रक्रिया बी रुक जाती है (और इसलिए प्रक्रिया ए भी रुक जाती है)। हमारी BFS संरचना अभी भी वैध है।
-;केस 2: यू और वी विभिन्न स्तरों पर हैं। व्यापकता की हानि के बिना, मान लें कि u स्तर i−1 में है और v स्तर i में है; इसलिए किनारे को आगे (यू) और पीछे (वी) से हटा दिया जाना चाहिए।
+;स्थिति 2: u और v विभिन्न स्तरों पर हैं। व्यापकता की हानि के बिना मान लें कि u स्तर i−1 में है और v स्तर i में है; इसलिए किनारे को आगे (u) और पीछे (v) से हटा दिया जाना चाहिए।
-:;केस 2.1: यदि नया बैकवर्ड (v) खाली नहीं है, तो घटक नहीं बदले हैं: अन्य किनारे हैं जो v को पीछे की ओर जोड़ते हैं। प्रक्रिया B रुक जाती है (और प्रक्रिया A भी रुक जाती है)।
+:;स्थिति 2.1: यदि नया बैकवर्ड (v) रिक्त नहीं है तो घटक परिवर्तित नहीं हैं: अन्य किनारे हैं जो v को पीछे की ओर जोड़ते हैं। प्रक्रिया B रुक जाती है (और प्रक्रिया A भी रुक जाती है)।
-:;केस 2.2: यदि नया बैकवर्ड (v) खाली है, तो v अब लेवल i−1 से जुड़ा नहीं है, और इसलिए रूट से इसकी दूरी अब i नहीं है; यह कम से कम i+1 होना चाहिए। इसके अतिरिक्त, v से जुड़े अन्य शीर्ष भी हो सकते हैं, जिनकी मूल से दूरी विलोपन के परिणामस्वरूप बढ़ जाती है। अद्यतन दूरियों की गणना करने के लिए, हम एक कतार Q का उपयोग करते हैं, जिसमें प्रारंभ में केवल शीर्ष v होता है।
+:;स्थिति 2.2: यदि नया बैकवर्ड (v) रिक्त है तो v अब लेवल i−1 से सम्बद्ध नहीं है और इसलिए रूट से इसकी दूरी अब i नहीं है; यह कम से कम i+1 होना चाहिए। इसके अतिरिक्त v से जुड़े अन्य शीर्ष भी हो सकते हैं जिनकी मूल से दूरी विलोपन के परिणामस्वरूप बढ़ जाती है। अद्यतन दूरियों की गणना करने के लिए हम कतार Q का उपयोग करते हैं जिसमें प्रारंभ में केवल शीर्ष v होता है।
-जबकि Q खाली नहीं है:
+जबकि Q रिक्त नहीं है:
-# डब्ल्यू := डीक्यू (क्यू)
+# w:= डीक्यू (Q)
 # w को उसके स्तर (जैसे, j) से हटा दें, और उसे अगले स्तर (j+1) में डाल दें।
 # स्थानीय पड़ोसियों को अपडेट करें:
-#* लोकल(w) में प्रत्येक किनारे w−x के लिए, इसे लोकल(x) से हटाएं और इसे आगे (x) में रखें।
+#* लोकल(w) में प्रत्येक किनारे w−x के लिए इसे लोकल(x) से पृथक कियें और इसे आगे (x) में रखें।
-#* पिछड़ा(डब्ल्यू) := स्थानीय(डब्ल्यू)
+#* पिछड़ा(w):= स्थानीय(w)
 # अग्रिम पड़ोसियों को अपडेट करें:
-#* आगे (डब्ल्यू) में प्रत्येक किनारे w-x के लिए, इसे पीछे (x) से हटा दें और इसे स्थानीय (x) में डालें; यदि नया बैकवर्ड (x) खाली है, तो x को Q पर पंक्तिबद्ध करें।
+#* आगे (w) में प्रत्येक किनारे w-x के लिए इसे पीछे (x) से हटा दें और इसे स्थानीय (x) में डालें; यदि नया बैकवर्ड (x) रिक्त है तो x को Q पर पंक्तिबद्ध करें।
-#* स्थानीय(डब्ल्यू) := आगे(डब्ल्यू)
+#* स्थानीय(w):= आगे(w)
-#* आगे(w) := खाली सेट
+#* आगे(w):= रिक्त सेट
-# यदि नया बैकवर्ड (w) खाली है, तो Q पर फिर से w कतार में लगाएं।
+# यदि नया बैकवर्ड (w) रिक्त है तो Q पर पुनः से w कतार में लगाएं।
-यदि किनारे हटाने से कोई घटक नहीं टूटता है और हम मामले 2.2 में हैं, तो अंततः प्रक्रिया रुक जाएगी। इस मामले में यह देखना आसान है कि बीएफएस संरचना सही ढंग से बनाए रखी गई है। यदि इसके विलोपन से कोई घटक टूट जाता है, तो प्रक्रिया अपने आप नहीं रुकेगी। हालाँकि, प्रक्रिया ए, ब्रेक को पहचानते हुए रुक जाएगी, और दोनों प्रक्रियाएँ रुक जाएँगी। इस मामले में बीएफएस संरचना में किए गए सभी परिवर्तनों को नजरअंदाज कर दिया जाता है, और हम उस बीएफएस संरचना पर वापस चले जाते हैं जो हमारे पास विलोपन से ठीक पहले थी, सिवाय इसके कि हटाए गए किनारे को अब एक कृत्रिम किनारे से बदल दिया गया है। स्पष्ट रूप से, इस मामले में v अब एक पेड़ की जड़ है जिसमें कुछ अन्य कृत्रिम किनारों के माध्यम से नया घटक और शायद अतिरिक्त घटक शामिल हैं। साथ ही, के वंशजों को जोड़ने वाला कोई किनारा नहीं है {{mvar|v}}
+यदि किनारे पृथक करने से कोई घटक नहीं टूटता है और हम स्थिति 2.2 में हों तो अंततः प्रक्रिया रुक जाएगी। इस स्थिति में यह देखना सरल है कि BFS संरचना सही प्रकार से बनाए रखी गई है। यदि इसके विलोपन से कोई घटक विभक्त हो जाता है तो प्रक्रिया अपने आप नहीं रुकेगी। जबकि प्रक्रिया A ब्रेक को पहचानते हुए रुक जाएगी और दोनों प्रक्रियाएँ रुक जाएँगी। इस स्थिति में '''BFS''' संरचना में किए गए सभी परिवर्तनों की अवहेलना कर देता है और हम उस BFS संरचना पर वापस चले जाते हैं जो हमारे पास विलोपन से ठीक पहले थी सिवाय इसके कि पृथक किये गए किनारे को अब कृत्रिम किनारे से परिवर्तित दिया गया है। स्पष्ट रूप से इस स्थिति में v अब ट्री की जड़ है जिसमें कुछ अन्य कृत्रिम किनारों के माध्यम से नया घटक और संभवतः अतिरिक्त घटक सम्मिलित हैं। साथ ही {{mvar|v}} के वंशजों को जोड़ने वाला कोई किनारा नहीं है।
-किसी भी शीर्ष के साथ जो नहीं है {{mvar|v}} के वंशज, कृत्रिम किनारे को छोड़कर {{tmath|u-v}}.<ref>One way to realize the return to the structure preceding the deletion of e without having to copy the whole structure is to keep on a stack all the changes that took place in the BFS structure since the deletion of e and undo them one by one. This way the processing time is only multiplied by a constant.</ref>
-जब भी प्रक्रिया में किसी किनारे को संसाधित किया जाता है, तो उसका एक समापन बिंदु एक स्तर तक गिर जाता है। चूंकि प्रक्रिया बी द्वारा समाप्त किए गए रनों में एक शीर्ष तक पहुंचने वाला निम्नतम स्तर है <math>|V|-1</math>, प्रति किनारा लागत सीमाबद्ध है <math>2|V|</math>. इसलिए प्रति विलोपन कार्रवाई में परिशोधन समय है <math>O(n)</math>.
-== पूरी तरह से गतिशील कनेक्टिविटी ==
+{{mvar|v}} के वंशज जो कृत्रिम किनारे {{tmath|u-v}}<ref>One way to realize the return to the structure preceding the deletion of e without having to copy the whole structure is to keep on a stack all the changes that took place in the BFS structure since the deletion of e and undo them one by one. This way the processing time is only multiplied by a constant.</ref> को छोड़कर किसी भी शीर्ष के साथ नहीं है।
-=== चक्रीय ग्राफ़ (वन) ===
+जब भी प्रक्रिया में किसी किनारे को संसाधित किया जाता है तो उसका समापन बिंदु एक स्तर तक गिर जाता है। चूंकि प्रक्रिया B द्वारा समाप्त किए गए संचालनों में शीर्ष तक पहुंचने वाला निम्नतम स्तर <math>|V|-1</math> है एवं प्रति किनारा लागत <math>2|V|</math> सीमाबद्ध है इसलिए प्रति विलोपन कार्रवाई में परिशोधन समय <math>O(n)</math> है।
-किसी जंगल को [[लिंक-कट पेड़]]ों या यूलर टूर पेड़ों के संग्रह का उपयोग करके दर्शाया जा सकता है। तब गतिशील कनेक्टिविटी समस्या को आसानी से हल किया जा सकता है, क्योंकि प्रत्येक दो नोड्स के लिए x,y, x, y से जुड़ा होता है यदि और केवल यदि FindRoot(x)=FindRoot(y)। परिशोधित अद्यतन समय और क्वेरी समय दोनों O(log(n)) हैं।
+== पूर्ण रूप से डायनमिक कनेक्टिविटी ==
+=== चक्रीय ग्राफ़ (फारेस्ट) ===
+किसी फ़ॉरेस्ट को [[लिंक-कट पेड़|लिंक-कट ट्री]] या यूलर टूर ट्री के संग्रह का उपयोग करके दर्शाया जा सकता है। तब डायनमिक कनेक्टिविटी समस्या को सरलता से हल किया जा सकता है क्योंकि प्रत्येक दो नोड्स के लिए x,y, x, y से जुड़ा होता है यदि और केवल यदि FindRoot(x)=FindRoot(y)। परिशोधित अद्यतन समय और क्वेरी समय दोनों O(log(n)) हैं।
 === सामान्य ग्राफ़ ===
-एक सामान्य ग्राफ़ को उसके फैले हुए जंगल द्वारा दर्शाया जा सकता है - एक जंगल जिसमें ग्राफ़ के प्रत्येक जुड़े घटक के लिए एक पेड़ होता है। हम इस फैले हुए जंगल को एफ कहते हैं। एफ को यूलर टूर पेड़ों के जंगल द्वारा दर्शाया जा सकता है।
+सामान्य ग्राफ़ को उसके फैले हुए फ़ॉरेस्ट द्वारा दर्शाया जा सकता है - एक फ़ॉरेस्ट जिसमें ग्राफ़ के प्रत्येक जुड़े घटक के लिए ट्री होता है। हम इस फैले हुए फ़ॉरेस्ट को F कहते हैं। F को यूलर टूर ट्री के फ़ॉरेस्ट द्वारा दर्शाया जा सकता है।
-क्वेरी और इंसर्ट ऑपरेशंस को एफ का प्रतिनिधित्व करने वाले ईटी पेड़ों पर संबंधित ऑपरेशंस का उपयोग करके कार्यान्वित किया जाता है। चुनौतीपूर्ण ऑपरेशन डिलीट है, और विशेष रूप से, एक किनारे को हटाना जो एफ के स्पैनिंग पेड़ों में से एक में निहित है। यह स्पैनिंग ट्री को दो में तोड़ देता है पेड़, लेकिन, यह संभव है कि कोई और किनारा हो जो उन्हें जोड़ता हो। चुनौती यह है कि यदि ऐसा कोई प्रतिस्थापन किनारा मौजूद है तो उसे तुरंत खोजा जाए। इसके लिए अधिक जटिल डेटा संरचना की आवश्यकता होती है। ऐसी कई संरचनाओं का वर्णन नीचे किया गया है।
+क्वेरी और इंसर्ट संचालनों को F का प्रतिनिधित्व करने वाले ET ट्री पर संबंधित संचालनों का उपयोग करके कार्यान्वित किया जाता है। चुनौतीपूर्ण संचालन डिलीट है और विशेष रूप से एक किनारे को हटाना जो F के स्पैनिंग ट्री में से एक में निहित है। यह स्पैनिंग ट्री को दो में विभक्त कर देता है लेकिन यह संभव है कि कोई और किनारा हो जो उन्हें सम्बद्ध करता हो। चुनौती यह है कि यदि ऐसा कोई प्रतिस्थापन किनारा उपस्थित है तो उसे तुरंत खोजा जाए। इसके लिए अधिक जटिल डेटा संरचना की आवश्यकता होती है। ऐसी कई संरचनाओं का वर्णन नीचे किया गया है।
 ==== स्तर संरचना ====
-ग्राफ़ में प्रत्येक किनारे को एक स्तर निर्दिष्ट किया गया है। माना L=lg n. ग्राफ़ में डाले गए प्रत्येक किनारे का स्तर L से प्रारंभ किया गया है, और डिलीट ऑपरेशन के दौरान 0 तक घट सकता है।
+ग्राफ़ में प्रत्येक किनारे को एक स्तर तक निर्दिष्ट किया गया है। माना L=lg n ग्राफ़ में डाले गए प्रत्येक किनारे का स्तर L से प्रारंभ किया गया है और डिलीट संचालन के समय 0 तक घट सकता है।
-और L के बीच प्रत्येक i के लिए, Gi को उस सबग्राफ के रूप में परिभाषित करें जिसमें किनारों का स्तर i या उससे कम है, और Fi Gi का फैला हुआ जंगल है। हमारा पहले का वन F अब FL कहलाता है। हम वनों का घटता क्रम रखेंगे FL ⊇ ... ⊇ F0. <ref>{{Cite journal | doi = 10.1145/502090.502095| title = Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity| journal = Journal of the ACM| volume = 48| issue = 4| pages = 723| year = 2001| last1 = Holm | first1 = J. | last2 = De Lichtenberg | first2 = K. | last3 = Thorup | first3 = M. | s2cid = 7273552}}</ref><ref>[http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf Dynamic Graph Problems] - in Lecture Notes in Advanced Data Structures. Prof. Erik Demaine; Scribe: Katherine Lai.</ref>
+और L के मध्य प्रत्येक i के लिए Gi को उस सबग्राफ के रूप में परिभाषित करें जिसमें किनारों का स्तर i या उससे कम है और Fi Gi का फैला हुआ फ़ॉरेस्ट है। हमारा पहले का फ़ॉरेस्ट F अब FL कहलाता है। हम वनों का घटता क्रम FL ⊇ ... ⊇ F0 रखेंगे।<ref>{{Cite journal | doi = 10.1145/502090.502095| title = Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity| journal = Journal of the ACM| volume = 48| issue = 4| pages = 723| year = 2001| last1 = Holm | first1 = J. | last2 = De Lichtenberg | first2 = K. | last3 = Thorup | first3 = M. | s2cid = 7273552}}</ref><ref>[http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf Dynamic Graph Problems] - in Lecture Notes in Advanced Data Structures. Prof. Erik Demaine; Scribe: Katherine Lai.</ref>
 ===== परिचालन =====
-क्वेरी और इंसर्ट ऑपरेशन केवल सबसे बड़े फ़ॉरेस्ट FL का उपयोग करते हैं। छोटे सबग्राफ से केवल डिलीट ऑपरेशन के दौरान सलाह ली जाती है, और विशेष रूप से, उस किनारे को हटाना जो एफएल के फैले हुए पेड़ों में से एक में निहित है।
+क्वेरी और इंसर्ट संचालन केवल सबसे बड़े फ़ॉरेस्ट FL का उपयोग करते हैं। छोटे सबग्राफ से केवल डिलीट संचालन के समय सलाह ली जाती है और विशेष रूप से उस किनारे को हटाना जो FL के फैले हुए ट्री में से एक में निहित है।
-जब इस तरह के किनारे e = x−y को हटा दिया जाता है, तो इसे सबसे पहले FL से और उन सभी छोटे फैले हुए जंगलों से हटा दिया जाता है, यानी i ≥ स्तर (e) वाले प्रत्येक Fi से। फिर हम प्रतिस्थापन किनारे की तलाश करते हैं।
+जब इस प्रकार के किनारे e = x−y को हटा दिया जाता है तो इसे सबसे पहले FL से और उन सभी छोटे फैले हुए फ़ॉरेस्टों से हटा दिया जाता है अर्थात i ≥ स्तर (e) वाले प्रत्येक Fi से। पुनः हम प्रतिस्थापन किनारे की खोज करते हैं।
-सबसे छोटे फैले जंगल से शुरू करें जिसमें ई, अर्थात्, फाई के साथ आई = स्तर (ई) शामिल है। किनारा e एक निश्चित पेड़ T⊆Fi से संबंधित है। ई को हटाने के बाद, पेड़ टी दो छोटे पेड़ों में टूट जाता है: टीएक्स जिसमें नोड एक्स होता है और टाय जिसमें नोड वाई होता है। Gi का एक किनारा एक प्रतिस्थापन किनारा है, यदि और केवल यदि यह Tx में एक नोड को Ty में एक नोड से जोड़ता है। मान लीजिए कि टीएक्स छोटा पेड़ है (यानी इसमें टी के अधिकतम आधे नोड होते हैं; हम यूलर पेड़ों में जोड़े गए एनोटेशन द्वारा प्रत्येक उपट्री का आकार बता सकते हैं)।
+सबसे छोटे फैले फ़ॉरेस्ट से प्रारम्भ करें जिसमें e, अर्थात् Fi के साथ i = स्तर (e) सम्मिलित है। किनारा e एक निश्चित ट्री T⊆Fi से संबंधित है। e को पृथक करने के बाद ट्री T दो छोटे ट्री में विभक्त हो जाता है: Tx जिसमें नोड x होता है और Ty जिसमें नोड y होता है। Gi का किनारा प्रतिस्थापन किनारा होता है यदि और केवल यदि यह Tx में नोड को Ty में नोड से सम्बद्ध करता है। मान लीजिए कि Tx छोटा ट्री है (अर्थात इसमें टी के अधिकतम आधे नोड होते हैं; हम यूलर ट्री में जोड़े गए एनोटेशन द्वारा प्रत्येक उपट्री का आकार बता सकते हैं)।
-हम पहले Tx के प्रत्येक किनारे के स्तर को 1 से कम करते हैं। फिर हम सभी किनारों ε पर स्तर i और Tx में कम से कम एक नोड के साथ लूप करते हैं:
+हम पहले Tx के प्रत्येक किनारे के स्तर को 1 से कम करते हैं। पुनः हम सभी किनारों ε पर स्तर i और Tx में कम से कम एक नोड के साथ लूप करते हैं:
-* यदि ε का दूसरा नोड Ty में है, तो एक प्रतिस्थापन किनारा मिल जाता है! इस किनारे को Fi और FL तक के सभी वनों में जोड़ें, और समाप्त करें। फैले हुए जंगल निश्चित हैं। ध्यान दें कि इस खोज के लिए भुगतान करने के लिए, हम खोज के दौरान देखे गए किनारों के स्तर को कम कर देते हैं।
+* यदि ε का दूसरा नोड Ty में है तो एक प्रतिस्थापन किनारा मिल जाता है! इस किनारे को Fi और FL तक के सभी वनों में जोड़ें, और समाप्त करें। फैले हुए फ़ॉरेस्ट निश्चित हैं। ध्यान दें कि इस खोज के लिए भुगतान करने के लिए हम खोज के समय देखे गए किनारों के स्तर को कम कर देते हैं।
-* यदि ε का दूसरा नोड Tx में है, तो यह प्रतिस्थापन किनारा नहीं है, और हमारा समय बर्बाद करने के लिए इसे 'दंडित' करने के लिए, हम इसके स्तर को 1 से कम कर देते हैं।
+* यदि ε का दूसरा नोड Tx में है तो यह प्रतिस्थापन किनारा नहीं है और हमारा समय नष्ट करने के परिणामस्वरूप हम इसके स्तर को 1 से कम कर देते हैं।
 ===== विश्लेषण =====
-प्रत्येक किनारे का स्तर अधिकतम lg n बार कम हो जाएगा। क्यों? क्योंकि प्रत्येक कमी के साथ, यह एक ऐसे पेड़ में गिरता है जिसका आकार पिछले स्तर में इसके पेड़ के आकार का अधिकतम आधा होता है। इसलिए प्रत्येक स्तर i में, प्रत्येक जुड़े घटक में नोड्स की संख्या अधिकतम 2 है<sup>मैं</sup>. इसलिए किनारे का स्तर हमेशा कम से कम 0 होता है।
+प्रत्येक किनारे का स्तर अधिकतम lg ''n'' बार कम हो जाएगा। क्यों? क्योंकि प्रत्येक कमी के साथ यह ऐसे ट्री में गिरता है जिसका आकार पिछले स्तर में इसके ट्री के आकार का अधिकतम आधा होता है। इसलिए प्रत्येक स्तर i में प्रत्येक जुड़े घटक में नोड्स की संख्या अधिकतम 2<sup>i</sup> है इसलिए किनारे का स्तर सदैव कम से कम 0 होता है।
-प्रत्येक किनारा जिसका स्तर कम हो जाता है, ले लेता है <math>O(\lg n)</math> खोजने का समय (ईटी ट्री ऑपरेशंस का उपयोग करके)। कुल मिलाकर, प्रत्येक सम्मिलित किनारा लेता है <math>O(\lg^2 n)</math> इसे हटाए जाने तक का समय, इसलिए हटाने के लिए परिशोधन समय है  <math>O(\lg^2 n)</math>. डिलीट का शेष भाग भी लेता है <math>O(\lg^2 n)</math> समय, चूँकि हमें अधिक से अधिक किनारे को हटाना है <math>O(\lg n)</math> स्तर, और प्रत्येक स्तर से हटाने में लगता है <math>O(\lg n)</math> (फिर से ईटी ऑपरेशंस का उपयोग करके)।
+प्रत्येक किनारा जिसका स्तर कम हो जाता है एवं खोजने का समय (ईटी ट्री संचालनों का उपयोग करके)  <math>O(\lg n)</math> मानते है। कुल मिलाकर प्रत्येक सम्मिलित किनारा इसे पृथक किये जाने तक का समय <math>O(\lg^2 n)</math> लेता है  इसलिए पृथक करने के लिए परिशोधन समय  <math>O(\lg^2 n)</math> है एवं डिलीट का शेष भाग <math>O(\lg^2 n)</math> समय भी लेता है चूँकि हमें अधिक से अधिक <math>O(\lg n)</math> स्तर किनारे को हटाना है और प्रत्येक स्तर से पृथक करने में <math>O(\lg n)</math> (पुनः से ईटी संचालनों का उपयोग करके) लगता है।
-कुल मिलाकर, प्रति अद्यतन परिशोधन समय है <math>O(\lg^2 n)</math>. प्रति प्रश्न समय में सुधार किया जा सकता है <math>O(\lg n / \lg \lg n)</math>.
+कुल मिलाकर प्रति अद्यतन परिशोधन समय <math>O(\lg^2 n)</math> है एवं प्रति प्रश्न समय में सुधार <math>O(\lg n / \lg \lg n)</math> किया जा सकता है।
-हालाँकि, प्रति अद्यतन सबसे खराब स्थिति वाला समय हो सकता है <math>O(n)</math>. यह प्रश्न कि क्या सबसे खराब स्थिति में सुधार किया जा सकता है, एक खुला प्रश्न था, जब तक कि इसे कटसेट संरचना द्वारा सकारात्मक रूप से हल नहीं किया गया था।
+जबकि प्रति अद्यतन सबसे दोषपूर्ण स्थिति वाला समय <math>O(n)</math> हो सकता है एवं यह प्रश्न कि क्या सबसे दोषपूर्ण स्थिति में सुधार किया जा सकता है यह एक खुला प्रश्न था जब तक कि इसे कटसेट संरचना द्वारा सकारात्मक रूप से हल नहीं किया गया था।
 ==== कटसेट संरचना ====
-एक ग्राफ G(V,E) और एक उपसमुच्चय T⊆V को देखते हुए, Cutset(T) को किनारों के सेट के रूप में परिभाषित करें जो T को V\T से जोड़ते हैं। ''कटसेट संरचना'' एक डेटा संरचना है, जो पूरे ग्राफ़ को मेमोरी में रखे बिना, कटसेट में तुरंत एक किनारा ढूंढ सकती है, यदि ऐसा कोई किनारा मौजूद है। <ref>{{Cite conference | doi = 10.1137/1.9781611973105.81| title = पॉलीलॉगरिदमिक सबसे खराब स्थिति में गतिशील ग्राफ़ कनेक्टिविटी| conference = Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms| pages = 1131| year = 2013| last1 = Kapron | first1 = B. M. | last2 = King | first2 = V. | last3 = Mountjoy | first3 = B. | isbn = 978-1-61197-251-1}}</ref>
+ग्राफ G(V,E) और उपसमुच्चय T⊆V को देखते हुए Cutset(T) को किनारों के सेट के रूप में परिभाषित करते हैं जो T को V\T से जोड़ते हैं। '''''कटसेट संरचना'''''  डेटा संरचना है जो पूरे ग्राफ़ को मेमोरी में रखे बिना कटसेट में तुरंत किनारा खोज सकती है यदि ऐसा कोई किनारा उपस्थित होता है। <ref>{{Cite conference | doi = 10.1137/1.9781611973105.81| title = पॉलीलॉगरिदमिक सबसे खराब स्थिति में गतिशील ग्राफ़ कनेक्टिविटी| conference = Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms| pages = 1131| year = 2013| last1 = Kapron | first1 = B. M. | last2 = King | first2 = V. | last3 = Mountjoy | first3 = B. | isbn = 978-1-61197-251-1}}</ref>
-प्रत्येक शीर्ष को एक संख्या देकर प्रारंभ करें। मान लीजिए कि n शीर्ष हैं; फिर प्रत्येक शीर्ष को lg(n) बिट्स वाली एक संख्या द्वारा दर्शाया जा सकता है। इसके बाद, प्रत्येक किनारे को एक संख्या दें, जो इसके शीर्षों की संख्याओं का संयोजन है - 2 lg(n) बिट्स वाली एक संख्या।
+प्रत्येक शीर्ष को एक संख्या देकर प्रारंभ करें। मान लीजिए कि n शीर्ष हैं; पुनः प्रत्येक शीर्ष को lg(n) बिट्स वाली एक संख्या द्वारा दर्शाया जा सकता है। इसके पश्चात प्रत्येक किनारे को एक संख्या दें जो इसके शीर्षों की संख्याओं का संयोजन - 2 lg(n) बिट्स वाली एक संख्या है।
-प्रत्येक शीर्ष v के लिए, [[xor]](v) की गणना करें और रखें, जो कि उसके निकटवर्ती सभी किनारों की संख्याओं का xor है।
+प्रत्येक शीर्ष v के लिए [[xor]](v) की गणना करें और रखें जो कि उसके निकटवर्ती सभी किनारों की संख्याओं का xor है।
-अब प्रत्येक उपसमुच्चय T⊆V के लिए, 'xor(T)' = T में सभी शीर्षों के मानों के xor की गणना करना संभव है। एक किनारे e = u−v पर विचार करें जो T का आंतरिक किनारा है (यानी दोनों u और v T में हैं)। e की संख्या को xor(T) में दो बार शामिल किया गया है - एक बार u के लिए और एक बार v के लिए। चूँकि प्रत्येक संख्या का xor स्वयं 0 है, e गायब हो जाता है और xor(T) को प्रभावित नहीं करता है। इस प्रकार, xor(T) वास्तव में कटसेट(T) में सभी किनारों का xor है। कई विकल्प हैं:
+अब प्रत्येक उपसमुच्चय T⊆V के लिए 'xor(T)' = T में सभी शीर्षों के मानों के xor की गणना करना संभव है। किनारे e = u−v पर विचार करें जो T का आंतरिक किनारा है (अर्थात दोनों u और v T में हैं)। e की संख्या को xor(T) में दो बार सम्मिलित किया गया है - एक बार u के लिए और एक बार v के लिए। चूँकि प्रत्येक संख्या का xor स्वयं 0 है तथा e गायब हो जाता है और xor(T) को प्रभावित नहीं करता है। इस प्रकार xor(T) वास्तव में कटसेट(T) में सभी किनारों का xor है। कई विकल्प हैं:
-* यदि xor(T)=0, तो हम आत्मविश्वास से उत्तर दे सकते हैं कि Cutset(T) खाली है।
+* यदि xor(T)=0, तो हम आत्मविश्वास से उत्तर दे सकते हैं कि कटसेट(T) रिक्त है।
-* यदि xor(T) वास्तविक किनारे e की संख्या है, तो संभवतः कटसेट(T) में e ही एकमात्र किनारा है, और हम e वापस कर सकते हैं। हम ई की संख्या से ई के अंतिम बिंदुओं को एलजी (एन) सबसे बाएं बिट्स और एलजी (एन) सबसे दाएं बिट्स में विभाजित करके भी पढ़ सकते हैं।
+* यदि xor(T) वास्तविक किनारे e की संख्या है तो संभवतः कटसेट(T) में e ही एकमात्र किनारा है, और हम e वापस कर सकते हैं। हम ई की संख्या से ई के अंतिम बिंदुओं को एलजी (एन) सबसे बाएं बिट्स और एलजी (एन) सबसे दाएं बिट्स में विभाजित करके भी पढ़ सकते हैं।
 * तीसरा विकल्प यह है कि xor(T) एक गैर-शून्य संख्या है जो वास्तविक किनारे का प्रतिनिधित्व नहीं करती है। यह केवल तभी हो सकता है जब कटसेट (T) में दो या दो से अधिक किनारे हों, क्योंकि उस स्थिति में xor(T) कई संख्या में किनारों का xor है। इस मामले में, हम विफलता की रिपोर्ट करते हैं, क्योंकि हम जानते हैं कि कटसेट में किनारे हैं लेकिन किसी एक किनारे की पहचान नहीं कर सकते हैं। <ref>There is a small probability that the xor of several different edges will result in a number which happens to be the number of another edge. This might lead to a false positive. In order to reduce the probability of this event, we can enlarge the domain of the numbers of vertices to, say, ''n''<sup>3</sup> instead of ''n''. Then, if there is more than one edge in cutset(T), xor(T) will almost certainly be a meaningless value, as stated above.</ref>
 अब हमारा लक्ष्य इस तीसरे विकल्प को संभालना है।
-सबसे पहले, कटसेट संरचनाओं के एलजी (एन) स्तरों का एक अनुक्रम बनाएं, जिनमें से प्रत्येक में ऊपरी स्तर से लगभग आधे किनारे होते हैं (यानी, प्रत्येक स्तर के लिए, संभावना 1/2 के साथ ऊपरी स्तर से प्रत्येक किनारे को चुनें)। यदि पहले स्तर में xor(T) एक अवैध मान लौटाता है, जिसका अर्थ है कि कटसेट(T) में दो या दो से अधिक किनारे हैं, तो संभावना है कि अगले स्तर में, जिसमें कम किनारे हैं, xor(T) एक वैध मान लौटाएगा मान क्योंकि Cutset(T) में एक ही किनारा होगा। यदि xor(T) अभी भी अवैध मान लौटाता है, तो अगले स्तर पर जारी रखें, आदि। चूंकि किनारों की संख्या कम हो रही है, इसलिए दो मामले हैं:
+सबसे पहले कटसेट संरचनाओं के lg (n) स्तरों का एक अनुक्रम बनाएं जिनमें से प्रत्येक में ऊपरी स्तर से लगभग आधे किनारे होते हैं (अर्थात प्रत्येक स्तर के लिए संभावना 1/2 के साथ ऊपरी स्तर से प्रत्येक किनारे को चुनें)। यदि पहले स्तर में xor(T) एक अवैध मान लौटाता है जिसका अर्थ है कि कटसेट(T) में दो या दो से अधिक किनारे हैं तो संभावना है कि अगले स्तर में जिसमें कम किनारे हैं, xor(T) वैध मान लौटाएगा क्योंकि कटसेट(T) में एक ही किनारा होगा। यदि xor(T) अभी भी अवैध मान लौटाता है तो अगले स्तर पर जारी रखें, आदि। चूंकि किनारों की संख्या कम हो रही है इसलिए दो स्थितियां हैं:
-* अच्छा मामला यह है कि अंततः हमें एक ऐसा स्तर मिल जाता है जिसमें कटसेट(टी) में एक ही किनारा होता है; फिर हम उस किनारे को लौटाते हैं और समाप्त करते हैं।
+* अनुकूल स्थिति यह है कि अंततः हमें एक ऐसा स्तर प्राप्त हो जाता है जिसमें कटसेट(टी) में एक ही किनारा होता है; पुनः हम उस किनारे को लौटाते हैं और समाप्त करते हैं।
-* बुरी स्थिति यह है कि अंततः हमें एक ऐसा स्तर मिलता है जिसमें कटसेट(टी) में कोई किनारा नहीं होता है; तब हम विफलता की रिपोर्ट करते हैं, क्योंकि हम जानते हैं कि कटसेट में किनारे हैं लेकिन किसी एक किनारे की पहचान नहीं कर सकते हैं।
+* बुरी स्थिति यह है कि अंततः हमें एक ऐसा स्तर मिलता है जिसमें कटसेट(टी) में कोई किनारा नहीं होता है तब हम विफलता की रिपोर्ट करते हैं क्योंकि हम जानते हैं कि कटसेट में किनारे हैं लेकिन किसी एक किनारे की पहचान नहीं कर सकते हैं।
 यह सिद्ध करना संभव है कि सफलता की संभावना कम से कम 1/9 है।
-इसके बाद, स्तर संरचना के स्वतंत्र संस्करणों C lg(n) का एक संग्रह बनाएं, जहां C एक स्थिरांक है। प्रत्येक संस्करण में, स्तर से स्तर तक किनारों की एक स्वतंत्र यादृच्छिक कमी करें। प्रत्येक संस्करण पर प्रत्येक क्वेरी का प्रयास करें जब तक कि उनमें से कोई एक सफल न हो जाए। सभी संस्करणों के विफल होने की संभावना अधिकतम है:
+इसके पश्चात स्तर संरचना के स्वतंत्र संस्करणों C lg(n) का एक संग्रह बनाएं जहां C एक स्थिरांक है। प्रत्येक संस्करण में स्तर से स्तर तक किनारों की एक स्वतंत्र यादृच्छिक कमी करें। प्रत्येक संस्करण पर प्रत्येक क्वेरी का प्रयास करें जब तक कि उनमें से कोई एक सफल न हो जाए। सभी संस्करणों के विफल होने की संभावना अधिकतम है:
-:<math>(1-1/9)^{C \lg{n}} = 2^{- 0.17C \lg{n}} = n^{-0.17 C}</math> C के उचित चयन से हम विफलता की संभावना को मनमाने ढंग से 0 के करीब बना सकते हैं।
+:<math>(1-1/9)^{C \lg{n}} = 2^{- 0.17C \lg{n}} = n^{-0.17 C}</math> C के उचित चयन से हम विफलता की संभावना को मनमाने ढंग से 0 के निकट बना सकते हैं।
 ===== परिचालन =====
-हम एक गतिशील कनेक्टिविटी संरचना में एक कटसेट संरचना जोड़ सकते हैं।
+हम एक डायनमिक कनेक्टिविटी संरचना में कटसेट संरचना जोड़ सकते हैं।
-कटसेट संरचना पर इन्सर्ट और डिलीट ऑपरेशन बिल्कुल उसी तरह से किए जाते हैं: डाले गए/हटाए गए किनारे को इसके दोनों एंडपॉइंट्स में XORed किया जाता है।
+कटसेट संरचना पर इन्सर्ट और डिलीट संचालन बिल्कुल उसी प्रकार से किए जाते हैं: डाले गए /पृथक किये गए किनारे को इसके दोनों एंडपॉइंट्स में XORed किया जाता है।
-जब गतिशील कनेक्टिविटी संरचना के लिए उपयोग किए जाने वाले स्पैनिंग फ़ॉरेस्ट से एक किनारे को हटा दिया जाता है, तो प्रतिस्थापन किनारे को खोजने के लिए कटसेट संरचना का उपयोग किया जाता है।
+जब डायनमिक कनेक्टिविटी संरचना के लिए उपयोग किए जाने वाले स्पैनिंग फ़ॉरेस्ट से एक किनारे को हटा दिया जाता है तो प्रतिस्थापन किनारे को खोजने के लिए कटसेट संरचना का उपयोग किया जाता है।
 ===== विश्लेषण =====
-एक एकल कटसेट संरचना के लिए केवल O(n lg n) मेमोरी की आवश्यकता होती है - प्रत्येक n शीर्ष के लिए 2 lg n बिट्स के साथ केवल एक संख्या। हमें किनारों को स्वयं नहीं रखना है। घने ग्राफ़ के लिए, यह पूरे ग्राफ़ को मेमोरी में रखने की तुलना में बहुत सस्ता है।
+एकल कटसेट संरचना के लिए केवल O(n lg n) मेमोरी की आवश्यकता होती है - प्रत्येक n शीर्ष के लिए 2 lg n बिट्स के साथ केवल एक संख्या। हमें किनारों को स्वयं नहीं रखना है। घने ग्राफ़ के लिए, यह पूरे ग्राफ़ को मेमोरी में रखने की तुलना में अधिक सस्ता है।
-हमें lg(n) संस्करण रखना होगा, जिनमें से प्रत्येक में lg(n) स्तर होंगे। इसलिए, कुल मेमोरी आवश्यकता है {{tmath|O(n \lg^3 n)}}.
+हमें lg(n) संस्करण रखना होगा जिनमें से प्रत्येक में lg(n) स्तर होंगे। इसलिए कुल मेमोरी आवश्यकता  {{tmath|O(n \lg^3 n)}} है।
-सबसे खराब स्थिति में क्वेरी का समय O(polylog(n)) है। यह डायनामिक कनेक्टिविटी#लेवल संरचना के विपरीत है, जिसमें क्वेरी का समय O(पॉलीलॉग(n)) परिशोधित है, लेकिन सबसे खराब स्थिति का समय O(n) है।
+सबसे खराब स्थिति में क्वेरी का समय O(polylog(n)) है। यह '''डायनामिक संबद्धता''', लेवल संरचना के विपरीत है जिसमें क्वेरी का समय O(polylog(n)) परिशोधित है लेकिन सबसे खराब स्थिति का समय O(n) है।
-=== ऑफ़लाइन गतिशील कनेक्टिविटी ===
+=== ऑफ़लाइन डायनमिक कनेक्टिविटी ===
-यदि किनारों को जिस क्रम में हटाया जाएगा वह समय से पहले ज्ञात है, तो हम प्रति क्वेरी लॉग (एन) में गतिशील कनेक्टिविटी समस्या को हल कर सकते हैं। यदि हम एक अधिकतम फैले हुए वन को बनाए रख सकते हैं जहां किनारों को उनके विलोपन समय के अनुसार क्रमबद्ध किया जाता है, तो हम जानते हैं कि जब हम जंगल में मौजूद कुछ किनारों को हटाते हैं, तो कोई संभावित किनारा नहीं है जो इसे प्रतिस्थापित कर सके। यदि कोई किनारा होता जो हटाए गए किनारे के समान दो घटकों को जोड़ता है, तो यह दूसरा किनारा हमारे द्वारा हटाए गए किनारे के बजाय अधिकतम फैले हुए जंगल का हिस्सा होता। यह डिलीट ऑपरेशन को तुच्छ बना देता है: यदि डिलीट किया जाने वाला किनारा हमारे जंगल का हिस्सा है, तो हमें बस पेड़ को उसके दो हिस्सों में विभाजित करना होगा, या अन्यथा ऑपरेशन को अनदेखा करना होगा।
+यदि किनारों को जिस क्रम में पृथक किया जाएगा वह समय से पहले ज्ञात है, तो हम प्रति क्वेरी लॉग (एन) में डायनमिक कनेक्टिविटी समस्या को हल कर सकते हैं। यदि हम एक अधिकतम फैले हुए वन को बनाए रख सकते हैं जहां किनारों को उनके विलोपन समय के अनुसार क्रमबद्ध किया जाता है, तो हम जानते हैं कि जब हम फ़ॉरेस्ट में उपस्थित कुछ किनारों को हटाते हैं, तो कोई संभावित किनारा नहीं है जो इसे प्रतिस्थापित कर सके। यदि कोई किनारा होता जो पृथक किये गए किनारे के समान दो घटकों को सम्बद्ध करता है, तो यह दूसरा किनारा हमारे द्वारा पृथक किये गए किनारे के स्थान पर अधिकतम फैले हुए फ़ॉरेस्ट का भाग होता। यह '''डिलीट''' संचालन को तुच्छ बना देता है: यदि डिलीट किया जाने वाला किनारा हमारे फ़ॉरेस्ट का भाग है तो हमें बस ट्री को उसके दो भागों में विभाजित करना होगा या अन्यथा संचालन को अनदेखा करना होगा।
-किनारा जोड़ना थोड़ा अधिक जटिल है। यदि हम u से v तक एक किनारा किनारा e जोड़ते हैं, तो यदि u और v जुड़े नहीं हैं, तो यह किनारा अधिकतम स्पैनिंग फ़ॉरेस्ट का हिस्सा होगा। यदि वे जुड़े हुए हैं, तो हम अपने जंगल में u->v जोड़ना चाहते हैं यदि यह हमारे अधिकतम फैले हुए जंगल में सुधार कर सकता है। ऐसा करने के लिए, हमें तुरंत यह जांचने की आवश्यकता है कि यू से वी तक के पथ पर किस किनारे को हटाने का समय सबसे कम है। यदि इस किनारे को हटाने का समय ई के हटाने के समय के बाद आता है, तो ई हमारे अधिकतम फैले हुए जंगल में सुधार नहीं कर सकता है। अन्यथा, दूसरे किनारे को हटा दिया जाना चाहिए और उसे ई से बदल दिया जाना चाहिए।
+किनारों को सम्बद्ध करना थोड़ा अधिक जटिल है। यदि हम u से v तक एक किनारा किनारा e जोड़ते हैं तो यदि u और v जुड़े नहीं हैं तो यह किनारा अधिकतम स्पैनिंग फ़ॉरेस्ट का भाग होगा। यदि वे जुड़े हुए हैं तो हम अपने फ़ॉरेस्ट में u->v सम्बद्ध करना चाहते हैं यदि यह हमारे अधिकतम फैले हुए फ़ॉरेस्ट में सुधार कर सकता है। ऐसा करने के लिए, हमें तुरंत यह जांचने की आवश्यकता है कि यू से वी तक के पथ पर किस किनारे को पृथक करने का समय सबसे कम है। यदि इस किनारे को पृथक करने का समय E के पृथक करने के समय के बाद आता है, तो ई हमारे अधिकतम फैले हुए फ़ॉरेस्ट में सुधार नहीं कर सकता है। अन्यथा, दूसरे किनारे को हटा दिया जाना चाहिए और उसे ई से परिवर्तित दिया जाना चाहिए।
-इसके लिए हमें निम्नलिखित ऑपरेशन करने की आवश्यकता है: एक किनारा जोड़ें, एक किनारा काटें, और पथ पर न्यूनतम किनारे की क्वेरी करें जिसे प्रति ऑपरेशन लॉग (एन) में लिंक-कट ट्री के साथ आसानी से किया जा सकता है।
+इसके लिए हमें निम्नलिखित संचालन करने की आवश्यकता है: एक किनारा जोड़ें, एक किनारा काटें और पथ पर न्यूनतम किनारे की क्वेरी करें जिसे प्रति संचालन log(n) में लिंक-कट ट्री के साथ सरलता से किया जा सकता है।
 == यह भी देखें ==
@@ Line 143: / Line 142: @@
 {{reflist}}
 * See also: {{Cite conference | doi = 10.1145/335305.335345| title = Near-optimal fully-dynamic graph connectivity| conference = Proceedings of the thirty-second annual ACM symposium on Theory of computing - STOC '00| pages = 343| year = 2000| last1 = Thorup | first1 = M. | isbn = 1581131844}}
-[[Category: ग्राफ़ डेटा संरचनाएँ]] [[Category: ग्राफ़ एल्गोरिदम]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 27/06/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with maths render errors]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:ग्राफ़ एल्गोरिदम]]
+[[Category:ग्राफ़ डेटा संरचनाएँ]]

Anonymous

Search

डायनमिक कनेक्टिविटी: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 12:49, 8 September 2023

Contents

वृद्धिशील संबद्धता

घटती संबद्धता

चक्रीय ग्राफ़ (फारेस्ट)

सामान्य ग्राफ़

पूर्ण रूप से डायनमिक कनेक्टिविटी

चक्रीय ग्राफ़ (फारेस्ट)

सामान्य ग्राफ़

स्तर संरचना

परिचालन

विश्लेषण

कटसेट संरचना

परिचालन

विश्लेषण

ऑफ़लाइन डायनमिक कनेक्टिविटी

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डायनमिक कनेक्टिविटी: Difference between revisions

Latest revision as of 12:49, 8 September 2023

वृद्धिशील संबद्धता

घटती संबद्धता

चक्रीय ग्राफ़ (फारेस्ट)

सामान्य ग्राफ़

पूर्ण रूप से डायनमिक कनेक्टिविटी

चक्रीय ग्राफ़ (फारेस्ट)

सामान्य ग्राफ़

स्तर संरचना

परिचालन

विश्लेषण

कटसेट संरचना

परिचालन

विश्लेषण

ऑफ़लाइन डायनमिक कनेक्टिविटी

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories