Connected and Biconnected Components

CONNECTED COMPONENT

A connected component of graph G is said to be a maximally connected induced subgraph. This means that it is a connected induced subgraph which is not a proper subgraph by itself of any other connected subgraph of G.

We can observe that the above Figure is a connected graph. The graph has only one connected component which is itself. Let us have a look at the following figure that is a graph with two connected components.

BICONNECTED COMPONENTS

Before getting into biconnected components let us first understand what an articulation point is exactly. An articulation point of a graph is a point or a vertex v, where v is a vertex such that when we remove the vertex v and all edges incident upon v, we end up breaking a connected component of the graph into two or more pieces.

A graph is said to be biconnected when we have a connected graph with no articulation points in it. One algorithm that is particularly useful in finding the biconnected components of a graph is Depth-first search.

However, the problem of finding the articulation points concerns the connectivity of graphs which is the simplest of many important problems. One of the examples of the applications of connectivity algorithms could be the following.

We may represent a communication network as a graph in where the vertices represent the sites to be kept in communication with each other.

Let us consider that a graph has connectivity k if the deletion of any k-1 vertices fails to disconnect the graph. A point to note down is that a graph is said to have connectivity two or more if and only if it has no articulation points, that is, if and only if it is biconnected.

As the connectivity of a graph increases, it is more likely that the graph is to survive the failure of some of its vertices. No matter if it is by the failure of the processing units at the vertices or an external attack.

Now, let us take a look into a simple depth-first search algorithm to find all the articulation points of a given connected graph, and thereby test their absence whether the graph is biconnected.

1. Firstly, we need to perform a depth-first search of the graph and compute the dfnumber [v] for each vertex v. Here, dfnumber orders the vertices as in a preorder traversal of the depth-first spanning tree.

2. Next, we compute low [v] for each vertex v, which is the smallest dfnumber of v or of any vertex y reachable from v by following down zero or more tree edges to a descendant x of v (x may be v) and then following a back edge (x, y). We compute low [v] for all the vertices v and visit the vertices in a postorder traversal. When we process v, we will be computing low [y] for every child y of vertex v. Here, low [v] should be considered to be the minimum of 

  i. dfnumber [v],

 ii. dfnumber [z] for any vertex z where there is a back edge (v, z)  

iii. And low [y] for any child y of v.

The articulation points are as follows:

1. The root is said to be an articulation point if and only if it has two or more children. There are no cross edges, hence the deletion of the root must disconnect the subtrees rooted at its children, as a disconnect {b, d, e} from {c, f, g}.

2. Any vertex v except the root node is said to be an articulation point if and only if there is some child y of v such that low [y] ≥ dfnumber [v]. In this case, v disconnects y and its descendants from the rest of the graph. On the other hand, if we have low [y] < dfnumber [v], then there must be a way to get y down from the tree and back to a proper ancestor of v (where v is the vertex whose dfnumber is low [y]), and therefore deletion of v does not disconnect y or its descendants from the rest of the graph.