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

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

ग्राफ़ के शीर्षों का सेट V निश्चित है, लेकिन किनारों का सेट E बदल सकता है। कठिनाई के क्रम में तीन मामले हैं:

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

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

वृद्धिशील कनेक्टिविटी

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

घटती कनेक्टिविटी

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

चक्रीय ग्राफ़ (वन)

जब Tree_(graph_theory)#Forest में किनारे u-v को हटा दिया जाता है, तो उस किनारे वाला पेड़ दो पेड़ों में टूट जाता है: उनमें से एक में u होता है और दूसरे में v होता है। तालिका को निम्नलिखित तरीके से अपडेट किया जाता है।

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

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

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

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

प्रक्रिया ए

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

प्रक्रिया बी

चौड़ाई-पहली खोज|चौड़ाई-पहली संरचना (बीएफएस) का उपयोग करती है, जिसे निम्नानुसार आरंभ किया गया है। एक शीर्ष 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 में हैं, तो अंततः प्रक्रिया रुक जाएगी। इस मामले में यह देखना आसान है कि बीएफएस संरचना सही ढंग से बनाए रखी गई है। यदि इसके विलोपन से कोई घटक टूट जाता है, तो प्रक्रिया अपने आप नहीं रुकेगी। हालाँकि, प्रक्रिया ए, ब्रेक को पहचानते हुए रुक जाएगी, और दोनों प्रक्रियाएँ रुक जाएँगी। इस मामले में बीएफएस संरचना में किए गए सभी परिवर्तनों को नजरअंदाज कर दिया जाता है, और हम उस बीएफएस संरचना पर वापस चले जाते हैं जो हमारे पास विलोपन से ठीक पहले थी, सिवाय इसके कि हटाए गए किनारे को अब एक कृत्रिम किनारे से बदल दिया गया है। स्पष्ट रूप से, इस मामले में 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(पॉलीलॉग(n)) परिशोधित है, लेकिन सबसे खराब स्थिति का समय O(n) है।

ऑफ़लाइन गतिशील कनेक्टिविटी

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

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

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

यह भी देखें

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

संदर्भ

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