Articulation points in a graph
What is an Articulation point
Articulation point means a vertex that is connected to a graph, if that vertex is removed from the graph, the graph will disconnect and separate into multiple components. This can be represented as follows,
Let’s remove the “D” from the graph
When “D” is removed from the graph the graph is split into 2 components called “ A, B, C ” and “ E, F ”. So, we can consider “D” as the articulation point for this graph.
Let’s assume this graph is acting like a computer network. If the computer called “D” is removed from this network, the whole network will be disconnected. To avoid this kind of problem we can connect “B” and “E” computers separately. Now, Although the “D” computer is removed from the network the network will not be disconnected. We can represent it as follows,
Algorithm to find articulation point
Steps
Prepare a DFS Spanning tree for the graph.
DFS Spanning tree for the above example is as follows,
Mention the DFS number for each vertex according to the visited path. (DFS number = d)
Find the lowest DFS number for each vertex
This can be found using the path to the parent vertex. Let’s assume we want to search for the lowest DFS number of “B”. For the “B”, the parent is “A”.
When starting from the “B”, the path is B->D->C and again to A. So, the lowest DFS number for “B” is 1. Because A’s DFS number equals to 1.
If we want to search for the lowest DFS number of “E”, For the “E” vertex, the parent is “D”.
When starting from the “E”, the path is E->F and again to D. So, the lowest DFS number for “E” is 3. Because D’s DFS number equals to 1.
Likewise, all the lowest numbers for the above scenario are as follows, (Lowest DFS number = L)
Find the articulation point using the below condition. If the condition became true, it is an articulation point
If there 2 vertices called “U” and “V”, U is the parent vertex and V is the child vertex.
According to the above scenario, Let’s take “B” and “D” vertices. Parent vertex is “B” and child vertex is “D”.
According to the condition,
Condition is false. So “B” is not an articulation point.
Again, Let’s check the “D” and “E” vertices. So, “D” is the parent vertex and “E” is the child vertex.
According to the condition,
Condition is true. So, “D” is an articulation point.
This condition is accepting all the vertices except the root vertex. If the root is an articulation point, we can identify it by checking the child vertices around the root vertex. If the root vertex is an articulation point, it will have two or more child vertices.