द्विसंबद्ध घटक
आलेख सिद्धांत में, एक द्विसंबद्ध घटक (कभी-कभी 2-संबद्ध घटक के रूप में जाना जाता है) एक अधिकतम द्विसंबद्ध उपआलेख होता है। कोई भी संबद्ध (आलेख सिद्धांत) द्विसंबद्ध घटकों के ट्री (आलेख सिद्धांत) में विघटित हो जाते है जिसे आलेख़ का कक्ष-प्रभाज ट्री कहा जाता है। कक्ष एक दूसरे से साझा शीर्ष (आलेख सिद्धांत) से जुड़े होते हैं जिन्हें प्रभाज कोने या अलग-अलग कोने या संधि बिन्दु कहा जाता है। विशेष रूप से, एक प्रभाज शीर्ष कोई भी शीर्ष होता है जिसके हटाने से संबद्ध घटक (आलेख सिद्धांत) की संख्या बढ़ जाती है।[1]
एल्गोरिदम
रैखिक समय डेप्थ-प्रथम सर्च
जॉन हॉपक्रॉफ्ट और रॉबर्ट टार्जन (1973) के कारण एक संबद्ध अप्रत्यक्ष आलेख में द्विसंबद्ध घटकों की गणना के लिए उत्कृष्ट अनुक्रमिक एल्गोरिदम है।[2] यह रैखिक समय में चलता है, और डेप्थ प्रथम सर्च पर आधारित है। इस एल्गोरिदम को एल्गोरिदम के परिचय की समस्या 22-2 (दोनों 2 और 3 संस्करण) के रूप में भी रेखांकित किया गया है।
निम्नलिखित जानकारी को बनाए रखते हुए डेप्थ-प्रथम सर्च चलाने का विचार है:
- डेप्थ-प्रथम-सर्च ट्री में प्रत्येक शीर्ष की डेप्थ (एक बार देखने के बाद), और
- प्रत्येक शीर्ष v के लिए, डेप्थ-प्रथम-सर्च ट्री में v के सभी वंशजों के निकटवर्तियों की सबसे कम डेप्थ (v सहित), जिसे lowpoint कहा जाता है।
डेप्थ प्रथम सर्च के समय बनाए रखने के लिए डेप्थ मानक है। v के निम्न बिंदु की गणना v के सभी वंशजों को (अर्थात, डेप्थ-प्रथम-सर्च स्टैक से v के पॉप अप होने से ठीक पहले) v की न्यूनतम डेप्थ, v के सभी निकटवर्तियों की डेप्थ (डेप्थ-प्रथम-सर्च ट्री में v के जनक के अतिरिक्त) और डेप्थ-प्रथम-सर्च वृक्ष में v के सभी बच्चों के निम्न बिंदु के रूप में जाने के बाद की जा सकती है।
मुख्य तथ्य यह है कि एक गैर रूट शीर्ष v एक प्रभाज शीर्ष (या संधि बिन्दु) है जो दो द्विसंबद्ध घटकों को अलग करता है यदि और मात्र यदि v का कोई बच्चा y है जैसे कि lowpoint(y) ≥ depth(v)। इस गुण का परीक्षण तब किया जा सकता है जब v के प्रत्येक बच्चे से डेप्थ-प्रथम सर्च वापस कर दी जाती है (अर्थात, v डेप्थ-फर्स्ट-सर्च स्टैक से पॉप अप होने से ठीक पहले), और यदि सत्य है, तो v आलेख़ को अलग-अलग द्विसंबद्ध घटकों में अलग कर देते है। इसे प्रत्येक ऐसे y में से एक द्विसंबद्ध घटक की गणना करके (एक घटक जिसमें y सम्मिलित है, में y, प्लस v का उपट्री सम्मिलित होगा), और फिर ट्री से y के उपट्री को मिटाकर प्रदर्शित किया जा सकता है।
रूट शीर्ष को अलग से हैंडल किया जाना चाहिए: यह एक प्रभाज शीर्ष है यदि और मात्र यदि इसके डीएफएस ट्री में कम से कम दो बच्चे हैं। इस प्रकार, रूट के प्रत्येक बच्चा उपट्री (रूट सहित) में से मात्र एक घटक बनाना पर्याप्त है।
स्यूडोकोड
GetArticulationPoints (i, d)
visited[i] := true
depth[i] := d
low[i] := d
childCount := 0
isArticulation := false
for each ni in adj[i] do
if not visited[ni] then
parent[ni] := i
GetArticulationPoints (ni, d + 1)
childCount := childCount + 1
if low[ni] ≥ depth[i] then
isArticulation := true
low[i] := Min (low[i], low[ni])
else if ni ≠ parent[i] then
low[i] := Min (low[i], depth[ni])
if (parent[i] ≠ null and isArticulation) or (parent[i] = null and childCount > 1) then
Output i as articulation point
ध्यान दें कि बच्चे और माता-पिता डीएफएस ट्री में संबंधों को दर्शाते हैं, मूल आलेख नहीं।
अन्य एल्गोरिदम
उपरोक्त एल्गोरिदम का सरल विकल्प श्रृंखला अपघटन का उपयोग करता है, जो डेप्थ-पहले सर्च-ट्री के आधार पर विशेष कान अपघटन हैं।[3] इस ब्रिज (आलेख सिद्धांत) नियम द्वारा श्रृंखला अपघटन की गणना रैखिक समय में की जा सकती है। C को G का एक श्रृंखला अपघटन होने दें। फिर G 2-शीर्ष -संबद्ध है यदि और मात्र यदि G न्यूनतम डिग्री (आलेख सिद्धांत) 2 है और C में C1 एकमात्र चक्र (आलेख सिद्धांत) है। यह तुरंत रैखिक-समय 2-संबद्ध परीक्षण देते है और निम्न कथन का उपयोग करके रैखिक समय में G के सभी प्रभाज शीर्षों को सूचीबद्ध करने के लिए विस्तारित किया जा सकता है: संबद्ध आलेख G में एक शीर्ष v (न्यूनतम डिग्री 2 के साथ) प्रभाज शीर्ष है यदि और मात्र यदि v एक पुल (आलेख सिद्धांत) के लिए घटना है या v C – C1 में एक चक्र का पहला शीर्ष है। रैखिक समय में G के कक्ष-प्रभाज ट्री को बनाने के लिए शीर्षों की सूची का उपयोग किया जा सकता है।
समस्या के ऑनलाइन एल्गोरिदम संस्करण में, कोने और किनारों को गतिशील रूप से जोड़ा जाता है (परन्तु हटाया नहीं जाता है), और डेटा संरचना को द्विसंबद्ध घटकों को बनाए रखना चाहिए। जेफरी वेस्टब्रुक और रॉबर्ट टार्जन (1992) [4] असंयुक्त-समूह डेटा संरचनाओं के आधार पर इस समस्या के लिए कुशल डेटा संरचना विकसित की। विशेष रूप से, यह O(m α(m, n)) कुल समय में n शीर्ष जोड़ और m किनारा जोड़ संसाधित करता है, जहां α प्रतिलोम एकरमैन फलन है। यह समय सीमा उत्तम सिद्ध होती है।
उजी विस्किन और रॉबर्ट टार्जन (1985) [5] CRCW समानांतर रैंडम-एक्सेस मशीन पर समानांतर एल्गोरिदम डिज़ाइन किया जो n + m प्रोसेसर के साथ O(log n) समय में चलते है।
संबंधित संरचनाएं
तुल्यता संबंध
यादृच्छिक अप्रत्यक्ष आलेख के किनारों पर एक द्विआधारी संबंध को परिभाषित कर सकते है, जिसके अनुसार दो किनारे 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.
