Cut Vertices and Bridges

Graph Theory · Axiom Academy

LESSON Cut Vertices and Bridges Understanding critical components in graph connectivity and network reliability 1. Cut Vertices (Articulation Points) A cut vertex is critical to graph connectivity. When removed along with its incident edges, the graph becomes disconnected or the number of components increases. Watch the animation: Vertex C is a cut vertex. When we remove it, the graph splits into two disconnected components. A bridge is a critical edge in graph connectivity. Unlike cut vertices which are vertices, bridges are edges. When a bridge is removed, the graph becomes disconnected. Watch the animation: The edge (B, D) is a bridge. When we remove it, the graph splits into two disconnected components. 3. Finding Cut Vertices and Bridges To identify cut vertices and bridges, we can use depth-first search (DFS) with additional tracking: Compute discovery time : when each vertex is first visited Compute low value : earliest visited vertex reachable from subtree A vertex v is a cut vertex if it has a child u where low[u] ≥ disc[v] An edge (u, v) is a bridge if low[v] > disc[u] Watch the animation: See how DFS identifies cut vertices by tracking discovery times and low values. 4. Network Reliability and Single Points of Failure Cut vertices and bridges represent single points of failure in networks: Computer Networks: Routers that are cut vertices represent critical network nodes Transportation: Bridges in road networks are literal critical connections

This is the written version of the interactive lesson above. See the full Graph Theory course.