Card 03/ 07
Bridges and Articulation Points From Discovery Times and Low Values
A child whose subtree cannot climb above its parent without the tree edge marks that edge as a bridge.
A bridge is an edge whose removal splits a connected undirected graph into two parts, and an articulation point is a vertex whose removal does the same; one depth-first search finds both by recording two numbers for each vertex. The card defines the numbers, traces them on a graph of six vertices, and gives the two tests that turn them into verdicts.
Picture a road network where one bridge is the only way off an island: close it and the island is cut off. A graph bridge is the same single point of failure, a cable, a road or a dependency with no way round it. The picture breaks in one place. An island is visible on a map, while a graph of thousands of vertices shows no coastline, and its bridges are found only by the numbers below.
The graph has seven edges, A-B, B-C, C-A, B-D, D-E, E-B and E-F. A-B-C and B-D-E are triangles that share B, and F hangs off E.
A depth-first search from A walks a tree through the graph. Each vertex gets a discovery time, the count of vertices discovered before it: A is 0, B 1, and so on. An edge to an already discovered vertex other than the parent is a back edge, a second way up the tree. Each vertex's low value is the smallest discovery time its subtree can reach, going down tree edges and then up at most one back edge. A low value smaller than a vertex's own discovery time means its subtree has a route above it that does not use the edge from its parent.
The two tests compare a child's low value with its parent's discovery time:
- Bridge: the tree edge from parent to child is a bridge when low[child] > disc[parent]. Nothing below the child reaches the parent or higher except through that edge.
- Articulation point: a parent other than the root is an articulation point when low[child] ≥ disc[parent] for some child. The child's subtree can reach the parent but nothing above it, so removing the parent cuts the subtree off.
- The root has nothing above it, so it is an articulation point only when it has two or more children in the tree.
The table below gives each vertex's numbers from a run, with neighbours visited in the order the edges were listed.
| Vertex | Discovery | Low | Parent | Verdict |
|---|---|---|---|---|
| A | 0 | 0 | None, the root | One child, B, so not an articulation point |
| B | 1 | 0 | A | Child D has low 1 ≥ 1: an articulation point. B-D is not a bridge, since 1 is not greater than 1 |
| C | 2 | 0 | B | Back edge C-A reaches 0, so B-C is not a bridge |
| D | 3 | 1 | B | Child E has low 1, not ≥ 3: D is not an articulation point |
| E | 4 | 1 | D | Back edge E-B reaches 1. Child F has low 5 > 4: E-F is a bridge, and E an articulation point |
| F | 5 | 5 | E | No back edge; a leaf |
E-F is the only bridge, and B and E are the articulation points. B shows that the two verdicts are not the same thing: B is an articulation point with no bridge at it. Removing the edge B-D leaves D connected through E and the edge E-B, which is why low[D] equals disc[B]. Removing the vertex B takes both of those edges with it, and the triangle B-D-E loses its link to A and C.
The search visits each vertex and edge once, so both lists come out in O(V + E) time. A brute-force check that deletes each edge and each vertex in turn and counts the parts agreed with the run.
← → move through sections and cards