बाइकनेक्टेड ग्राफ

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

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

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

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

इनपुट: ग्राफ का एडजेसेंसी मैट्रिक्स। 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 आउटपुट: ग्राफ एक बाइकनेक्टेड ग्राफ है।

एल्गोरिदम

isArticulation(start, visited, disc, low, parent)

इनपुट: स्टार्ट वर्टेक्स, विजिटेड ऐरे जब नोड विजिट हो जाए तो मार्क करने के लिए, डिस्क वर्टेक्स की डिस्कवरी टाइम रखेगा, और लो सबट्री के बारे में जानकारी रखेगा। पैरेंट वर्तमान वर्टेक्स का पैरेंट रखेगा।

आउटपुट - True यदि कोई आर्टिकुलेशन पॉइंट मिला

Begin 
  time := 0 //the value of time will not be initialized for next function calls 
  dfsChild := 0 
  mark start as visited 
  set disc[start] := time+1 and low[start] := time + 1 
  time := time + 1 
  for all vertex v in the graph G, do 
    if there is an edge between (start, v), then 
      if v is visited, then 
        increase dfsChild 
        parent[v] := start 
        if isArticulation(v, visited, disc, low, parent) is true, then 
          return ture 
        low[start] := minimum of low[start] and low[v] 
        if parent[start] is φ AND dfsChild > 1, then 
          return true 
        if parent[start] is φ AND low[v] >= disc[start], then 
          return true 
      else if v is not the parent of start, then 
        low[start] := minimum of low[start] and disc[v] 
  done 
  return false 
End

isBiconnected(graph)

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

आउटपुट - True यदि ग्राफ बाइ-कनेक्टेड है

Begin 
  initially set all vertices are unvisited and parent of each vertices are φ 
  if isArticulation(0, visited, disc, low, parent) = true, then 
    return false 
  for each node i of the graph, do 
    if i is not visited, then 
      return false 
  done 
  return true 
End

उदाहरण

#include #define NODE 5 using namespace std; int graph[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) { return (a 1) { //when u have 2 or more children return true; } if(parent[start] != -1 && low[v]>= disc[start]) return true; } else if(v != parent[start]) //update low of start for previous call low[start] = min(low[start], disc[v]); } } return false; } bool isBiConnected() { bool *vis = new bool[NODE]; int *disc = new int[NODE]; int *low = new int[NODE]; int *parent = new int[NODE]; for(int i = 0; i

आउटपुट
The Graph is a biconnected graph.