Articulation Point
Let G= (V, E) be a connected undirected graph. An articulation point (or cut vertex) of G is a vertex whose removal disconnects G. In other words a vertex v is an articulation point if removing v increases the number of connected components. Nodes having color red in below graph are articulation points.
The easiest solution is to remove a vertex (and its corresponding edges) one by one from G and test whether the resulting graph is still connected or not (say by DFS). The running time is O(V * (V+E).
In DFS tree, a vertex u is articulation point if one of the following two conditions is true.
- u is root of DFS tree and it has at least two children.
- u is not root of DFS tree and it has a child v such that no vertex in subtree rooted with v has a back edge to one of the ancestors (in DFS tree) of u.
To find the articulation point, We make use of the discovery time in the DFS tree. Observe that if we follow a path from an ancestor to a descendant, the discovery time is in increasing order. If there is a subtree rooted at a children of v which does not have a back edge connecting to a SMALLER discovery time than discover[v], then v is an articulation point. Using Low[v] we can find if a subtree has a back edge climbing to an upper part of the tree, where Low[v] is the smallest value of a subtree rooted at v to which it can climb up by a back edge.
Low[v] =min (discover[v], discover[w] ): (u, w) is a back edge for some descendant u of v.
Bridge
An edge is called bridge if removing it from the graph (while keeping the vertices) increases the number of connected components. Important points
- A bridge is part of every spanning tree.
- If u is parent of v in a rooted spanning tree, then uv is a bridge if and only if every vertex reachable from v not using u is a descendant of v.
