द्विसंबद्ध घटक: Difference between revisions

Latest revision as of 11:35, 26 April 2023

An example graph with biconnected components marked

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

आलेख सिद्धांत में, एक द्विसंबद्ध घटक (कभी-कभी 2-संबद्ध घटक के रूप में जाना जाता है) एक अधिकतम द्विसंबद्ध उपआलेख होता है। कोई भी संबद्ध (आलेख सिद्धांत) द्विसंबद्ध घटकों के ट्री (आलेख सिद्धांत) में विघटित हो जाते है जिसे आलेख़ का कक्ष-प्रभाज ट्री कहा जाता है। कक्ष एक दूसरे से साझा शीर्ष (आलेख सिद्धांत) से जुड़े होते हैं जिन्हें प्रभाज कोने या अलग-अलग कोने या संधि बिन्दु कहा जाता है। विशेष रूप से, एक प्रभाज शीर्ष कोई भी शीर्ष होता है जिसके हटाने से संबद्ध घटक (आलेख सिद्धांत) की संख्या बढ़ जाती है।^[1]

एल्गोरिदम

रैखिक समय डेप्थ-प्रथम सर्च

जॉन हॉपक्रॉफ्ट और रॉबर्ट टार्जन (1973) के कारण एक संबद्ध अप्रत्यक्ष आलेख में द्विसंबद्ध घटकों की गणना के लिए उत्कृष्ट अनुक्रमिक एल्गोरिदम है।^[2] यह रैखिक समय में चलता है, और डेप्थ प्रथम सर्च पर आधारित है। इस एल्गोरिदम को एल्गोरिदम के परिचय की समस्या 22-2 (दोनों 2 और 3 संस्करण) के रूप में भी रेखांकित किया गया है।

निम्नलिखित जानकारी को बनाए रखते हुए डेप्थ-प्रथम सर्च चलाने का विचार है:

डेप्थ-प्रथम-सर्च ट्री में प्रत्येक शीर्ष की डेप्थ (एक बार देखने के बाद), और
प्रत्येक शीर्ष $v$ के लिए, डेप्थ-प्रथम-सर्च ट्री में $v$ के सभी वंशजों के निकटवर्तियों की सबसे कम डेप्थ ( $v$ सहित), जिसे $lowpoint$ कहा जाता है।

डेप्थ प्रथम सर्च के समय बनाए रखने के लिए डेप्थ मानक है। $v$ के निम्न बिंदु की गणना $v$ के सभी वंशजों को (अर्थात, डेप्थ-प्रथम-सर्च स्टैक से $v$ के पॉप अप होने से ठीक पहले) $v$ की न्यूनतम डेप्थ, $v$ के सभी निकटवर्तियों की डेप्थ (डेप्थ-प्रथम-सर्च ट्री में $v$ के जनक के अतिरिक्त) और डेप्थ-प्रथम-सर्च वृक्ष में $v$ के सभी बच्चों के निम्न बिंदु के रूप में जाने के बाद की जा सकती है।

मुख्य तथ्य यह है कि एक गैर रूट शीर्ष $v$ एक प्रभाज शीर्ष (या संधि बिन्दु) है जो दो द्विसंबद्ध घटकों को अलग करता है यदि और मात्र यदि $v$ का कोई बच्चा $y$ है जैसे कि $lowpoint(y) \geq 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

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

प्रभाज सिरों को खोजने के लिए टार्जन के एल्गोरिदम का एक प्रदर्शन। D डेप्थ को दर्शाता है और L निम्न बिंदु को दर्शाता है।

अन्य एल्गोरिदम

उपरोक्त एल्गोरिदम का सरल विकल्प श्रृंखला अपघटन का उपयोग करता है, जो डेप्थ-पहले सर्च-ट्री के आधार पर विशेष कान अपघटन हैं।^[3] इस ब्रिज (आलेख सिद्धांत) नियम द्वारा श्रृंखला अपघटन की गणना रैखिक समय में की जा सकती है। $C$ को $G$ का एक श्रृंखला अपघटन होने दें। फिर $G$ 2-शीर्ष -संबद्ध है यदि और मात्र यदि $G$ न्यूनतम डिग्री (आलेख सिद्धांत) 2 है और $C$ में $C 1$ एकमात्र चक्र (आलेख सिद्धांत) है। यह तुरंत रैखिक-समय 2-संबद्ध परीक्षण देते है और निम्न कथन का उपयोग करके रैखिक समय में $G$ के सभी प्रभाज शीर्षों को सूचीबद्ध करने के लिए विस्तारित किया जा सकता है: संबद्ध आलेख $G$ में एक शीर्ष $v$ (न्यूनतम डिग्री 2 के साथ) प्रभाज शीर्ष है यदि और मात्र यदि $v$ एक पुल (आलेख सिद्धांत) के लिए घटना है या $v$ $C - C 1$ में एक चक्र का पहला शीर्ष है। रैखिक समय में $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]

A graph, and its block-cut tree.Blocks: b₁ = [1,2] b₂ = [2,3,4] b₃ = [2,5,6,7] b₄ = [7,8,9,10,11] b₅ = [8,12,13,14,15] b₆ = [10,16] b₇ = [10,17,18] Cutpoints: c₁ = 2 c₂ = 7 c₃ = 8 c₄ = 10

यह भी देखें

त्रिसंबद्ध घटक
ब्रिज (आलेख सिद्धांत)
निर्देशित रेखांकन में द्वि-संबद्ध घटकों का एकल-प्रविष्टि एकल-निकास प्रतिरूप

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

बाहरी संबंध

C++ implementation of Biconnected Components

[AL-TAIE_p.-1] 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)

[2] 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-3] 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.

[4] Westbrook, J.; Tarjan, R. E. (1992). "ब्रिज-कनेक्टेड और बाइकनेक्टेड घटकों को ऑनलाइन बनाए रखना". Algorithmica. 7 (1–6): 433–464. doi:10.1007/BF01758773.

[5] Tarjan, R.; Vishkin, U. (1985). "एक कुशल समानांतर बाइकनेक्टिविटी एल्गोरिथम". SIAM J. Comput. 14 (4): 862–874. CiteSeerX 10.1.1.465.8898. doi:10.1137/0214061.

[6] Tarjan & Vishkin (1985) credit the definition of this equivalence relation to Harary (1969); however, Harary does not appear to describe it in explicit terms.

[7] Harary, Frank (1969), Graph Theory, Addison-Wesley, p. 29.

[8] Harary (1969), p. 36.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
 {{Short description|Maximal biconnected subgraph}}
-{{confused|vertex cut}}
+{{confused|शीर्ष विभाजक}}
-[[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>
+[[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>
 == एल्गोरिदम ==
-=== रैखिक समय गहराई-पहली खोज ===
+=== रैखिक समय डेप्थ-प्रथम सर्च ===
-[[जॉन हॉपक्रॉफ्ट]] और [[रॉबर्ट टार्जन]] (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 संस्करण) के रूप में भी रेखांकित किया गया है।
+[[जॉन हॉपक्रॉफ्ट]] और [[रॉबर्ट टार्जन]] (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 संस्करण) के रूप में भी रेखांकित किया गया है।
-निम्नलिखित जानकारी को बनाए रखते हुए [[गहराई-पहली खोज]] चलाने का विचार है:
+निम्नलिखित जानकारी को बनाए रखते हुए [[गहराई-पहली खोज|डेप्थ-प्रथम सर्च]] चलाने का विचार है:
-# डेप्थ-फर्स्ट-सर्च ट्री में प्रत्येक शीर्ष की गहराई (एक बार देखने के बाद), और
+# डेप्थ-प्रथम-सर्च ट्री में प्रत्येक शीर्ष की डेप्थ (एक बार देखने के बाद), और
-# प्रत्येक शीर्ष के लिए {{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|y}} का {{mvar|v}} ऐसा है कि {{math|lowpoint(''y'') ≥ depth(''v'')}}. इस संपत्ति का परीक्षण तब किया जा सकता है जब प्रत्येक बच्चे से गहराई-पहली खोज वापस आ जाए {{mvar|v}} (यानी, ठीक पहले {{mvar|v}} डेप्थ-फ़र्स्ट-सर्च स्टैक से पॉप अप हो जाता है), और अगर सही है, {{mvar|v}} ग्राफ़ को अलग-अलग बाइकनेक्टेड घटकों में अलग करता है। इस तरह के प्रत्येक में से एक द्विसंबद्ध घटक की गणना करके इसका प्रतिनिधित्व किया जा सकता है {{mvar|y}} (एक घटक जिसमें शामिल है {{mvar|y}} का सबट्री होगा {{mvar|y}}, प्लस {{mvar|v}}), और उसके बाद के सबट्री को मिटा दें {{mvar|y}} पेड़ से।
+मुख्य तथ्य यह है कि एक गैर रूट शीर्ष {{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}} के उपट्री को मिटाकर प्रदर्शित किया जा सकता है।
-रूट वर्टेक्स को अलग से हैंडल किया जाना चाहिए: यह एक कट वर्टेक्स है अगर और केवल अगर इसके डीएफएस ट्री में कम से कम दो बच्चे हैं। इस प्रकार, रूट के प्रत्येक चाइल्ड सबट्री (रूट सहित) में से केवल एक घटक बनाना पर्याप्त है।
+रूट शीर्ष को अलग से हैंडल किया जाना चाहिए: यह एक प्रभाज शीर्ष है यदि और मात्र यदि इसके डीएफएस ट्री में कम से कम दो बच्चे हैं। इस प्रकार, रूट के प्रत्येक बच्चा उपट्री (रूट सहित) में से मात्र एक घटक बनाना पर्याप्त है।
 === स्यूडोकोड ===
-  <u>GetArticulationPoints(i, d)</u>
+  GetArticulationPoints (i, d)
-      देखा [i]: = सच
+      visited[i] := '''true'''
-      गहराई [i] := डी
+      depth[i] := d
-      कम [i] := डी
+      low[i] := d
-      बच्चे की गिनती: = 0
+      childCount := 0
-      isArticulation: = झूठा
+      isArticulation := '''false'''
-      adj [i] do में प्रत्येक ni के लिए
+      '''for each''' ni '''in''' adj[i] '''do'''
-         अगर नहीं देखा [नी] तो
-             अभिभावक [नी]: = मैं
-             GetArticulationPoints(ni, d + 1)
-             चाइल्डकाउंट := चाइल्डकाउंट + 1
-             अगर कम [नी] ≥ गहराई [i] तो
-                 आर्टिक्यूलेशन: = सच
-             कम [i] : = न्यूनतम (कम [i], कम [नी])
-         वरना अगर नी ≠ माता पिता [i] तो
-             कम [i] : = न्यूनतम (कम [i], गहराई [नी])
-     अगर (माता-पिता [i] ≠ अशक्त और आर्टिक्यूलेशन) या (माता-पिता [i] = अशक्त और चाइल्डकाउंट> 1) तो
-         आउटपुट i अभिव्यक्ति बिंदु के रूप में
-ध्यान दें कि बच्चे और माता-पिता डीएफएस पेड़ में संबंधों को दर्शाते हैं, मूल ग्राफ नहीं।
-<दिव>[[File:TarjanAPDemoDepth.gif|400px|thumb|कटे हुए सिरों को खोजने के लिए टार्जन के एल्गोरिद्म का एक डेमो। D गहराई को दर्शाता है और L निम्न बिंदु को दर्शाता है।]]</div>
+         '''if''' '''not''' visited[ni] '''then'''
-<br>
+             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
+ध्यान दें कि बच्चे और माता-पिता डीएफएस ट्री में संबंधों को दर्शाते हैं, मूल आलेख नहीं।[[File:TarjanAPDemoDepth.gif|400px|thumb|प्रभाज  सिरों को खोजने के लिए टार्जन के एल्गोरिदम का एक  प्रदर्शन। D डेप्थ को दर्शाता है और L निम्न बिंदु को दर्शाता है।]]
 === अन्य एल्गोरिदम ===
-उपरोक्त एल्गोरिथ्म का एक सरल विकल्प [[श्रृंखला अपघटन]] का उपयोग करता है, जो गहराई-पहले खोज-वृक्षों के आधार पर विशेष कान अपघटन हैं।<ref name="Schmidt">{{citation
+उपरोक्त एल्गोरिदम का सरल विकल्प [[श्रृंखला अपघटन]] का उपयोग करता है, जो डेप्थ-पहले सर्च-ट्री के आधार पर विशेष कान अपघटन हैं।<ref name="Schmidt">{{citation
   | last = Schmidt | first = Jens M. | author-link = Jens M. Schmidt
   | doi = 10.1016/j.ipl.2013.01.016
@@ Line 54: / Line 52: @@
   | year = 2013
   | title = A Simple Test on 2-Vertex- and 2-Edge-Connectivity
-  | volume = 113| arxiv = 1209.0700}}.</ref> इस ब्रिज (ग्राफ थ्योरी) #Bridge-Finding with Chain Decompositions द्वारा चेन डीकंपोज़िशन की गणना रैखिक समय में की जा सकती है। होने देना {{mvar|C}} की एक श्रृंखला अपघटन हो {{mvar|G}}. तब {{mvar|G}} 2-वर्टेक्स-कनेक्टेड है अगर और केवल अगर {{mvar|G}} न्यूनतम [[डिग्री (ग्राफ सिद्धांत)]] 2 और है {{math|''C''{{sub|1}}}} में एकमात्र [[चक्र (ग्राफ सिद्धांत)]] है {{mvar|C}}. यह तुरंत एक रैखिक-समय 2-कनेक्टिविटी परीक्षण देता है और सभी कटे हुए शीर्षों को सूचीबद्ध करने के लिए बढ़ाया जा सकता है {{mvar|G}} निम्न कथन का उपयोग करते हुए रैखिक समय में: एक शीर्ष {{mvar|v}} एक जुड़े ग्राफ में {{mvar|G}} (न्यूनतम डिग्री 2 के साथ) एक कट वर्टेक्स है अगर और केवल अगर {{mvar|v}} एक [[पुल (ग्राफ सिद्धांत)]] या के लिए घटना है {{mvar|v}} चक्र का पहला शीर्ष है {{math|''C'' – ''C''{{sub|1}}}}. कटे हुए शीर्षों की सूची का उपयोग द्विसंबद्ध घटक#ब्लॉक-कट ट्री|का ब्लॉक-कट ट्री बनाने के लिए किया जा सकता है {{mvar|G}} रैखिक समय में।
+  | 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> [[असंयुक्त-सेट डेटा संरचना]]ओं के आधार पर इस समस्या के लिए एक कुशल डेटा संरचना विकसित की। विशेष रूप से, यह प्रक्रिया करता है {{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> [[असंयुक्त-सेट डेटा संरचना|असंयुक्त-समूह डेटा संरचनाओं]] के आधार पर इस समस्या के लिए कुशल डेटा संरचना विकसित की। विशेष रूप से, यह {{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 [[समानांतर रैंडम-एक्सेस मशीन]] पर एक समानांतर एल्गोरिथ्म डिज़ाइन किया गया है जो अंदर चलता है {{math|''O''(log ''n'')}} इसके साथ समय {{math|''n'' + ''m''}} प्रोसेसर।
+[[उजी विस्किन]] और रॉबर्ट टार्जन (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|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.&nbsp;36.</ref>
+[[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
-किसी दिए गए ग्राफ का ब्लॉक ग्राफ {{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>
+''c''<sub>2</sub> = 7
-=== ब्लॉक-कट ट्री ===
+''c''<sub>3</sub> = 8
-एक ग्राफ का कटपॉइंट, कट वर्टेक्स या आर्टिक्यूलेशन पॉइंट {{mvar|G}} एक वर्टेक्स है जिसे दो या दो से अधिक ब्लॉकों द्वारा साझा किया जाता है। कनेक्टेड ग्राफ़ के ब्लॉक और कटप्वाइंट की संरचना को एक ट्री (ग्राफ़ थ्योरी) द्वारा वर्णित किया जा सकता है जिसे ब्लॉक-कट ट्री या बीसी-ट्री कहा जाता है। इस पेड़ में प्रत्येक ब्लॉक के लिए और दिए गए ग्राफ के प्रत्येक अभिव्यक्ति बिंदु के लिए एक शीर्ष है। ब्लॉक के प्रत्येक जोड़े के लिए ब्लॉक-कट ट्री में एक किनारा होता है और उस ब्लॉक से संबंधित एक आर्टिक्यूलेशन पॉइंट होता है।<ref>{{harvtxt|Harary|1969}}, p.&nbsp;36.</ref>
-[[File:Block-cut tree2.svg|800px|thumb|none|एक ग्राफ, और उसका ब्लॉक-कट ट्री।<br/>ब्लॉक: <br/>
+''c''<sub>4</sub> = 10]]
-{{math|1=''b''{{sub|1}} = [1,2]}} <br/>
-{{math|1=''b''{{sub|2}} = [2,3,4]}} <br/>
-{{math|1=''b''{{sub|3}} = [2,5,6,7]}} <br/>
-{{math|1=''b''{{sub|4}} = [7,8,9,10,11]}} <br/>
-{{math|1=''b''{{sub|5}} = [8,12,13,14,15]}} <br/>
-{{math|1=''b''{{sub|6}} = [10,16]}} <br/>
-{{math|1=''b''{{sub|7}} = [10,17,18]}} <br/> कटपॉइंट्स: <br/>
-{{math|1=''c''{{sub|1}} = 2}} <br/>
-{{math|1=''c''{{sub|2}} = 7}} <br/>
-{{math|1=''c''{{sub|3}} = 8}} <br/>
-{{math|1=''c''{{sub|4}} = 10}}]]
 == यह भी देखें ==
-* त्रिकोणीय घटक
+* त्रिसंबद्ध घटक
-* ब्रिज (ग्राफ सिद्धांत)
+* ब्रिज (आलेख सिद्धांत)
-* निर्देशित रेखांकन में द्वि-जुड़े घटकों का एकल-प्रविष्टि एकल-निकास काउंटर भाग
+* निर्देशित रेखांकन में द्वि-संबद्ध घटकों का एकल-प्रविष्टि एकल-निकास प्रतिरूप
 ==टिप्पणियाँ==
@@ Line 112: / Line 122: @@
 * [http://www.geeksforgeeks.org/biconnected-components/ C++ implementation of Biconnected Components]
-{{DEFAULTSORT:Biconnected Component}}[[Category: ग्राफ कनेक्टिविटी]] [[Category: स्यूडोकोड के उदाहरण वाले लेख]]
+{{DEFAULTSORT:Biconnected Component}}
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Biconnected Component]]
-[[Category:Created On 28/02/2023]]
+[[Category:Created On 28/02/2023|Biconnected Component]]
+[[Category:Lua-based templates|Biconnected Component]]
+[[Category:Machine Translated Page|Biconnected Component]]
+[[Category:Pages with script errors|Biconnected Component]]
+[[Category:Templates Vigyan Ready|Biconnected Component]]
+[[Category:Templates that add a tracking category|Biconnected Component]]
+[[Category:Templates that generate short descriptions|Biconnected Component]]
+[[Category:Templates using TemplateData|Biconnected Component]]
+[[Category:ग्राफ कनेक्टिविटी|Biconnected Component]]
+[[Category:स्यूडोकोड के उदाहरण वाले लेख|Biconnected Component]]

Anonymous

Search

द्विसंबद्ध घटक: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 11:35, 26 April 2023

Contents

एल्गोरिदम

रैखिक समय डेप्थ-प्रथम सर्च

स्यूडोकोड

अन्य एल्गोरिदम

संबंधित संरचनाएं

तुल्यता संबंध

कक्ष आलेख

कक्ष-प्रभाज ट्री

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

द्विसंबद्ध घटक: Difference between revisions

Latest revision as of 11:35, 26 April 2023

एल्गोरिदम

रैखिक समय डेप्थ-प्रथम सर्च

स्यूडोकोड

अन्य एल्गोरिदम

संबंधित संरचनाएं

तुल्यता संबंध

कक्ष आलेख

कक्ष-प्रभाज ट्री

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories