डायनमिक कनेक्टिविटी

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

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

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

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

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

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

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

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

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

जब चक्रीय ग्राफ़ में 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 रिक्त नहीं है:

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

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

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

जब भी प्रक्रिया में किसी किनारे को संसाधित किया जाता है तो उसका समापन बिंदु एक स्तर तक गिर जाता है। चूंकि प्रक्रिया 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 रखेंगे।

परिचालन

क्वेरी और इंसर्ट संचालन केवल सबसे बड़े फ़ॉरेस्ट 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 से जोड़ते हैं। कटसेट संरचना डेटा संरचना है जो पूरे ग्राफ़ को मेमोरी में रखे बिना कटसेट में तुरंत किनारा खोज सकती है यदि ऐसा कोई किनारा उपस्थित होता है।

प्रत्येक शीर्ष को एक संख्या देकर प्रारंभ करें। मान लीजिए कि 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 है। इस मामले में, हम विफलता की रिपोर्ट करते हैं, क्योंकि हम जानते हैं कि कटसेट में किनारे हैं लेकिन किसी एक किनारे की पहचान नहीं कर सकते हैं।

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

सबसे पहले कटसेट संरचनाओं के 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) में लिंक-कट ट्री के साथ सरलता से किया जा सकता है।

यह भी देखें

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

संदर्भ

• 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.