Graph Theory37 sections · 1633 units
Open in Course

Articulation Points - Input Example

(Graph with critical vertices)

Input: n=5n=5, edges [[0,1],[1,2],[2,0],[1,3],[3,4]][[0,1],[1,2],[2,0],[1,3],[3,4]]. Graph: triangle 01200-1-2-0 with a tail 1341-3-4. Vertex 11 is an articulation point. Remove it, and you get components {0,2}\{0,2\} and {3,4}\{3,4\}. Vertex 33 is an articulation point.

Remove it, and you get {0,1,2}\{0,1,2\} and {4}\{4\}. Output: [1,3][1, 3]. These are the critical vertices holding the graph together. Vertices 00, 22, and 44 are not articulation points.