PK

PKBytes

Explore tracks
Chapter 38: Connectivity, Bridges, Articulation Points and SCCs
38.06Intermediate / Advanced4 topics14 min4 interactive animations

Graph robustness

Robustness asks how much damage a graph can take. Removal tests give the definitions of bridges and cut vertices, and the bridge tree tells how many edges must be added to survive any single link failure.

Learning goals

  • Test bridges and cut vertices by removal and compare with low-link
  • Count the edges needed to make a connected graph 2-edge-connected
  • State what 2-edge-connected and biconnected mean and how they differ

Prerequisites

BridgesArticulation points

A network is robust if no single failure splits it. Before trusting a clever linear-time algorithm it helps to see the slow, obviously correct definition: break each link, one at a time, and count the pieces.

38.06.1

Bridge removal

The definition-level test is simple: count the connected components, remove one edge, count again. If the number rose, the edge is a bridge. Doing this for every edge costs O(m · (n + m)), against O(n + m) for low-link, but it is a reliable reference to test the fast version against.

Run the “Remove each edge: two cycles and a bridge” preset: of 7 edges only 2-3 raises the count from 1 to 2, the other six leave one component. On the “Remove each edge: disconnected” preset the graph already has 2 components; the path edges 0-1 and 1-2 each raise the count to 3, the triangle edges do not, so the answer is 2 bridges.

Count components with union-find, skipping the removed edge. Vertices are the same on both sides of the comparison, so only the count of components changes.

Java
1static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
2
3static int components(int n, int[][] edges, int skipEdge, int skipVertex) {   // -1 means "skip nothing"
4    int[] p = new int[n];
5    for (int i = 0; i < n; i++) p[i] = i;
6    for (int k = 0; k < edges.length; k++) {
7        int a = edges[k][0], b = edges[k][1];
8        if (k == skipEdge || a == skipVertex || b == skipVertex) continue;
9        p[find(p, a)] = find(p, b);
10    }
11    int count = 0;
12    for (int v = 0; v < n; v++) if (v != skipVertex && find(p, v) == v) count++;
13    return count;
14}
15
16static List<Integer> bridgesByRemoval(int n, int[][] edges) {
17    int base = components(n, edges, -1, -1);
18    List<Integer> out = new ArrayList<>();
19    for (int k = 0; k < edges.length; k++)
20        if (components(n, edges, k, -1) > base) out.add(k);          // removing edge k splits a component
21    return out;
22}

Robustness: remove an edge or vertex, and how many edges to add

Interactive · edit the input

Your input

Try

undirected graph · 6 vertices · 7 edges

0
1
2
3
4
5
Removed edge or vertexIts removal splits the graphComponent 1Component 2

edges whose removal splits the graph

none yet
Setup

The graph starts with 1 component. Remove each edge in turn and count components again: if the count rises, that edge is a bridge. This brute force is O(m·(n+m)); the low-link DFS does it in O(n+m).

Step 1 / 9
Java
1static int components(int n, int[][] edges, int skipEdge, int skipVertex) {   // -1 means "skip nothing"
2    int[] p = new int[n];
3    for (int i = 0; i < n; i++) p[i] = i;
4    for (int k = 0; k < edges.length; k++) {
5        int a = edges[k][0], b = edges[k][1];
6        if (k == skipEdge || a == skipVertex || b == skipVertex) continue;
7        p[find(p, a)] = find(p, b);
8    }
9    int count = 0;
10    for (int v = 0; v < n; v++) if (v != skipVertex && find(p, v) == v) count++;
11    return count;
12}
13static List<Integer> bridgesByRemoval(int n, int[][] edges) {
14    int base = components(n, edges, -1, -1);
15    List<Integer> out = new ArrayList<>();
16    for (int k = 0; k < edges.length; k++)
17        if (components(n, edges, k, -1) > base) out.add(k);      // removing edge k splits a component
18    return out;
19}
20static List<Integer> articulationByRemoval(int n, int[][] edges) {
21    int base = components(n, edges, -1, -1);
22    List<Integer> out = new ArrayList<>();
23    for (int v = 0; v < n; v++)
24        if (components(n, edges, -1, v) > base) out.add(v);      // removing vertex v splits its component
25    return out;
26}
27static int edgesToMakeBridgeless(int n, int[][] edges) {         // connected graph: edges to add so no bridge remains
28    boolean[] isBridge = new boolean[edges.length];
29    for (int k : bridgesByRemoval(n, edges)) isBridge[k] = true;
30    int[] p = new int[n];
31    for (int i = 0; i < n; i++) p[i] = i;
32    for (int k = 0; k < edges.length; k++) if (!isBridge[k]) p[find(p, edges[k][0])] = find(p, edges[k][1]);
33    int[] degree = new int[n];                                   // degree in the bridge tree
34    for (int k = 0; k < edges.length; k++)
35        if (isBridge[k]) { degree[find(p, edges[k][0])]++; degree[find(p, edges[k][1])]++; }
36    int leaves = 0;
37    for (int v = 0; v < n; v++) if (find(p, v) == v && degree[v] == 1) leaves++;
38    return (leaves + 1) / 2;                                     // every leaf needs a new edge; one edge serves two leaves
39}

Live state

0 checks0 bridges

components

1

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L14components=1The graph starts with 1 component. Remove each edge in turn and count components again: if the count rises, that edge is a bridge. This brute force is O(m·(n+m)); the low-link DFS does it in O(n+m).
2L17edge=0-1 components=1 base=1Remove 0-1: 1 component (was 1). The count did not rise: another route connects its ends.
3L17edge=1-2 components=1 base=1Remove 1-2: 1 component (was 1). The count did not rise: another route connects its ends.
4L17edge=2-0 components=1 base=1Remove 2-0: 1 component (was 1). The count did not rise: another route connects its ends.
5L17edge=3-4 components=1 base=1Remove 3-4: 1 component (was 1). The count did not rise: another route connects its ends.
6L17edge=4-5 components=1 base=1Remove 4-5: 1 component (was 1). The count did not rise: another route connects its ends.
7L17edge=5-3 components=1 base=1Remove 5-3: 1 component (was 1). The count did not rise: another route connects its ends.
8L17edge=2-3 components=2 base=1Remove 2-3: 2 components (was 1). The count rose: it is a bridge.
9L18return=11 bridge: 2-3.
38.06.2

Articulation removal

The same idea works for vertices: remove a vertex together with its edges, then count the components of the **remaining** vertices. If that count is higher than before, the vertex is an articulation point.

Be careful with isolated vertices: removing one leaves the others untouched and lowers the count by one, so it is not an articulation point. In the “Remove each vertex: bowtie” preset, removing vertex 2 leaves {0, 1} and {3, 4}: 2 components against 1 before. Every other vertex leaves one component.

Use this brute force on small inputs as an oracle; for the real graph use the DFS of the previous lesson.

Java
1static List<Integer> articulationByRemoval(int n, int[][] edges) {
2    int base = components(n, edges, -1, -1);
3    List<Integer> out = new ArrayList<>();
4    for (int v = 0; v < n; v++)
5        if (components(n, edges, -1, v) > base) out.add(v);          // removing v splits its component
6    return out;
7}

Robustness: remove an edge or vertex, and how many edges to add

Interactive · edit the input

Your input

Try

undirected graph · 6 vertices · 7 edges

0
1
2
3
4
5
Removed edge or vertexIts removal splits the graphComponent 1Component 2

edges whose removal splits the graph

none yet
Setup

The graph starts with 1 component. Remove each edge in turn and count components again: if the count rises, that edge is a bridge. This brute force is O(m·(n+m)); the low-link DFS does it in O(n+m).

Step 1 / 9
Java
1static int components(int n, int[][] edges, int skipEdge, int skipVertex) {   // -1 means "skip nothing"
2    int[] p = new int[n];
3    for (int i = 0; i < n; i++) p[i] = i;
4    for (int k = 0; k < edges.length; k++) {
5        int a = edges[k][0], b = edges[k][1];
6        if (k == skipEdge || a == skipVertex || b == skipVertex) continue;
7        p[find(p, a)] = find(p, b);
8    }
9    int count = 0;
10    for (int v = 0; v < n; v++) if (v != skipVertex && find(p, v) == v) count++;
11    return count;
12}
13static List<Integer> bridgesByRemoval(int n, int[][] edges) {
14    int base = components(n, edges, -1, -1);
15    List<Integer> out = new ArrayList<>();
16    for (int k = 0; k < edges.length; k++)
17        if (components(n, edges, k, -1) > base) out.add(k);      // removing edge k splits a component
18    return out;
19}
20static List<Integer> articulationByRemoval(int n, int[][] edges) {
21    int base = components(n, edges, -1, -1);
22    List<Integer> out = new ArrayList<>();
23    for (int v = 0; v < n; v++)
24        if (components(n, edges, -1, v) > base) out.add(v);      // removing vertex v splits its component
25    return out;
26}
27static int edgesToMakeBridgeless(int n, int[][] edges) {         // connected graph: edges to add so no bridge remains
28    boolean[] isBridge = new boolean[edges.length];
29    for (int k : bridgesByRemoval(n, edges)) isBridge[k] = true;
30    int[] p = new int[n];
31    for (int i = 0; i < n; i++) p[i] = i;
32    for (int k = 0; k < edges.length; k++) if (!isBridge[k]) p[find(p, edges[k][0])] = find(p, edges[k][1]);
33    int[] degree = new int[n];                                   // degree in the bridge tree
34    for (int k = 0; k < edges.length; k++)
35        if (isBridge[k]) { degree[find(p, edges[k][0])]++; degree[find(p, edges[k][1])]++; }
36    int leaves = 0;
37    for (int v = 0; v < n; v++) if (find(p, v) == v && degree[v] == 1) leaves++;
38    return (leaves + 1) / 2;                                     // every leaf needs a new edge; one edge serves two leaves
39}

Live state

0 checks0 bridges

components

1

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L14components=1The graph starts with 1 component. Remove each edge in turn and count components again: if the count rises, that edge is a bridge. This brute force is O(m·(n+m)); the low-link DFS does it in O(n+m).
2L17edge=0-1 components=1 base=1Remove 0-1: 1 component (was 1). The count did not rise: another route connects its ends.
3L17edge=1-2 components=1 base=1Remove 1-2: 1 component (was 1). The count did not rise: another route connects its ends.
4L17edge=2-0 components=1 base=1Remove 2-0: 1 component (was 1). The count did not rise: another route connects its ends.
5L17edge=3-4 components=1 base=1Remove 3-4: 1 component (was 1). The count did not rise: another route connects its ends.
6L17edge=4-5 components=1 base=1Remove 4-5: 1 component (was 1). The count did not rise: another route connects its ends.
7L17edge=5-3 components=1 base=1Remove 5-3: 1 component (was 1). The count did not rise: another route connects its ends.
8L17edge=2-3 components=2 base=1Remove 2-3: 2 components (was 1). The count rose: it is a bridge.
9L18return=11 bridge: 2-3.
38.06.3

Connectivity augmentation

**Augmentation**: given a connected graph, what is the fewest number of edges to add so that no bridge remains (the graph becomes 2-edge-connected)? Contract the 2-edge-connected components into the bridge tree. A **leaf** of that tree is a component with exactly one bridge; unless a new edge ends inside it, that bridge stays. One new edge can touch at most two leaves, so at least ⌈leaves / 2⌉ edges are needed, and that many always suffice.

The answer is (leaves + 1) / 2 in integer arithmetic, and 0 when the bridge tree is a single point. The “Add edges: a path needs one” preset (0-1 1-2 2-3) has 2 leaves and needs 1 edge, closing the path into a cycle. The “Add edges: a star with four leaves” preset has 4 leaves and needs 2. The “Add edges: already 2-edge-connected” preset is a cycle and needs 0.

The sufficiency claim is a theorem (Eswaran and Tarjan); the exhaustive search in this course's test suite confirms the formula on every small graph tried. The animation reports the count, not the exact edges to add.

Java
1static int edgesToMakeBridgeless(int n, int[][] edges) {   // connected graph: edges to add so that no bridge remains
2    boolean[] isBridge = new boolean[edges.length];
3    for (int k : bridgesByRemoval(n, edges)) isBridge[k] = true;
4    int[] p = new int[n];
5    for (int i = 0; i < n; i++) p[i] = i;
6    for (int k = 0; k < edges.length; k++)
7        if (!isBridge[k]) p[find(p, edges[k][0])] = find(p, edges[k][1]);   // contract the 2-edge-connected components
8    int[] degree = new int[n];                                           // degree in the bridge tree
9    for (int k = 0; k < edges.length; k++)
10        if (isBridge[k]) { degree[find(p, edges[k][0])]++; degree[find(p, edges[k][1])]++; }
11    int leaves = 0;
12    for (int v = 0; v < n; v++) if (find(p, v) == v && degree[v] == 1) leaves++;
13    return (leaves + 1) / 2;                                             // every leaf needs a new edge; one edge serves two leaves
14}

Robustness: remove an edge or vertex, and how many edges to add

Interactive · edit the input

Your input

Try

undirected graph · 6 vertices · 7 edges

0
1
2
3
4
5
Removed edge or vertexIts removal splits the graphComponent 1Component 2

edges whose removal splits the graph

none yet
Setup

The graph starts with 1 component. Remove each edge in turn and count components again: if the count rises, that edge is a bridge. This brute force is O(m·(n+m)); the low-link DFS does it in O(n+m).

Step 1 / 9
Java
1static int components(int n, int[][] edges, int skipEdge, int skipVertex) {   // -1 means "skip nothing"
2    int[] p = new int[n];
3    for (int i = 0; i < n; i++) p[i] = i;
4    for (int k = 0; k < edges.length; k++) {
5        int a = edges[k][0], b = edges[k][1];
6        if (k == skipEdge || a == skipVertex || b == skipVertex) continue;
7        p[find(p, a)] = find(p, b);
8    }
9    int count = 0;
10    for (int v = 0; v < n; v++) if (v != skipVertex && find(p, v) == v) count++;
11    return count;
12}
13static List<Integer> bridgesByRemoval(int n, int[][] edges) {
14    int base = components(n, edges, -1, -1);
15    List<Integer> out = new ArrayList<>();
16    for (int k = 0; k < edges.length; k++)
17        if (components(n, edges, k, -1) > base) out.add(k);      // removing edge k splits a component
18    return out;
19}
20static List<Integer> articulationByRemoval(int n, int[][] edges) {
21    int base = components(n, edges, -1, -1);
22    List<Integer> out = new ArrayList<>();
23    for (int v = 0; v < n; v++)
24        if (components(n, edges, -1, v) > base) out.add(v);      // removing vertex v splits its component
25    return out;
26}
27static int edgesToMakeBridgeless(int n, int[][] edges) {         // connected graph: edges to add so no bridge remains
28    boolean[] isBridge = new boolean[edges.length];
29    for (int k : bridgesByRemoval(n, edges)) isBridge[k] = true;
30    int[] p = new int[n];
31    for (int i = 0; i < n; i++) p[i] = i;
32    for (int k = 0; k < edges.length; k++) if (!isBridge[k]) p[find(p, edges[k][0])] = find(p, edges[k][1]);
33    int[] degree = new int[n];                                   // degree in the bridge tree
34    for (int k = 0; k < edges.length; k++)
35        if (isBridge[k]) { degree[find(p, edges[k][0])]++; degree[find(p, edges[k][1])]++; }
36    int leaves = 0;
37    for (int v = 0; v < n; v++) if (find(p, v) == v && degree[v] == 1) leaves++;
38    return (leaves + 1) / 2;                                     // every leaf needs a new edge; one edge serves two leaves
39}

Live state

0 checks0 bridges

components

1

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L14components=1The graph starts with 1 component. Remove each edge in turn and count components again: if the count rises, that edge is a bridge. This brute force is O(m·(n+m)); the low-link DFS does it in O(n+m).
2L17edge=0-1 components=1 base=1Remove 0-1: 1 component (was 1). The count did not rise: another route connects its ends.
3L17edge=1-2 components=1 base=1Remove 1-2: 1 component (was 1). The count did not rise: another route connects its ends.
4L17edge=2-0 components=1 base=1Remove 2-0: 1 component (was 1). The count did not rise: another route connects its ends.
5L17edge=3-4 components=1 base=1Remove 3-4: 1 component (was 1). The count did not rise: another route connects its ends.
6L17edge=4-5 components=1 base=1Remove 4-5: 1 component (was 1). The count did not rise: another route connects its ends.
7L17edge=5-3 components=1 base=1Remove 5-3: 1 component (was 1). The count did not rise: another route connects its ends.
8L17edge=2-3 components=2 base=1Remove 2-3: 2 components (was 1). The count rose: it is a bridge.
9L18return=11 bridge: 2-3.
38.06.4

Edge-biconnectivity intro

Two notions of “survives one failure” are easy to confuse. A graph is **2-edge-connected** if it is connected and has no bridge: no single edge failure disconnects it. It is **biconnected** (2-vertex-connected) if it is connected, has at least three vertices, and has no cut vertex: no single vertex failure disconnects it.

Every biconnected graph is 2-edge-connected, but not the other way round. The bowtie (two triangles sharing vertex 2) has no bridge, so it is 2-edge-connected, but vertex 2 is a cut vertex, so it is not biconnected. Both properties have a clean characterisation (Whitney and Menger): a graph is 2-edge-connected exactly when every pair of vertices has two edge-disjoint paths, and biconnected exactly when every pair has two internally vertex-disjoint paths.

The code checks both properties with the removal helpers. Higher levels (3-edge-connected, k-vertex-connected) need max-flow ideas, which is where the next chapter, Network Flow and Minimum Cuts, comes in.

PropertyTestSurvivesExample
2-edge-connectedconnected and no bridgeany one edge failinga cycle; the bowtie
Biconnectedconnected, 3+ vertices, no cut vertexany one vertex failinga cycle; not the bowtie
Treeconnected, every edge a bridgenothinga path
Java
1static boolean isTwoEdgeConnected(int n, int[][] edges) {
2    return components(n, edges, -1, -1) == 1 && bridgesByRemoval(n, edges).isEmpty();
3}
4
5static boolean isBiconnected(int n, int[][] edges) {
6    return n >= 3 && components(n, edges, -1, -1) == 1 && articulationByRemoval(n, edges).isEmpty();
7}

Robustness: remove an edge or vertex, and how many edges to add

Interactive · edit the input

Your input

Try

undirected graph · 6 vertices · 7 edges

0
1
2
3
4
5
Removed edge or vertexIts removal splits the graphComponent 1Component 2

edges whose removal splits the graph

none yet
Setup

The graph starts with 1 component. Remove each edge in turn and count components again: if the count rises, that edge is a bridge. This brute force is O(m·(n+m)); the low-link DFS does it in O(n+m).

Step 1 / 9
Java
1static int components(int n, int[][] edges, int skipEdge, int skipVertex) {   // -1 means "skip nothing"
2    int[] p = new int[n];
3    for (int i = 0; i < n; i++) p[i] = i;
4    for (int k = 0; k < edges.length; k++) {
5        int a = edges[k][0], b = edges[k][1];
6        if (k == skipEdge || a == skipVertex || b == skipVertex) continue;
7        p[find(p, a)] = find(p, b);
8    }
9    int count = 0;
10    for (int v = 0; v < n; v++) if (v != skipVertex && find(p, v) == v) count++;
11    return count;
12}
13static List<Integer> bridgesByRemoval(int n, int[][] edges) {
14    int base = components(n, edges, -1, -1);
15    List<Integer> out = new ArrayList<>();
16    for (int k = 0; k < edges.length; k++)
17        if (components(n, edges, k, -1) > base) out.add(k);      // removing edge k splits a component
18    return out;
19}
20static List<Integer> articulationByRemoval(int n, int[][] edges) {
21    int base = components(n, edges, -1, -1);
22    List<Integer> out = new ArrayList<>();
23    for (int v = 0; v < n; v++)
24        if (components(n, edges, -1, v) > base) out.add(v);      // removing vertex v splits its component
25    return out;
26}
27static int edgesToMakeBridgeless(int n, int[][] edges) {         // connected graph: edges to add so no bridge remains
28    boolean[] isBridge = new boolean[edges.length];
29    for (int k : bridgesByRemoval(n, edges)) isBridge[k] = true;
30    int[] p = new int[n];
31    for (int i = 0; i < n; i++) p[i] = i;
32    for (int k = 0; k < edges.length; k++) if (!isBridge[k]) p[find(p, edges[k][0])] = find(p, edges[k][1]);
33    int[] degree = new int[n];                                   // degree in the bridge tree
34    for (int k = 0; k < edges.length; k++)
35        if (isBridge[k]) { degree[find(p, edges[k][0])]++; degree[find(p, edges[k][1])]++; }
36    int leaves = 0;
37    for (int v = 0; v < n; v++) if (find(p, v) == v && degree[v] == 1) leaves++;
38    return (leaves + 1) / 2;                                     // every leaf needs a new edge; one edge serves two leaves
39}

Live state

0 checks0 bridges

components

1

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L14components=1The graph starts with 1 component. Remove each edge in turn and count components again: if the count rises, that edge is a bridge. This brute force is O(m·(n+m)); the low-link DFS does it in O(n+m).
2L17edge=0-1 components=1 base=1Remove 0-1: 1 component (was 1). The count did not rise: another route connects its ends.
3L17edge=1-2 components=1 base=1Remove 1-2: 1 component (was 1). The count did not rise: another route connects its ends.
4L17edge=2-0 components=1 base=1Remove 2-0: 1 component (was 1). The count did not rise: another route connects its ends.
5L17edge=3-4 components=1 base=1Remove 3-4: 1 component (was 1). The count did not rise: another route connects its ends.
6L17edge=4-5 components=1 base=1Remove 4-5: 1 component (was 1). The count did not rise: another route connects its ends.
7L17edge=5-3 components=1 base=1Remove 5-3: 1 component (was 1). The count did not rise: another route connects its ends.
8L17edge=2-3 components=2 base=1Remove 2-3: 2 components (was 1). The count rose: it is a bridge.
9L18return=11 bridge: 2-3.

Practice ladder

Now try it yourself

Easy

  • Find if Path Exists in Graph

Medium

  • Critical Connections in a Network
  • Number of Operations to Make Network Connected

Advanced

  • Minimum Number of Days to Disconnect Island
  • Remove Max Number of Edges to Keep Graph Fully Traversable

Key takeaways

  • Removal tests are the definitions of bridges and cut vertices and make a good oracle for the DFS algorithms.
  • To make a connected graph 2-edge-connected add ⌈leaves / 2⌉ edges, where leaves are leaves of the bridge tree.
  • Biconnected implies 2-edge-connected, not the reverse.