Graph Theory37 sections · 1633 units
Open in Course

Low-Link Example

Computing values step by step

Graph: 121-2, 232-3, 313-1, 242-4. Start DFS at 11. Discovery times: disc[1]=0, disc[2]=1, disc[3]=2, disc[4]=3. Low-link values: low[1]=0 (reaches itself), low[2]=0 (back edge 313-1 reaches 11), low[3]=0 (back edge 313-1), low[4]=3 (no back edges, dead end).

Edge 242-4 is a bridge because low[4]=3 > disc[2]=1. The subtree of 44 cannot reach anything earlier than 44 itself. Removing edge 242-4 disconnects node 44 from the rest.