द्विसंबद्ध घटक: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Maximal biconnected subgraph}} | {{Short description|Maximal biconnected subgraph}} | ||
{{confused|शीर्ष विभाजक}} | {{confused|शीर्ष विभाजक}} | ||
[[Image:Graph-Biconnected-Components.svg|thumb|alt=An example graph with biconnected components marked|प्रत्येक रंग एक द्विसंबद्ध घटक से मेल खाता है। बहुरंगी कोने | [[Image:Graph-Biconnected-Components.svg|thumb|alt=An example graph with biconnected components marked|प्रत्येक रंग एक द्विसंबद्ध घटक से मेल खाता है। बहुरंगी कोने प्रभाज कोने होते हैं, और इस प्रकार वे कई द्विसंबद्ध घटकों से संबंधित होते हैं।]]आलेख सिद्धांत में, एक द्विसंबद्ध घटक (कभी-कभी 2-संबद्ध घटक के रूप में जाना जाता है) एक अधिकतम [[ द्विसंबद्ध ग्राफ |द्विसंबद्ध उपआलेख]] होता है। कोई भी संबद्ध (आलेख सिद्धांत) द्विसंबद्ध घटकों के [[वृक्ष (ग्राफ सिद्धांत)|ट्री (आलेख सिद्धांत]]) में विघटित हो जाते है जिसे आलेख़ का कक्ष-प्रभाज ट्री कहा जाता है। कक्ष एक दूसरे से साझा शीर्ष ([[ ग्राफ सिद्धांत |आलेख सिद्धांत]]) से जुड़े होते हैं जिन्हें प्रभाज कोने या अलग-अलग कोने या संधि बिन्दु कहा जाता है। विशेष रूप से, एक प्रभाज शीर्ष कोई भी शीर्ष होता है जिसके हटाने से [[ जुड़ा हुआ घटक (ग्राफ सिद्धांत) |संबद्ध घटक (आलेख सिद्धांत]]) की संख्या बढ़ जाती है।<ref name="AL-TAIE p. ">{{cite book | last=AL-TAIE | first=MOHAMMED ZUHAIR. KADRY, SEIFEDINE | title=ग्राफ और नेटवर्क विश्लेषण के लिए पायथन।| publisher=SPRINGER | publication-place= | date=2019 | isbn=3-319-85037-7 | oclc=1047552679 | page= | quote= एक कट-वर्टेक्स एक ऐसा शीर्ष है जिसे हटाने पर नेटवर्क घटकों की संख्या बढ़ जाती है।| chapter=3. Graph Theory}}</ref> | ||
| Line 11: | Line 11: | ||
निम्नलिखित जानकारी को बनाए रखते हुए [[गहराई-पहली खोज|डेप्थ-प्रथम सर्च]] चलाने का विचार है: | निम्नलिखित जानकारी को बनाए रखते हुए [[गहराई-पहली खोज|डेप्थ-प्रथम सर्च]] चलाने का विचार है: | ||
# डेप्थ-प्रथम-सर्च ट्री में प्रत्येक शीर्ष की डेप्थ (एक बार देखने के बाद), और | # डेप्थ-प्रथम-सर्च ट्री में प्रत्येक शीर्ष की डेप्थ (एक बार देखने के बाद), और | ||
# प्रत्येक शीर्ष {{mvar|v}} के लिए, डेप्थ-प्रथम-सर्च ट्री में {{mvar|v}} के सभी वंशजों के निकटवर्तियों की सबसे कम डेप्थ ({{mvar|v}} सहित) , जिसे {{math|'''lowpoint'''}} कहा जाता है। | # प्रत्येक शीर्ष {{mvar|v}} के लिए, डेप्थ-प्रथम-सर्च ट्री में {{mvar|v}} के सभी वंशजों के निकटवर्तियों की सबसे कम डेप्थ ({{mvar|v}} सहित), जिसे {{math|'''lowpoint'''}} कहा जाता है। | ||
डेप्थ प्रथम सर्च के समय बनाए रखने के लिए डेप्थ मानक है। {{mvar|v}} के निम्न बिंदु की गणना {{mvar|v}} के सभी वंशजों को (अर्थात, डेप्थ-प्रथम-सर्च स्टैक से {{mvar|v}} के पॉप अप होने से ठीक पहले) {{mvar|v}} की न्यूनतम डेप्थ, {{mvar|v}} के सभी निकटवर्तियों की डेप्थ (डेप्थ-प्रथम-सर्च ट्री में {{mvar|v}} के जनक के अतिरिक्त) और डेप्थ-प्रथम-सर्च वृक्ष में {{mvar|v}} के सभी बच्चों के निम्न बिंदु के रूप में जाने के बाद की जा सकती है। | डेप्थ प्रथम सर्च के समय बनाए रखने के लिए डेप्थ मानक है। {{mvar|v}} के निम्न बिंदु की गणना {{mvar|v}} के सभी वंशजों को (अर्थात, डेप्थ-प्रथम-सर्च स्टैक से {{mvar|v}} के पॉप अप होने से ठीक पहले) {{mvar|v}} की न्यूनतम डेप्थ, {{mvar|v}} के सभी निकटवर्तियों की डेप्थ (डेप्थ-प्रथम-सर्च ट्री में {{mvar|v}} के जनक के अतिरिक्त) और डेप्थ-प्रथम-सर्च वृक्ष में {{mvar|v}} के सभी बच्चों के निम्न बिंदु के रूप में जाने के बाद की जा सकती है। | ||
मुख्य तथ्य यह है कि एक गैर रूट शीर्ष {{mvar|v}} एक | मुख्य तथ्य यह है कि एक गैर रूट शीर्ष {{mvar|v}} एक प्रभाज शीर्ष (या संधि बिन्दु) है जो दो द्विसंबद्ध घटकों को अलग करता है यदि और मात्र यदि {{mvar|v}} का कोई बच्चा {{mvar|y}} है जैसे कि {{math|lowpoint(''y'') ≥ depth(''v'')}}। इस गुण का परीक्षण तब किया जा सकता है जब {{mvar|v}} के प्रत्येक बच्चे से डेप्थ-प्रथम सर्च वापस कर दी जाती है (अर्थात, {{mvar|v}} डेप्थ-फर्स्ट-सर्च स्टैक से पॉप अप होने से ठीक पहले), और यदि सत्य है, तो {{mvar|v}} आलेख़ को अलग-अलग द्विसंबद्ध घटकों में अलग कर देते है। इसे प्रत्येक ऐसे {{mvar|y}} में से एक द्विसंबद्ध घटक की गणना करके (एक घटक जिसमें {{mvar|y}} सम्मिलित है, में {{mvar|y}}, प्लस {{mvar|v}} का उपट्री सम्मिलित होगा), और फिर ट्री से {{mvar|y}} के उपट्री को मिटाकर प्रदर्शित किया जा सकता है। | ||
रूट शीर्ष को अलग से हैंडल किया जाना चाहिए: यह एक | रूट शीर्ष को अलग से हैंडल किया जाना चाहिए: यह एक प्रभाज शीर्ष है यदि और मात्र यदि इसके डीएफएस ट्री में कम से कम दो बच्चे हैं। इस प्रकार, रूट के प्रत्येक बच्चा उपट्री (रूट सहित) में से मात्र एक घटक बनाना पर्याप्त है। | ||
=== स्यूडोकोड === | === स्यूडोकोड === | ||
GetArticulationPoints(i, d) | GetArticulationPoints (i, d) | ||
visited[i] := '''true''' | visited[i] := '''true''' | ||
depth[i] := d | depth[i] := d | ||
| Line 32: | Line 32: | ||
'''if''' '''not''' visited[ni] '''then''' | '''if''' '''not''' visited[ni] '''then''' | ||
parent[ni] := i | parent[ni] := i | ||
GetArticulationPoints(ni, d + 1) | GetArticulationPoints (ni, d + 1) | ||
childCount := childCount + 1 | childCount := childCount + 1 | ||
'''if''' low[ni] ≥ depth[i] '''then''' | '''if''' low[ni] ≥ depth[i] '''then''' | ||
isArticulation := '''true''' | isArticulation := '''true''' | ||
low[i] := Min (low[i], low[ni]) | low[i] := Min (low[i], low[ni]) | ||
'''else if''' ni ≠ parent[i] '''then''' | '''else if''' ni ≠ parent[i] '''then''' | ||
low[i] := Min (low[i], depth[ni]) | low[i] := Min (low[i], depth[ni]) | ||
'''if''' (parent[i] ≠ '''null''' '''and''' isArticulation) '''or''' (parent[i] = '''null''' '''and''' childCount > 1) '''then''' | '''if''' (parent[i] ≠ '''null''' '''and''' isArticulation) '''or''' (parent[i] = '''null''' '''and''' childCount > 1) '''then''' | ||
Output i as articulation point | Output i as articulation point | ||
ध्यान दें कि बच्चे और माता-पिता डीएफएस ट्री में संबंधों को दर्शाते हैं, मूल आलेख नहीं।[[File:TarjanAPDemoDepth.gif|400px|thumb| | ध्यान दें कि बच्चे और माता-पिता डीएफएस ट्री में संबंधों को दर्शाते हैं, मूल आलेख नहीं।[[File:TarjanAPDemoDepth.gif|400px|thumb|प्रभाज सिरों को खोजने के लिए टार्जन के एल्गोरिदम का एक प्रदर्शन। D डेप्थ को दर्शाता है और L निम्न बिंदु को दर्शाता है।]] | ||
=== अन्य एल्गोरिदम === | === अन्य एल्गोरिदम === | ||
उपरोक्त एल्गोरिदम का | उपरोक्त एल्गोरिदम का सरल विकल्प [[श्रृंखला अपघटन]] का उपयोग करता है, जो डेप्थ-पहले सर्च-ट्री के आधार पर विशेष कान अपघटन हैं।<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 52: | Line 52: | ||
| year = 2013 | | year = 2013 | ||
| title = A Simple Test on 2-Vertex- and 2-Edge-Connectivity | | title = A Simple Test on 2-Vertex- and 2-Edge-Connectivity | ||
| volume = 113| arxiv = 1209.0700}}.</ref> इस ब्रिज (आलेख | | volume = 113| arxiv = 1209.0700}}.</ref> इस ब्रिज (आलेख सिद्धांत) नियम द्वारा श्रृंखला अपघटन की गणना रैखिक समय में की जा सकती है। {{mvar|C}} को {{mvar|G}} का एक श्रृंखला अपघटन होने दें। फिर {{mvar|G}} 2-शीर्ष -संबद्ध है यदि और मात्र यदि {{mvar|G}} न्यूनतम [[डिग्री (ग्राफ सिद्धांत)|डिग्री (आलेख सिद्धांत]]) 2 है और {{mvar|C}} में {{math|''C''{{sub|1}}}} एकमात्र [[चक्र (ग्राफ सिद्धांत)|चक्र (आलेख सिद्धांत]]) है। यह तुरंत रैखिक-समय 2-संबद्ध परीक्षण देते है और निम्न कथन का उपयोग करके रैखिक समय में {{mvar|G}} के सभी प्रभाज शीर्षों को सूचीबद्ध करने के लिए विस्तारित किया जा सकता है: संबद्ध आलेख {{mvar|G}} में एक शीर्ष {{mvar|v}} (न्यूनतम डिग्री 2 के साथ) प्रभाज शीर्ष है यदि और मात्र यदि {{mvar|v}} एक [[पुल (ग्राफ सिद्धांत)|पुल (आलेख सिद्धांत]]) के लिए घटना है या {{mvar|v}} {{math|''C'' – ''C''{{sub|1}}}} में एक चक्र का पहला शीर्ष है। रैखिक समय में {{mvar|G}} के कक्ष-प्रभाज ट्री को बनाने के लिए शीर्षों की सूची का उपयोग किया जा सकता है। | ||
समस्या के [[ ऑनलाइन एल्गोरिदम |ऑनलाइन एल्गोरिदम]] संस्करण में, कोने और किनारों को गतिशील रूप से जोड़ा जाता है ( | समस्या के [[ ऑनलाइन एल्गोरिदम |ऑनलाइन एल्गोरिदम]] संस्करण में, कोने और किनारों को गतिशील रूप से जोड़ा जाता है (परन्तु हटाया नहीं जाता है), और डेटा संरचना को द्विसंबद्ध घटकों को बनाए रखना चाहिए। [[जेफरी वेस्टब्रुक]] और रॉबर्ट टार्जन (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> [[असंयुक्त-सेट डेटा संरचना|असंयुक्त-समूह डेटा संरचनाओं]] के आधार पर इस समस्या के लिए कुशल डेटा संरचना विकसित की। विशेष रूप से, यह {{math|''O''(''m'' ''α''(''m'', ''n''))}} कुल समय में {{mvar|n}} शीर्ष जोड़ और {{mvar|m}} किनारा जोड़ संसाधित करता है, जहां {{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|''n'' + ''m''}} प्रोसेसर के साथ {{math|''O''(log ''n'')}} समय में चलते है। | ||
== संबंधित संरचनाएं == | == संबंधित संरचनाएं == | ||
=== तुल्यता संबंध === | === तुल्यता संबंध === | ||
यादृच्छिक अप्रत्यक्ष आलेख के किनारों पर एक [[द्विआधारी संबंध]] को परिभाषित कर सकते है, जिसके अनुसार दो किनारे {{mvar|e}} और {{mvar|f}} संबंधित हैं यदि और मात्र यदि {{math|1=''e'' = ''f''}} या आलेख़ में {{mvar|e}} और {{mvar|f}} दोनों के माध्यम से एक सरल चक्र होते है। प्रत्येक किनारा स्वयं से संबंधित है, और किनारा {{mvar|e}} दूसरे किनारे {{mvar|f}} से संबंधित है यदि और मात्र यदि {{mvar|f}} से इसी प्रकार से {{mvar|e}} से संबंधित है। कम स्पष्ट रूप से, यह एक [[सकर्मक संबंध]] है: यदि कोई सरल चक्र मौजूद है जिसमें किनारे {{mvar|e}} और {{mvar|f}} हैं, और अन्य सरल चक्र जिसमें किनारे {{mvar|f}} और {{mvar|g}} हैं, तो {{mvar|e}} और {{mvar|g}} के माध्यम से सरल चक्र खोजने के लिए इन दो चक्रों को जोड़ सकते हैं। इसलिए, यह एक [[तुल्यता संबंध]] है, और इसका उपयोग किनारों को तुल्यता वर्गों में विभाजित करने के लिए किया जा सकता है, किनारों के उपसमूह गुण के साथ कि दो किनारे एक दूसरे से संबंधित हैं यदि और मात्र यदि वे समान तुल्यता वर्ग से संबंधित हैं। प्रत्येक तुल्यता वर्ग में किनारों द्वारा गठित उपआलेख दिए गए आलेख के द्विसंबद्ध घटक हैं। इस प्रकार, द्विसंबद्ध घटक आलेख के किनारों को विभाजित करते हैं; यद्यपि, वे एक दूसरे के साथ शीर्ष साझा कर सकते हैं।<ref>{{harvtxt|Tarjan|Vishkin|1985}} credit the definition of this equivalence relation to {{harvtxt|Harary|1969}}; however, Harary does not appear to describe it in explicit terms.</ref> | |||
=== कक्ष आलेख === | === कक्ष आलेख === | ||
किसी दिए गए | किसी दिए गए आलेख {{mvar|G}} का कक्ष आलेख उसके कक्षों का प्रतिच्छेदन आलेख है। इस प्रकार, इसमें {{mvar|G}} के प्रत्येक कक्ष के लिए एक शीर्ष होता है, और दो शीर्षों के बीच एक किनारा होता है जब भी संबंधित दो कक्ष एक शीर्ष साझा करते हैं। आलेख {{mvar|H}} दूसरे आलेख {{mvar|G}} का कक्ष आलेख है, जब {{mvar|H}} के सभी कक्ष पूर्ण उपआलेख हैं। इस गुण वाले आलेख {{mvar|H}} को [[ब्लॉक ग्राफ|कक्ष आलेख]] के रूप में जाना जाता है।<ref>{{citation|first=Frank|last=Harary|author-link=Frank Harary|title=Graph Theory|publisher=Addison-Wesley|year=1969|page=29}}.</ref> | ||
=== कक्ष- | === कक्ष-प्रभाज ट्री === | ||
आलेख {{mvar|G}} का प्रभाज बिंदु, प्रभाज शीर्ष या संधि बिन्दु एक शीर्ष है जिसे दो या दो से अधिक कक्षों द्वारा साझा किया जाता है। संबद्ध आलेख़ के कक्ष और प्रभाज बिंदु की संरचना को एक ट्री (आलेख सिद्धांत) द्वारा वर्णित किया जा सकता है जिसे कक्ष-प्रभाज ट्री या बीसी-ट्री कहा जाता है। इस ट्री में प्रत्येक कक्ष के लिए और दिए गए आलेख के प्रत्येक संधि बिंदु के लिए एक शीर्ष है। कक्ष के प्रत्येक युग्म के लिए कक्ष-प्रभाज ट्री में एक किनारा होता है और उस कक्ष से संबंधित एक संधि बिन्दु होता है।<ref>{{harvtxt|Harary|1969}}, p. 36.</ref> | |||
[[File:Block-cut tree2.svg|800px|thumb|none| | [[File:Block-cut tree2.svg|800px|thumb|none|A graph, and its block-cut tree.'''Blocks''': | ||
''b''<sub>1</sub> = [1,2] | |||
''b''<sub>2</sub> = [2,3,4] | |||
''b''<sub>3</sub> = [2,5,6,7] | |||
''b''<sub>4</sub> = [7,8,9,10,11] | |||
''b''<sub>5</sub> = [8,12,13,14,15] | |||
''b''<sub>6</sub> = [10,16] | |||
''b''<sub>7</sub> = [10,17,18] | |||
'''Cutpoints:''' | |||
''c''<sub>1</sub> = 2 | |||
''c''<sub>2</sub> = 7 | |||
''c''<sub>3</sub> = 8 | |||
''c''<sub>4</sub> = 10]] | |||
== यह भी देखें == | == यह भी देखें == | ||
* | * त्रिसंबद्ध घटक | ||
* ब्रिज (आलेख सिद्धांत) | * ब्रिज (आलेख सिद्धांत) | ||
* निर्देशित रेखांकन में द्वि- | * निर्देशित रेखांकन में द्वि-संबद्ध घटकों का एकल-प्रविष्टि एकल-निकास प्रतिरूप | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== | ||
Revision as of 07:54, 21 April 2023
आलेख सिद्धांत में, एक द्विसंबद्ध घटक (कभी-कभी 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.
