Finding the Articulation point
What is the articulation point? Simply, an articulation point is a vertex in the graph that if that articulation point were removed, the graph would get disconnected and split into multiple graphs. In other words, we can identify articulation points as Critical points in the graph.
Let's look into the example for more understanding.
The following graph represents the ATM machine network. All the vertexes are ATM machines, and all the lines are the connections between the ATM machines.
According to this diagram, there are critical atm machines. If we assumed one of those ATM machines had stopped working, it could cause the entire network to fail. In this graph, Let’s assume we remove the C ATM machine. If we remove the C ATM machine, the network will be split into two parts. C Atm serves as a network communication bridge. If C stops working, A, D, and B may work independently, and E, F, G, H, I work independently. So C is working as a critical point in this system to keep all the nodes connected.
In these scenarios, to find the articulation point programmatically, we need to use the DFS spanning tree. A DFS spanning tree means selecting one node and travel through the graph using the DFS algorithm and draw a tree. After finishing the drawing, we can see that there are edges drawn in single lines and the back edges are drawn in dashed lines. Then we need to mark the value of the depth of each vertex. D is the value of the depth. Then we need to find out what the lowest depth we can reach is from each vertex. But there is a rule when finding the lowest depth you can reach. To travel to the lowest depth, only one back edge can be used. The following table shows the depth and the lowest depth of each vertex.
After calculating depth and lowest depth we can find articulation points using the following formula.
l(v) >/ d(u)
u = “u” is the parent vertex
v = “v” is child vertex
l(v) = Lowest value of the child
d(u) = depth index of the parent
If this formula is TRUE ‘u’ is an articulation point.
Let's take C and E as an example
l(v) = 3
d(u) = 3
so in this example formula is true. Then we can say “c” is an articulation point.
Following is the algorithm implementation of articulation point finding.
REFERENCE
[1]K. Dinesh, “ATM Problem,” 08-Apr-2022. [Online]. Available: https://www.youtube.com/watch?v=pmt8hXL1df8. [Accessed: 12-Apr-2022].
[2]“Articulation points (or cut vertices) in a graph,” GeeksforGeeks, 21-May-2013. [Online]. Available: https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/. [Accessed: 12-Apr-2022].
