Bi-Connected Graph
Bheekya D
Connected Components : Set of vertices which are reachable or is a sub-graph,
in which any two vertices are connected by paths and no vertices is connected
with any vertices in the super graph.
● Given graph, is important to find out the number of connected components to
analyze the structure of the graph – it has many real-life applications.
● We can use either DFS or BFS for this task.
Algorithm: Conneted-Componts(G)
{
count=0;
for(each vertex vi in graph G) do
{
if(flag[V]= = -1) {
DFS(V,flag)
Count++;
} Input: given the undirected graph
} Result: Print the number of connected components
return count;
}
DFS(int V, int flag) {
flag[V] = 1;
for(each adjacent node u of V )do
if(flag[u] = = -1) The key point to observe in the algorithm is that the
DFS(u, flag) number of connected components is equal to the number
} of independent DFS function calls.
Cut Vertex
● A single vertex whose removal disconnects a graph is called a cut-vertex.
● Let G be a connected graph. A vertex v of G is called a cut vertex of G, if G-v
(Remove v from G) results a disconnected graph.
● When we remove a vertex from a graph then graph will break into two or
more graphs. This vertex is called a cut vertex.
● A connected graph G may have
maximum (n-2) cut vertices.
Cut Edge (Bridge)
● A cut- Edge or bridge is a single edge whose removal
disconnects a graph.
● Let G be a connected graph. An edge e of G is called a
cut edge of G, if G-e (Remove e from G) results a
disconnected graph.
● When we remove an edge from a graph then graph will
break into two or more graphs. This removal edge is
called a cut edge or bridge.
● A connected graph G may have at most (n-1) cut edges.
Bi-Connected Graph
● An undirected graph is called Biconnected if there are two vertex-disjoint
paths between any two vertices. In a Biconnected Graph, there is a simple
cycle through any two vertices.
● A graph with more than two vertices, the above properties must be there for
it to be Biconnected.
● A graph is said to be Biconnected if:
○ It is connected, i.e. it is possible to reach every vertex from every other
vertex, by a simple path.
○ Even after removing any vertex the graph remains connected.
○ A graph is Bi-connected iff it contains no articulation points or cut
vertex.
Articulation Point
A vertex v in a connected graph G is an articulation point if and
only if the deletion of vertex v together with all edges incident to v
disconnects the graph into two or more non-empty component
A vertex whose removal increases the number of connected
components is called an articulation Point.
Articulation Point: example
6
1 5
2 7
4
3 8
1
9
0
Graph G
Develop an efficient algorithm to test whether a connected graph is
biconnected.
If the graph is not biconnected, then write an algorithm for identifying all
the articulation points in it.
If the graph is not biconnected, determine a set of edges whose
inclusion makes the graph biconnected.
To determine such a set of edges, we need to identify the maximal
Subgraph of G that are biconnected.
Bi-Connected Components(Bi-CC)
G' = (V',E') is a maximal biconnected subgraphs of G if and only if G
has no biconnected subgraph G" = (V", E") such that V' subset of V"
and E' subset of E".
A maximal biconnected subgraph is a biconnected components.
every biconnected component of a connected graph G contains at
least two vertices (unless G itself has only one vertex)
Lemma 6.1Two biconnected components can have at most one
vertex in common and this vertex is an articulation point.
6
1 5
2 7
4
3 8
1
9
0
Graph G
We have to add the new edges to the original graph to 6
convert the G into bi-connected component.
That we can do if we know the maximal sub-graphs of 5
1
G, that are bi-connected (they are G' = (V', E')). 5
4 2
● A maximal bi-connected sub-graph is a bi-connected 3 2 7
component.
3 3 8
1
9
0
Now, we have to develop an efficiant algorithm to test whether a connected
graph biconnected.
For the case of graphs that are not biconnected, this algorithm will identify all
the articulation points. Once it has been identified that a connected graph is
not biconnected, it may be desirable to determine a set of edges whose
inclusion makes the graph biconnected.
Now, Let us identify an articulation points(APs) and biconnected components of
the connected G with N≥2 vertices.
This can be done by considering the depth first spanning(dfs) tree of G,
because dfs have property that is very useful in identifying APs and biconnected
components.
6
1 5
2 7
4
3 8
1
9
0
Graph G Depth first spanning tree of G
Follow the rules to identify the APs using the dfs tree:
i) the root node of a dfs is an AP iff it has at least two children.
ii) no leaf nodes are the APs.
iii) other than the root and leaf nodes, any other node(let it be u) is an AP iff L[w]
≥dfn[u](w is child of u). Here L[u] is the lowest depth first number that can be
reached from u using a path of descendents followed by at most one back edge, but
this may not true for some u, which leads to calculate L[]s for all nodes and
identify the APs in the graph G if L[w]≥ dfn[u] is true for any child w of u.
So, we have efine the L[]s
L[] = min{dfn[u], min{L[w]| w is a child of u}, min{dfn[w] | (u,w) is a back edge}}
L[] = min{dfn[u], min{L[w]| w is a child of u}, min{dfn[w] | (u,w) is a back edge}}
Start from the leaf nodes to the L[]s.
L[10]= min{dfn[10], min{--}, min{--}}= 4.
L[9]= min{dfn[9], min{--}, min{--}}= 5.
L[6]= min{dfn[6], min{--}, min{--}}= 8.
L[8]= min{dfn[8], min{--}, min{6}}= 6.
L[7]= min{dfn[7], min{6}, min{6}}= 6.
L[5]= min{dfn[5], min{8, 6}, min{10}}= 6.
L[2]= min{dfn[2], min{6}, min{1}}= 1.
L[3]= min{dfn[3], min{4, 5, 1}, min{--}}= 1.
L[4]= min{dfn[4], min{1}, min{--}}= 1.
L[1:10]= {1, 1, 1, 1, 6, 8, 6, 6, 5, 4}
L[1]= min{dfn[1], min{1}, min{--}}= 1.
L values are L[1:10]= {1, 1, 1, 1, 6, 8, 6, 6, 5, 4}
rules to identify the APs using the dfs tree:
i) the root node is not an AP because it has no two children, hence, node-1 is not AP
ii) the leaf nodes 10, 9, 6, 8 are not APs.
iii) For any other nodes, if L[w]≥dfn[u] for any w, then u is an AP.
Node 7, 6≥9 is false, so node 7 is not a AP.
Node 5, 8≥7 if true, so node 8 is a AP
Node 3, 4≥3 and 5≥3, so node 3 is a AP
Node 4, 1≥2 , so node 4 is not a AP
Node 2, 6≥6 , so node 2 is AP
Node 1, 1≥1 , but, root node is an AP iff the root node of a depth first spanning
tree has two children.
Algorithm BiComp(u, v)
//u is a start vertex for depth first search. v is its parent if any in the depth first panning tree. It is assumed that the global array dfn is initially
//zero and that the global variable num is initialized to 1. n is the number of vertices in G
{
dfn[u]:= num; L[u]=num; num= num + 1;
for each vertex w adjacent from u do
{
if ((v ≠ w) and (dfn[w]<dfn[u)) then add (u, w) to the top of a stack s;
if (dfn[w] =0) then
{
BiComp(w, u); // w is unvişited.
L[u]= min(L[u], L[w]);
if (L[w] ≥ dfn[u]) then
{
write ("New bi-component");
repeat
{
Delete an edge from the top of stack s;
Let this edge be (x, y);
write (x, y);
} until (((x, y) = (u, w)) or ((x, y) = (w, u)));
}
}
elseif (w ≠ v) then L[u]=min(L[u], dfn[w]);
}
}
Example 2
Now consider the following graph and find the Aps and Bi-Connected Components.