Bridges and articulation points

Back to two-way edges. Some lines of a network matter more than others: close one, and part of the network is cut off. One depth-first search, with the same low numbers as Tarjan’s method, finds every such line and every such station.

Weak points of a network

In an undirected graph:

• A bridge is an edge whose removal leaves more connected parts than before. In a railway, it is a line with no other way round it.
• An articulation point (or cut vertex) is a vertex whose removal, together with its edges, leaves more connected parts than before. The practice page calls it a cut station.

An edge is a bridge exactly when it lies on no cycle: if u–v is on a cycle, the rest of the cycle is another way from u to v; if it is on no cycle, there is no other way. The simple method removes each edge in turn and counts the parts again with a search: O(E · (V + E)). The method below does it all in one search, O(V + E).

Low numbers in an undirected search

Run a depth-first search and give each vertex its discovery number disc[v] (1, 2, 3, …). GRPH-3 showed that in an undirected search every edge is either a tree edge (it reached a new vertex) or a back edge (it joins a vertex to one above it on the path). There are no cross edges.

For each vertex v, let low[v] be the smallest discovery number that v’s subtree (v and everything below it in the search tree) can reach with one back edge. It is computed as the search returns:

low[u] = smallest of:
    disc[u]
    disc[w]   for each back edge u - w (not the edge u came by)
    low[v]    for each child v of u in the search tree

Step through the figure. The tags read disc/low.

The two rules, with proofs

If low[v] > disc[p], no back edge leaves v’s subtree to p or above it. The only edge between the subtree and the rest is p–v itself, so removing it cuts the subtree off. If low[v] ≤ disc[p], some back edge goes from the subtree to p or above; together with tree edges it makes a cycle through p–v, so p–v is not a bridge. Back edges are never bridges, for the same reason: each closes a cycle with tree edges.

If low[v] ≥ disc[p], the best v’s subtree can do is get back to p itself. Remove p, and nothing joins that subtree to the vertices above p (there are some, because p is not the start). If every child v has low[v] < disc[p], each child’s subtree has a back edge to a vertex above p, so removing p leaves every subtree joined to the part above p, and nothing is cut off.

The start is different. It has no vertices above it, so the rule above would mark it whenever it has any child. The start is a cut vertex exactly when it has two or more children in the search tree. Two children’s subtrees have no edge between them (there are no cross edges), so only the start joins them. With one child, removing the start leaves that one subtree whole. In the figure, A has one child, B, because C was reached through B.

The difference between the two tests is > against ≥. In the figure, low[E] = 4 = disc[D]: E’s part can get back to D, so D–E is on a cycle (D–E–F–D) and is no bridge, but it cannot get above D, so closing D cuts it off. A cut vertex need not touch any bridge, and the two ends of a bridge are cut vertices unless they have degree 1.

Repeated lines

The rule “skip the edge back to the parent” must skip the edge the search arrived by, not every edge to the parent vertex. With two lines between C and D (the figure’s second variant), the second line is a real second way: D’s low drops to C’s number, and neither line is a bridge. Skipping by parent vertex would miss this and report a bridge that is not there. So store each edge with its position in the list, and keep on the stack the position of the edge each vertex came by.

Cut vertices do not change: closing C closes both lines. A line from a vertex to itself joins nothing and is never a bridge; leave it out of the lists.

The search must not use recursion when paths can be long. Use the (vertex, iterator) stack again, with a third item: the edge the vertex came by. When the iterator on top runs out, pop it, and update the parent’s low and the two rules there. Now try CONN-P3, Weak points of the network.

Blocks, and the cheapest-tree link

• 2-edge-connected parts. Remove every bridge. The connected parts left are the largest groups of vertices with two separate ways (sharing no edge) between any two of them. Shrink each to a point, and the bridges form a forest: the bridge tree.
• Blocks. A block (a biconnected component) is a largest set of edges in which any two edges lie on a common cycle, or a single bridge on its own. Two blocks share at most one vertex, and that vertex is a cut vertex. The same search finds the blocks by keeping a stack of edges, and popping one block whenever the cut rule low[v] ≥ disc[p] holds.
• Menger’s theorem says the number of separate routes between two vertices equals the fewest edges (or vertices) whose removal splits them. Bridges are the case “one edge splits them”. FLOW-4 proves the general form with network flow.
• Edges in every cheapest tree. SPAN-4 said that an edge u–v of cost w is in every cheapest spanning tree when it is a bridge in the graph made of the edges of cost w between the groups formed by cheaper edges. That graph can have two edges between the same two groups, which is exactly why repeated lines must be handled as above.