द्विसंबद्ध ग्राफ

एक अप्रत्यक्ष ग्राफ़ को एक द्विसंबद्ध ग्राफ़ कहा जाता है, यदि किन्हीं दो शीर्षों के बीच दो शीर्ष-असंबद्ध पथ मौजूद हों। दूसरे शब्दों में, हम कह सकते हैं कि किन्हीं दो शीर्षों के बीच एक चक्र होता है।

हम कह सकते हैं कि एक ग्राफ जी एक द्वि-जुड़ा हुआ ग्राफ है यदि यह जुड़ा हुआ है, और कोई जोड़ बिंदु नहीं हैं या ग्राफ में कट वर्टेक्स मौजूद हैं।

इस समस्या को हल करने के लिए, हम DFS ट्रैवर्सल का उपयोग करेंगे। डीएफएस का उपयोग करते हुए, हम यह पता लगाने की कोशिश करेंगे कि कोई अभिव्यक्ति बिंदु मौजूद है या नहीं। हम यह भी जांचते हैं कि डीएफएस द्वारा सभी शीर्षों का दौरा किया गया है या नहीं, यदि नहीं तो हम कह सकते हैं कि ग्राफ जुड़ा नहीं है।

इनपुट और आउटपुट

इनपुट:ग्राफ का आसन्न मैट्रिक्स।0 1 1 1 01 0 1 0 01 1 0 0 11 0 0 0 10 0 1 1 0आउटपुट:ग्राफ एक द्विसंबद्ध ग्राफ है।

एल्गोरिदम

आर्टिक्यूलेशन है (शुरू करें, देखे गए, डिस्क, कम, पैरेंट)

इनपुट: प्रारंभ शीर्ष, किसी नोड का दौरा करने पर चिह्नित करने के लिए विज़िट किया गया सरणी, डिस्क शीर्ष के खोज समय को बनाए रखेगा, और निम्न उप-प्रकारों के बारे में जानकारी रखेगा। पैरेंट वर्तमान शीर्ष के पैरेंट को धारण करेगा।

आउटपुट - सही है अगर कोई अभिव्यक्ति बिंदु पाया जाता है।

प्रारंभ समय:=0//अगले फ़ंक्शन कॉल dfsChild के लिए समय का मान प्रारंभ नहीं किया जाएगा:=0 चिह्नित सेट डिस्क के रूप में प्रारंभ करें [प्रारंभ]:=समय + 1 और निम्न [प्रारंभ]:=समय + 1 समय:=समय + 1 ग्राफ जी में सभी शीर्ष v के लिए, यदि (प्रारंभ, v) के बीच एक किनारा है, तो यदि v का दौरा किया जाता है, तो dfsChild माता-पिता को बढ़ाएँ [v] :=प्रारंभ करें यदि isArticulation(v, विज़िट किया गया) , डिस्क, लो, पैरेंट) सच है, तो रिटर्न ट्यूर लो [स्टार्ट]:=मिनिमम ऑफ़ लो [स्टार्ट] और लो [v] अगर पैरेंट [स्टार्ट] φ और dfsChild> 1 है, तो अगर पैरेंट [स्टार्ट] सही है तो रिटर्न करें। φ और निम्न है[v]>=डिस्क [प्रारंभ], फिर सही लौटें यदि v प्रारंभ का जनक नहीं है, तो निम्न [प्रारंभ] :=कम से कम [शुरू] और डिस्क [v] किया गया वापसी falseEnd 

 द्विसंबद्ध है(ग्राफ) 
 

 इनपुट: दिया गया ग्राफ।
 

 आउटपुट - सही है अगर ग्राफ़ द्वि-जुड़ा हुआ है।
 
प्रारंभ में सेट करें कि सभी कोने देखे नहीं गए हैं और प्रत्येक कोने के माता-पिता हैं यदि आर्टिक्यूलेशन (0, विज़िट, डिस्क, निम्न, माता-पिता) =सत्य है, तो ग्राफ़ के प्रत्येक नोड के लिए झूठी वापसी करें, यदि मैं नहीं जाता हूं तो करें , फिर असत्य हो गया वापस लौटें trueEnd
 
उदाहरण
 
#शामिल करें#नेमस्पेस एसटीडी का उपयोग करके नोड 5 परिभाषित करें;इंट ग्राफ[NODE][NODE] ={ {0, 1, 1, 1, 0}, {1, 0, 1, 0, 0}, { 1, 1, 0, 0, 0}, {1, 0, 0, 0, 1}, {0, 0, 0, 1, 0}}; int min(int a, int b) {रिटर्न (a 1) {// जब आपके 2 या अधिक बच्चे सही हो जाते हैं; } अगर (माता-पिता [शुरू]! =-1 &&कम [वी]> =डिस्क [शुरू]) सच वापस; } और अगर (वी! =माता-पिता [शुरू]) // पिछली कॉल के लिए कम शुरुआत का अद्यतन करें कम [शुरू] =मिनट (कम [शुरू], डिस्क [वी]); } } झूठी वापसी;} बूल isBiConnected () { बूल * विज़ =नया बूल [नोड]; इंट * डिस्क =नया इंट [नोड]; इंट * लो =नया इंट [नोड]; इंट * पैरेंट =नया इंट [नोड]; for(int i =0; i 
आउटपुट
 
ग्राफ़ एक द्विसंबद्ध ग्राफ़ है।