An undirected graph is called Biconnected if there is a two vertex – disjoint ways between any two vertices. In a Biconnected Graph, there is a basic cycle through any two vertices.
By show, two hubs associated by an edge structure a biconnected graph, however, this doesn’t check the above properties. For a chart with in excess of two vertices, the above properties must be there for it to be Bi-connected.
Or in other words/way we can say that:
A graph is supposed to be Biconnected if:
- It is associated, for example, it is conceivable to arrive at each vertex from each other vertex, by a straightforward way.
- Even in the wake of eliminating any vertex the chart stays associated.
How to discover if a given graph is Biconnected or not?
A connected graph is Biconnected in the event that it is associated and doesn’t have any Articulation Point. We mostly need to check two things in it.
- It must be connected.
- There isn’t an articulation point in it.
We start from any vertex and do DFS crossing. In DFS crossing, we check if there is an articulation point. On the off chance that we don’t discover any articulation point, at that point the diagram is Biconnected. At last, we have to check if all vertices were reachable in DFS. In the event that all vertices were not reachable, at that point the graph isn’t associated or connected.
Time Complexity: The above capacity is a straightforward DFS with extra arrays. So time intricacy is same as DFS which is O(V+E) for nearness list portrayal of it.
Bridges in graph
An edge in an undirected connected graph is a scaffold if eliminating it disengages it. For a disengaged undirected graph, a definition is comparable, an extension is an edge eliminating which builds a number of detached segments.
Like Articulation Points, spans speak to weaknesses in an associated network and are helpful for planning dependable organisations. For instance, in a wired PC organisation, an explanation point shows the basic PCs and an extension demonstrates the basic wires or associations.
How to discover all bridges in a given graph?
A straightforward methodology is to individually eliminate all edges and check whether evacuation of an edge causes disengaged diagram. Following are steps of basic methodology for associated with it.
- For each edge (u, v), do following
- Remove (u, v) from a diagram
- See if the diagram stays associated (We can either utilise BFS or DFS)
- Add (u, v) back to the chart.
Time complexity of above method is O(E*(V+E)) if we are using the adjancy matrix.
We are going to do better this complexity, how?
The thought is like O(V+E) calculation for Articulation Points. We do DFS crossing of the given graph. In DFS tree an edge (u, v) (u is a parent of v in DFS tree) is connected if there doesn’t exist some other choice to arrive at u or a progenitor of u from subtree established with v. As examined in the past post, the worth low[v] demonstrates soonest visited vertex reachable from subtree established with v. The condition for an edge (u, v) to be a bridge is, “low[v] > disc[u]”.
Articulation Points
A vertex in an undirected associated chart is an articulation point if disposing of it (and edges through it) isolates the graph. Explanation focuses speak to weaknesses in an associated network – single focus whose disappointment would part the organisation into at least 2 segments. They are helpful for planning dependable organisations.
For a confined undirected chart, an explanation point is a vertex taking out which grows number of associated portions.
How to discover all articulation points in a given diagram?
A straightforward methodology is to individually eliminate all vertices and check whether the expulsion of a vertex causes disengaged diagram. Following are steps of basic methodology for the associated chart.
- For each vertex v, do the following
- Remove v from the graph
- See if the diagram stays associated (We can either utilise BFS or DFS)
- Add v back to the graph
The time complexity of the above technique is O(V*(V+E)) for a chart spoke to utilising contiguousness list. Would we be able to improve?
An O(V+E) calculation to discover all Articulation Points (APs). The thought is to utilise DFS (Depth First Search). In DFS, we follow vertices in a tree structure called the DFS tree. In DFS tree, a vertex u is a parent of another vertex v if v is found by u (clearly v is nearby of u in the diagram). In DFS tree, a vertex u is the exclamation point in the event that one of the accompanying two conditions is valid.
- u is the foundation of DFS tree and it has at any rate two kids.
- u isn’t the foundation of DFS tree and it has a youngster v to such an extent that no vertex in subtree established with v has a back edge to one of the precursors (in DFS tree) of u.
Way to write a C++ program to find if a given undirected graph is bi-connected
#include <iostream>
#include <list>
#define NIL -1
using namespace std;
// A class for representing an undirected graph
class Graph
{
int V; // Number of vertices
list *adj; // A dynamic array for adjacency list
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // to add an edge into the graph
bool isBC(); // returns true if the graph is fully Biconnected
};
Graph::Graph(int V)
{
this->V = V;
adj = new list[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v); // the graph is undirected
}
// A recursive function is that returns true if there is an articulation
// point in given graph, otherwise it returns false.
// This function almost same as isAPUtil() here ( http://goo.gl/Me9Fw )
// u –> The vertex to be visited next in the graph
// visited[] –> keeps tract of visited vertices in graph
// disc[] –> Stores discovery times of visited vertices in graph
// parent[] –> Stores the parent vertices in DFS tree
// A static variable that is used for simplicity, we can avoid use of static
// variable by passing the pointer.
static int time = 0;
// Counts the children in DFS Tree
int children = 0;
// Marks the current node as visited in code
visited[u] = true;
// Initialize the discovery time and low value
disc[u] = low[u] = ++time;
// Going through the all vertices adjacent to this
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
int v = *i; // v is a current adjacent of u
// If v is not visited yet, then we make it a child of u
// in DFS tree and recursion for it
if (!visited[v])
{
children++;
parent[v] = u;
// check if subgraph rooted with v has an articulation point in it
if(isBCUtil(v, visited, disc, low, parent))
return true;
// Check the subtree rooted with v has a connection to
// one of ancestors of u
low[u] = min(low[u], low[v]);
// u is articulation point in following case
// (1) u is root of DFS tree and can have two or more children.
if (parent[u] == NILL && children > 1)
return true;
// (2) If u is not the root and low value of one of its child is
// more than the discovery value of u.
if (parent[u] != NIL && low[v] >= disc[u])
return true;
}
// Update the low value of u for parent function call.
else if (v != parent[u])
low[u] = min(low[u], disc[v]);
}
return false; }
// The function that returns true if graph is Biconnected,
// otherwise it is false. It uses the recursion function isBCUtil()
bool Graph::isBC()
{
// Mark all the vertices as not visited in graph
bool *visited = new bool[V];
int *disc = new int[V];
int *low = new int[V];
int *parent = new int[V];
// Initialising the parent and visited, and ap(articulation point)
// array For (int i=0; i<V; i++)
{
parent[j] = NIL;
visited[j] = false;
}
// Call the function recursive helper function to find if there is an articulation
// point in given graph. We do the DFS traversal of graph starring from vertex 0 if ( isBCUtil (0, visited, disc, low,parent)==true)
return false;
// Now check whether the given graph is connected or not in manner. An undirected
// graph is connected if all vertices are reachable and also from any starting
// point (we have taken this 0 as starting point) for (int i=0; i<V; i++)
if (visited[j] == false)
return false;
return true; }
// Main function program to test above function
int main()
{
// Creating the graphs given in above diagrams
Graph g1(2);
g1.addEdge(0, 1);
g1.isBC()? cout << “done\n” : cout << “Not\n”;
Graph g2(5);
g2.addEdge(1, 0);
g2.addEdge(0, 2);
g2.addEdge(2, 1);
g2.addEdge(0, 3);
g2.addEdge(3, 4);
g2.addEdge(2, 4);
g2.isBC()? cout << "done\n" : cout << "Not\n";
Graph g3(3);
g3.addEdge(0, 1);
g3.addEdge(1, 2);
g3.isBC()? cout << "done\n" : cout << "Not\n";
Graph g4(5);
g4.addEdge(1, 0);
g4.addEdge(0, 2);
g4.addEdge(2, 1);
g4.addEdge(0, 3);
g4.addEdge(3, 4);
g4.isBC()? cout << "done\n" : cout << "Not\n";
Graph g5(3);
g5.addEdge(0, 1);
g5.addEdge(1, 2);
g5.addEdge(2, 0);
g5.isBC()? cout << "done\n" : cout << "Not\n";
return 0; }
To read more articles on Data Structures, click here.
By Akhil Sharma
