द्विसंबद्ध घटक
ग्राफ़ थ्योरी में, एक बायकनेक्टेड कंपोनेंट (कभी-कभी 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.
