द्विसंबद्ध घटक: Difference between revisions
No edit summary |
No edit summary |
||
| Line 7: | Line 7: | ||
=== रैखिक समय गहराई-पहली खोज === | === रैखिक समय गहराई-पहली खोज === | ||
[[जॉन हॉपक्रॉफ्ट]] और [[रॉबर्ट टार्जन]] (1973) के कारण एक संबद्ध [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष आलेख]] में द्विसंबद्ध घटकों की गणना के लिए | [[जॉन हॉपक्रॉफ्ट]] और [[रॉबर्ट टार्जन]] (1973) के कारण एक संबद्ध [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष आलेख]] में द्विसंबद्ध घटकों की गणना के लिए उत्कृष्ट अनुक्रमिक एल्गोरिदम है।<ref>{{Cite journal| first1 = J.| first2 = R.| last1 = Hopcroft| last2 = Tarjan| title = Algorithm 447: efficient algorithms for graph manipulation| journal = Communications of the ACM| volume = 16| issue = 6| pages = 372–378| year = 1973| doi = 10.1145/362248.362272| doi-access = free}}</ref> यह रैखिक समय में चलता है, और गहराई पहली खोज पर आधारित है। इस एल्गोरिदम को एल्गोरिदम के परिचय की समस्या 22-2 (दोनों 2 और 3 संस्करण) के रूप में भी रेखांकित किया गया है। | ||
निम्नलिखित जानकारी को बनाए रखते हुए [[गहराई-पहली खोज]] चलाने का विचार है: | निम्नलिखित जानकारी को बनाए रखते हुए [[गहराई-पहली खोज]] चलाने का विचार है: | ||
| Line 46: | Line 46: | ||
=== अन्य एल्गोरिदम === | === अन्य एल्गोरिदम === | ||
उपरोक्त | उपरोक्त एल्गोरिदम का एक सरल विकल्प [[श्रृंखला अपघटन]] का उपयोग करता है, जो गहराई-पहले खोज-ट्रीों के आधार पर विशेष कान अपघटन हैं।<ref name="Schmidt">{{citation | ||
| last = Schmidt | first = Jens M. | author-link = Jens M. Schmidt | | last = Schmidt | first = Jens M. | author-link = Jens M. Schmidt | ||
| doi = 10.1016/j.ipl.2013.01.016 | | doi = 10.1016/j.ipl.2013.01.016 | ||
| Line 58: | Line 58: | ||
समस्या के [[ ऑनलाइन एल्गोरिदम |ऑनलाइन एल्गोरिदम]] संस्करण में, कोने और किनारों को गतिशील रूप से जोड़ा जाता है (लेकिन हटाया नहीं जाता है), और एक डेटा संरचना को द्विसंबद्ध घटकों को बनाए रखना चाहिए। [[जेफरी वेस्टब्रुक]] और रॉबर्ट टार्जन (1992) <ref>{{Cite journal| first1 = J.| first2 = R. E.| title = ब्रिज-कनेक्टेड और बाइकनेक्टेड घटकों को ऑनलाइन बनाए रखना| last1 = Westbrook| journal = Algorithmica| volume = 7| issue = 1–6| pages = 433–464| year = 1992| doi = 10.1007/BF01758773| last2 = Tarjan}}</ref> [[असंयुक्त-सेट डेटा संरचना]]ओं के आधार पर इस समस्या के लिए एक कुशल डेटा संरचना विकसित की। विशेष रूप से, यह प्रक्रिया करता है {{mvar|n}} शीर्ष जोड़ और {{mvar|m}} बढ़त में जोड़ {{math|''O''(''m'' ''α''(''m'', ''n''))}} कुल समय, कहाँ {{mvar|α}} प्रतिलोम एकरमैन फलन है। यह समय सीमा उत्तम सिद्ध होती है। | समस्या के [[ ऑनलाइन एल्गोरिदम |ऑनलाइन एल्गोरिदम]] संस्करण में, कोने और किनारों को गतिशील रूप से जोड़ा जाता है (लेकिन हटाया नहीं जाता है), और एक डेटा संरचना को द्विसंबद्ध घटकों को बनाए रखना चाहिए। [[जेफरी वेस्टब्रुक]] और रॉबर्ट टार्जन (1992) <ref>{{Cite journal| first1 = J.| first2 = R. E.| title = ब्रिज-कनेक्टेड और बाइकनेक्टेड घटकों को ऑनलाइन बनाए रखना| last1 = Westbrook| journal = Algorithmica| volume = 7| issue = 1–6| pages = 433–464| year = 1992| doi = 10.1007/BF01758773| last2 = Tarjan}}</ref> [[असंयुक्त-सेट डेटा संरचना]]ओं के आधार पर इस समस्या के लिए एक कुशल डेटा संरचना विकसित की। विशेष रूप से, यह प्रक्रिया करता है {{mvar|n}} शीर्ष जोड़ और {{mvar|m}} बढ़त में जोड़ {{math|''O''(''m'' ''α''(''m'', ''n''))}} कुल समय, कहाँ {{mvar|α}} प्रतिलोम एकरमैन फलन है। यह समय सीमा उत्तम सिद्ध होती है। | ||
[[उजी विस्किन]] और रॉबर्ट टार्जन (1985) <ref>{{Cite journal| first1 = R.| first2 = U.| last1 = Tarjan| last2 = Vishkin| title = एक कुशल समानांतर बाइकनेक्टिविटी एल्गोरिथम| journal = [[SIAM Journal on Computing|SIAM J. Comput.]] | volume = 14 | issue = 4 | pages = 862–874 | year = 1985 | doi = 10.1137/0214061| citeseerx = 10.1.1.465.8898}}</ref> CRCW [[समानांतर रैंडम-एक्सेस मशीन]] पर एक समानांतर | [[उजी विस्किन]] और रॉबर्ट टार्जन (1985) <ref>{{Cite journal| first1 = R.| first2 = U.| last1 = Tarjan| last2 = Vishkin| title = एक कुशल समानांतर बाइकनेक्टिविटी एल्गोरिथम| journal = [[SIAM Journal on Computing|SIAM J. Comput.]] | volume = 14 | issue = 4 | pages = 862–874 | year = 1985 | doi = 10.1137/0214061| citeseerx = 10.1.1.465.8898}}</ref> CRCW [[समानांतर रैंडम-एक्सेस मशीन]] पर एक समानांतर एल्गोरिदम डिज़ाइन किया गया है जो अंदर चलता है {{math|''O''(log ''n'')}} इसके साथ समय {{math|''n'' + ''m''}} प्रोसेसर। | ||
== संबंधित संरचनाएं == | == संबंधित संरचनाएं == | ||
Revision as of 23:16, 20 April 2023
आलेख सिद्धांत में, एक द्विसंबद्ध घटक (कभी-कभी 2-संबद्ध घटक के रूप में जाना जाता है) एक अधिकतम द्विसंबद्ध उपआलेख होता है। कोई भी संबद्ध (आलेख सिद्धांत) द्विसंबद्ध घटकों के एक ट्री (आलेख सिद्धांत) में विघटित हो जाता है जिसे आलेख़ का कक्ष-कट ट्री कहा जाता है। कक्ष एक दूसरे से साझा शीर्ष ( आलेख सिद्धांत ) से जुड़े होते हैं जिन्हें कट कोने या अलग-अलग कोने या संधि बिन्दु कहा जाता है। विशेष रूप से, एक कट शीर्ष कोई भी शीर्ष होता है जिसके हटाने से संबद्ध घटक (आलेख सिद्धांत) की संख्या बढ़ जाती है।[1]
एल्गोरिदम
रैखिक समय गहराई-पहली खोज
जॉन हॉपक्रॉफ्ट और रॉबर्ट टार्जन (1973) के कारण एक संबद्ध अप्रत्यक्ष आलेख में द्विसंबद्ध घटकों की गणना के लिए उत्कृष्ट अनुक्रमिक एल्गोरिदम है।[2] यह रैखिक समय में चलता है, और गहराई पहली खोज पर आधारित है। इस एल्गोरिदम को एल्गोरिदम के परिचय की समस्या 22-2 (दोनों 2 और 3 संस्करण) के रूप में भी रेखांकित किया गया है।
निम्नलिखित जानकारी को बनाए रखते हुए गहराई-पहली खोज चलाने का विचार है:
- डेप्थ-फर्स्ट-सर्च ट्री में प्रत्येक शीर्ष की गहराई (एक बार देखने के बाद), और
- प्रत्येक शीर्ष के लिए v, के सभी वंशजों के पड़ोसियों की सबसे कम गहराई v (शामिल v ही) डेप्थ-फर्स्ट-सर्च ट्री में, जिसे कहा जाता है lowpoint.
गहराई पहली खोज के दौरान बनाए रखने के लिए गहराई मानक है। का निम्न बिंदु v के सभी वंशजों का दौरा करने के बाद गणना की जा सकती है v (यानी, ठीक पहले v डेप्थ-फर्स्ट-सर्च स्टैक (अमूर्त डेटा प्रकार)) की न्यूनतम गहराई के रूप में पॉप ऑफ हो जाता है v, के सभी पड़ोसियों की गहराई v (माता-पिता के अलावा v डेप्थ-फर्स्ट-सर्च ट्री में) और सभी बच्चों का निम्न बिंदु v डेप्थ-फर्स्ट-सर्च ट्री में।
मुख्य तथ्य यह है कि एक नॉनरूट शीर्ष v एक कट शीर्ष (या संधि बिन्दु) है जो दो द्विसंबद्ध घटकों को अलग करता है यदि और केवल अगर कोई बच्चा है y का v ऐसा है कि lowpoint(y) ≥ depth(v). इस संपत्ति का परीक्षण तब किया जा सकता है जब प्रत्येक बच्चे से गहराई-पहली खोज वापस आ जाए v (यानी, ठीक पहले v डेप्थ-फ़र्स्ट-सर्च स्टैक से पॉप अप हो जाता है), और अगर सही है, v आलेख़ को अलग-अलग बाइसंबद्ध घटकों में अलग करता है। इस तरह के प्रत्येक में से एक द्विसंबद्ध घटक की गणना करके इसका प्रतिनिधित्व किया जा सकता है y (एक घटक जिसमें शामिल है y का सबट्री होगा y, प्लस v), और उसके बाद के सबट्री को मिटा दें y पेड़ से।
रूट शीर्ष को अलग से हैंडल किया जाना चाहिए: यह एक कट शीर्ष है अगर और केवल अगर इसके डीएफएस ट्री में कम से कम दो बच्चे हैं। इस प्रकार, रूट के प्रत्येक चाइल्ड सबट्री (रूट सहित) में से केवल एक घटक बनाना पर्याप्त है।
स्यूडोकोड
GetArticulationPoints(i, d)
देखा [i]: = सच
गहराई [i] := डी
कम [i] := डी
बच्चे की गिनती: = 0
isArticulation: = झूठा
adj [i] do में प्रत्येक ni के लिए
अगर नहीं देखा [नी] तो
अभिभावक [नी]: = मैं
GetArticulationPoints(ni, d + 1)
चाइल्डकाउंट := चाइल्डकाउंट + 1
अगर कम [नी] ≥ गहराई [i] तो
आर्टिक्यूलेशन: = सच
कम [i] : = न्यूनतम (कम [i], कम [नी])
वरना अगर नी ≠ माता पिता [i] तो
कम [i] : = न्यूनतम (कम [i], गहराई [नी])
अगर (माता-पिता [i] ≠ अशक्त और आर्टिक्यूलेशन) या (माता-पिता [i] = अशक्त और चाइल्डकाउंट> 1) तो
आउटपुट i अभिव्यक्ति बिंदु के रूप में
ध्यान दें कि बच्चे और माता-पिता डीएफएस पेड़ में संबंधों को दर्शाते हैं, मूल आलेख नहीं।
<दिव>
अन्य एल्गोरिदम
उपरोक्त एल्गोरिदम का एक सरल विकल्प श्रृंखला अपघटन का उपयोग करता है, जो गहराई-पहले खोज-ट्रीों के आधार पर विशेष कान अपघटन हैं।[3] इस ब्रिज (आलेख थ्योरी) #Bridge-Finding with Chain Decompositions द्वारा चेन डीकंपोज़िशन की गणना रैखिक समय में की जा सकती है। होने देना C की एक श्रृंखला अपघटन हो G. तब G 2-शीर्ष -संबद्ध है अगर और केवल अगर G न्यूनतम डिग्री (आलेख सिद्धांत) 2 और है C1 में एकमात्र चक्र (आलेख सिद्धांत) है C. यह तुरंत एक रैखिक-समय 2-संबद्ध परीक्षण देता है और सभी कटे हुए शीर्षों को सूचीबद्ध करने के लिए बढ़ाया जा सकता है G निम्न कथन का उपयोग करते हुए रैखिक समय में: एक शीर्ष v एक जुड़े आलेख में G (न्यूनतम डिग्री 2 के साथ) एक कट शीर्ष है अगर और केवल अगर v एक पुल (आलेख सिद्धांत) या के लिए घटना है v चक्र का पहला शीर्ष है C – C1. कटे हुए शीर्षों की सूची का उपयोग द्विसंबद्ध घटक#कक्ष-कट ट्री|का कक्ष-कट ट्री बनाने के लिए किया जा सकता है G रैखिक समय में।
समस्या के ऑनलाइन एल्गोरिदम संस्करण में, कोने और किनारों को गतिशील रूप से जोड़ा जाता है (लेकिन हटाया नहीं जाता है), और एक डेटा संरचना को द्विसंबद्ध घटकों को बनाए रखना चाहिए। जेफरी वेस्टब्रुक और रॉबर्ट टार्जन (1992) [4] असंयुक्त-सेट डेटा संरचनाओं के आधार पर इस समस्या के लिए एक कुशल डेटा संरचना विकसित की। विशेष रूप से, यह प्रक्रिया करता है n शीर्ष जोड़ और m बढ़त में जोड़ O(m α(m, n)) कुल समय, कहाँ α प्रतिलोम एकरमैन फलन है। यह समय सीमा उत्तम सिद्ध होती है।
उजी विस्किन और रॉबर्ट टार्जन (1985) [5] CRCW समानांतर रैंडम-एक्सेस मशीन पर एक समानांतर एल्गोरिदम डिज़ाइन किया गया है जो अंदर चलता है O(log n) इसके साथ समय n + m प्रोसेसर।
संबंधित संरचनाएं
तुल्यता संबंध
एक मनमाने ढंग से अप्रत्यक्ष आलेख के किनारों पर एक द्विआधारी संबंध को परिभाषित कर सकता है, जिसके अनुसार दो किनारे e और f संबंधित हैं अगर और केवल अगर या तो e = f या आलेख़ में दोनों के माध्यम से एक साधारण चक्र होता है e और f. प्रत्येक किनारा स्वयं से संबंधित है, और एक किनारा है e दूसरे किनारे से संबंधित है f अगर और केवल अगर f से इसी प्रकार संबंधित है e. कम स्पष्ट रूप से, यह एक सकर्मक संबंध है: यदि किनारों से युक्त एक साधारण चक्र मौजूद है e और f, और किनारों से युक्त एक अन्य सरल चक्र f और g, तो कोई इन दोनों चक्रों को जोड़कर एक सरल चक्र खोज सकता है e और g. इसलिए, यह एक तुल्यता संबंध है, और इसका उपयोग किनारों को तुल्यता वर्गों में विभाजित करने के लिए किया जा सकता है, किनारों के सबसेट संपत्ति के साथ कि दो किनारे एक दूसरे से संबंधित हैं यदि और केवल यदि वे समान तुल्यता वर्ग से संबंधित हैं। प्रत्येक तुल्यता वर्ग में किनारों द्वारा गठित सबआलेख दिए गए आलेख के द्विसंबद्ध घटक हैं। इस प्रकार, द्विसंबद्ध घटक आलेख के किनारों को विभाजित करते हैं; हालाँकि, वे एक दूसरे के साथ शीर्ष साझा कर सकते हैं।[6]
कक्ष आलेख
किसी दिए गए आलेख का कक्ष आलेख G इसके कक्षों का प्रतिच्छेदन आलेख है। इस प्रकार, इसके प्रत्येक कक्ष के लिए एक शीर्ष है G, और दो शीर्षों के बीच एक किनारा जब भी संबंधित दो कक्ष एक शीर्ष साझा करते हैं। एक आलेख H दूसरे आलेख का कक्ष आलेख है G बिल्कुल जब के सभी कक्ष H पूर्ण सबआलेख हैं। रेखांकन H इस संपत्ति के साथ कक्ष आलेख के रूप में जाने जाते हैं।[7]
कक्ष-कट ट्री
एक आलेख का कटपॉइंट, कट शीर्ष या संधि बिन्दु G एक शीर्ष है जिसे दो या दो से अधिक कक्षों द्वारा साझा किया जाता है। संबद्ध आलेख़ के कक्ष और कटप्वाइंट की संरचना को एक ट्री (आलेख सिद्धांत) द्वारा वर्णित किया जा सकता है जिसे कक्ष-कट ट्री या बीसी-ट्री कहा जाता है। इस पेड़ में प्रत्येक कक्ष के लिए और दिए गए आलेख के प्रत्येक अभिव्यक्ति बिंदु के लिए एक शीर्ष है। कक्ष के प्रत्येक जोड़े के लिए कक्ष-कट ट्री में एक किनारा होता है और उस कक्ष से संबंधित एक संधि बिन्दु होता है।[8]
यह भी देखें
- त्रिकोणीय घटक
- ब्रिज (आलेख सिद्धांत)
- निर्देशित रेखांकन में द्वि-जुड़े घटकों का एकल-प्रविष्टि एकल-निकास काउंटर भाग
टिप्पणियाँ
- ↑ AL-TAIE, MOHAMMED ZUHAIR. KADRY, SEIFEDINE (2019). "3. Graph Theory". ग्राफ और नेटवर्क विश्लेषण के लिए पायथन।. SPRINGER. ISBN 3-319-85037-7. OCLC 1047552679.
एक कट-वर्टेक्स एक ऐसा शीर्ष है जिसे हटाने पर नेटवर्क घटकों की संख्या बढ़ जाती है।
{{cite book}}: CS1 maint: multiple names: authors list (link) - ↑ Hopcroft, J.; Tarjan, R. (1973). "Algorithm 447: efficient algorithms for graph manipulation". Communications of the ACM. 16 (6): 372–378. doi:10.1145/362248.362272.
- ↑ Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters, 113 (7): 241–244, arXiv:1209.0700, doi:10.1016/j.ipl.2013.01.016.
- ↑ Westbrook, J.; Tarjan, R. E. (1992). "ब्रिज-कनेक्टेड और बाइकनेक्टेड घटकों को ऑनलाइन बनाए रखना". Algorithmica. 7 (1–6): 433–464. doi:10.1007/BF01758773.
- ↑ Tarjan, R.; Vishkin, U. (1985). "एक कुशल समानांतर बाइकनेक्टिविटी एल्गोरिथम". SIAM J. Comput. 14 (4): 862–874. CiteSeerX 10.1.1.465.8898. doi:10.1137/0214061.
- ↑ Tarjan & Vishkin (1985) credit the definition of this equivalence relation to Harary (1969); however, Harary does not appear to describe it in explicit terms.
- ↑ Harary, Frank (1969), Graph Theory, Addison-Wesley, p. 29.
- ↑ Harary (1969), p. 36.
संदर्भ
- Eugene C. Freuder (1985). "A Sufficient Condition for Backtrack-Bounded Search". Journal of the Association for Computing Machinery. 32 (4): 755–761. doi:10.1145/4221.4225.
