Graph Theory37 sections · 1633 units
Open in Course

Articulation Point Walkthrough

(Step-by-step execution)

Graph: 010-1, 121-2, 020-2, 131-3. Start DFS at 00. Visit 00: disc[0]=0. Visit 11: disc[1]=1. Visit 22: disc[2]=2. Back edge 202-0: low[2]=0. Backtrack: low[1]=0. Visit 33: disc[3]=3, low[3]=3. Backtrack: check low[3]=3 >= disc[1]=1, so 11 is an articulation point.

Root 00 has only 11 child, so not an articulation point. Final articulation points: {1}\{1\}. Removing 11 splits the graph into {0,2}\{0,2\} and {3}\{3\}.