Question 1291

One Bridge Two Cutpoints

Undirected graph: two triangles joined by a single edge.

Triangle 0-1-2 joined to triangle 3-4-5 by the edge 2-3 01 23 45

DFS from 0, neighbours in increasing order, gives:

vertex 0 1 2 3 4 5
tin 0 1 2 3 4 5
low 0 0 0 3 3 3

Tree edges are 0-1, 1-2, 2-3, 3-4, 4-5. Using low[to] > tin[v] for a bridge and low[to] >= tin[v] for an articulation point on a non-root vertex, what do you get?

A

One bridge, 2-3. Three articulation points, 0, 2 and 3.

B

One bridge, 2-3. Two articulation points, 2 and 3.

C

One bridge, 2-3. One articulation point, 2.

D

Two bridges, 2-3 and 3-4. Two articulation points, 2 and 3.