Understanding Articulation Points in a graph

Graphs can be directed or undirected in nature. Articulation points are quite important in a graph as they signal possible vulnerabilities in a given network. Removing a node from a connected undirected graph is likely to split the network into different components of an undirected graph. 

A simple illustration of articulation points 

The undirected graph below contains seven nodes and there are two articulation or critical points. Node B is very important to the network as it directly connects with five nodes. Removing node B will break this graph into three disconnected components. The three disconnected graphs after removing node B will be (A) , (C and D) and (E, F and G). The second articulation point on this graph is node C. A decision to remove node C will lead to two disconnected components which are nodes (A, B, E, F, G) and (D). This clearly shows that node B and C are the two articulation points with B being slightly more critical. Node B is the most critical because if removed it renders the remaining graphs into three disconnected components. On the other hand, removing vertex C splits the graph into two disconnected components.

Continue reading