Graph Algorithms • Reliability

Articulation Points

Also known as cut vertices, articulation points are nodes whose removal disconnects the graph. They represent critical single points of failure in networks.

Try Interactive Simulator

Criticality

An articulation point is a node that, if removed, increases the number of connected components in a graph.

Low-Link Logic

We use DFS discovery times and low-link values. If a child cannot reach any ancestor of its parent, the parent is critical.

Condition

For a non-root node u, it is an AP if it has a child v such that low[v] ≥ disc[u].

Root Case

The root of the DFS tree is an articulation point if and only if it has more than one child in the DFS spanning tree.

Loading Lab...

Graph Algorithms • Reliability

Articulation Points

Also known as cut vertices, articulation points are nodes whose removal disconnects the graph. They represent critical single points of failure in networks.

Try Interactive Simulator

Criticality

An articulation point is a node that, if removed, increases the number of connected components in a graph.

Low-Link Logic

We use DFS discovery times and low-link values. If a child cannot reach any ancestor of its parent, the parent is critical.

Condition

For a non-root node u, it is an AP if it has a child v such that low[v] ≥ disc[u].

Root Case

The root of the DFS tree is an articulation point if and only if it has more than one child in the DFS spanning tree.