I have been reading a book called The Algorithm Design Manual by Steven Skiena and one of the topics discussed there is an algorithm to find all the articulation points in a graph.
In it, we first construct a DFS tree and store the following information for each vertex in the DFS tree:
- The traversal order at which we visited the vertex
- The highest reachable ancestor from the tree for each vertex
After constructing the tree, the author says one of the following conditions need to be satisfied for a vertex to be an articulation vertex:
- If the root has more than 1 child, it is an articulation point
- If we have an edge
A -> B
which is a bridge, then A is an articulation point - If we have an edge
A -> B
(A is parent of B) and the highest reachable node from B is A, then A is an articulation point.
I wrote a program to test this and it works on the graphs I tested it against:
// lo[] contains highest index
// pre[] contains traversal order
private void dfsFindArticulationPoints(int node, int parent) {
if(pre[node] != 0) {
lo[parent] = Math.min(lo[parent], pre[node]);
return;
}
pre[node] = index;
lo[node] = index;
index++;
int childCount = 0;
for(int child: graph[node]) {
if(pre[child] != 0)
childCount++;
if(child == parent)
continue;
dfsFindArticulationPoints(child, node);
lo[node] = Math.min(lo[child], lo[node]);
// Check case 2 and 3
if(node != 0 && pre[node] <= lo[child])
articulationPoints.add(node);
}
// Check case 1
if(node == 0 && childCount > 1)
articulationPoints.add(0);
}
My Question: I understand why those three conditions work. However how can I convince myself that those are the only three conditions to check?
Can somebody please prove to me that those are the only three conditions and there are no other conditions to check for?