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

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

ग्राफ़ के शीर्षों का सेट 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

चौड़ाई-पहली खोज|चौड़ाई-पहली संरचना (बीएफएस) का उपयोग करती है, जिसे निम्नानुसार आरंभ किया गया है। एक शीर्ष 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

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

केस 2

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

केस 2.1

यदि नया बैकवर्ड (v) रिक्त नहीं है, तो घटक नहीं परिवर्तिते हैं: अन्य किनारे हैं जो v को पीछे की ओर जोड़ते हैं। प्रक्रिया B रुक जाती है (और प्रक्रिया A भी रुक जाती है)।

केस 2.2

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

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

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

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

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

पूर्ण रूप से सक्रिय संबद्धता

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

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

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

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

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

स्तर संरचना

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

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

परिचालन

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

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

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

हम पहले 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, तो हम आत्मविश्वास से उत्तर दे सकते हैं कि Cutset(T) रिक्त है।
• यदि xor(T) वास्तविक किनारे e की संख्या है तो संभवतः कटसेट(T) में e ही एकमात्र किनारा है, और हम e वापस कर सकते हैं। हम ई की संख्या से ई के अंतिम बिंदुओं को एलजी (एन) सबसे बाएं बिट्स और एलजी (एन) सबसे दाएं बिट्स में विभाजित करके भी पढ़ सकते हैं।
• तीसरा विकल्प यह है कि xor(T) एक गैर-शून्य संख्या है जो वास्तविक किनारे का प्रतिनिधित्व नहीं करती है। यह केवल तभी हो सकता है जब कटसेट (T) में दो या दो से अधिक किनारे हों, क्योंकि उस स्थिति में xor(T) कई संख्या में किनारों का xor है। इस मामले में, हम विफलता की रिपोर्ट करते हैं, क्योंकि हम जानते हैं कि कटसेट में किनारे हैं लेकिन किसी एक किनारे की पहचान नहीं कर सकते हैं।

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

सबसे पहले, कटसेट संरचनाओं के एलजी (एन) स्तरों का एक अनुक्रम बनाएं, जिनमें से प्रत्येक में ऊपरी स्तर से लगभग आधे किनारे होते हैं (अर्थात, प्रत्येक स्तर के लिए, संभावना 1/2 के साथ ऊपरी स्तर से प्रत्येक किनारे को चुनें)। यदि पहले स्तर में xor(T) एक अवैध मान लौटाता है, जिसका अर्थ है कि कटसेट(T) में दो या दो से अधिक किनारे हैं, तो संभावना है कि अगले स्तर में, जिसमें कम किनारे हैं, xor(T) एक वैध मान लौटाएगा मान क्योंकि Cutset(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.