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.
Some steps in discovering articulation points
A standard way of finding the articulation point in a given graph is by removing each node one after the other. The goal is to determine if the elimination of a specific node will lead to the disconnection of the graph. Two common techniques utilised for finding articulation points and checking the connectivity of a graph is the DFS (Depth First Search) and BFS (Breadth First Search) approaches.
Step 1: Remove node v from the graph
Step 2: Determine the connectivity of the graph using BFS or DFS
Step 3: Restore node v back to the disconnected or connected graph.
DFS and BFS in articulation points
I’ve written an article on DFS and BFS but in this section will briefly look at how these two techniques are relevant to discovering articulation points. DFS uses an edge-based technique to traverse through a graph via a LIFO(Last in, First Out) approach. The visited nodes are added to a stack and the most recent vertex in the graph is removed for the continuation of the traversal. On the contrary, BFS adopts a node-based technique in finding the shortest path. When a vertex is visited, it is marked and added to the queue. Usually, nodes at the same horizontal level are first visited before progressing to the next tier. When a node is visited, it is added to a queue which is known for its FIFO (First in, First Out) strategy. BFS are considered to be slower than DFS in implementation.
DFS as a better option for Articulation points:
DFS can be viewed as a better traversal to prevent the disconnection of a graph. Compared to BFS, DFS pays better recognition to parent nodes which are sometimes the articulation points in a given graph.
The output of a BFS traversal for the above graph will be : R, A, B, C, D, E. With a queue based system, the source node of R will be removed from the node lists and that will result in the disconnection of the graph as node R is an articulation point.
On the other hand, with DFS, the source or origin node remains in the stack due to the LIFO method. The outcome in this case is R, A, E, B, C, D. The connected network will remain as the source node R is maintained. Unlike in BFS, a queue-based system implies the removal of an articulation node R. In the above example, there are two articulation vertices R and E.
From a business perspective, articulation points could be applicable to a telephone network where a critical connection between other units is disconnected. Or, a group of friends who are usually brought together by the same person in the group. Assuming the link between these friends goes travelling or is out of town, the social connection between these folks will go cold.
.