Articulation points and bridges — Tarjan's low-link values: Foundations

Before you can read the parent note, you must own eight small ideas. Each one is a picture first, a symbol second. We build them in order: every later idea only uses words already earned.

1. What is a graph? (dots and lines)

We draw this as circles with lines between them. Nothing more.

Figure — Articulation points and bridges — Tarjan's low-link values

2. Counting dots and lines: $V$ and $E$

Recall What does

$O (V + E)$ promise? That the algorithm touches each vertex and each edge a small constant number of times — no nested re-scanning ::: so the total work is proportional to $V + E$ , the size of the graph itself.

3. Connected, and "connected components"

Picture a map that splits into two islands with no road between them: that is two connected components.

4. DFS — walking the graph on a rope

5. The DFS tree: tree edges and back edges

When DFS runs, colour the roads by how they were used:

A tree edge is a road you drove down to reach a brand-new city for the first time.
A back edge is a road that leads to a city you've already visited — specifically an ancestor, a city higher up the rope you're currently hanging from.

The tree edges alone form the DFS tree: a family tree of "who discovered whom."

6. Timestamps: what `disc[u]` means

Recall If

$disc [a] < disc [b]$ , who might be the ancestor? $a$ was discovered first, so on any root-to- $b$ path, $a$ could sit above $b$ ::: smaller disc = discovered earlier = potentially an ancestor / higher in the tree.

7. The `low` value: highest reachable, as a number

Picture the fort again: from your platform and everything below it, what is the highest platform you can swing back to using one secret shortcut rope? Its timestamp is $low [u]$ .

The parent's recurrence assembles $low [u]$ from three sources — itself, its children's low, and its own back edges' disc. Each of those three words is now defined, so that formula is fully readable.

8. The " $min$ " symbol and why comparisons decide everything

How the foundations feed the topic

Read top to bottom: dots and lines become a DFS tree; timestamps make "height" a number; the low value compares those numbers; and the whole thing detects splits without ever deleting anything.

Related deeper machinery you will meet later, all built on this same low-link idea: Strongly Connected Components - Tarjan, Biconnected Components, and Bridge Trees / 2-edge-connected components.

Equipment checklist

Test yourself — say the answer out loud before revealing.

A vertex is ::: a single dot, one "city" in the network.
An edge $(u, v)$ is ::: a line joining two dots; here it is a two-way (undirected) road, so $(u, v)$ and $(v, u)$ mean the same road.
$V$ and $E$ are ::: the number of vertices (cities) and the number of edges (roads).
$O (V + E)$ means ::: total work grows in step with cities-plus-roads; each vertex and edge is handled a constant number of times.
A connected component is ::: a maximal group of cities all reachable from one another by roads.
DFS is ::: a walk that goes as deep as possible down unexplored roads, backing up only when stuck.
A tree edge vs a back edge is ::: a road used to reach a brand-new city vs a road leading to an already-visited ancestor (a climb upward).
An ancestor of $v$ is ::: any city on the path from the DFS-tree root down to $v$ .
$disc [u]$ is ::: the order number (0,1,2,...) stamped on $u$ when DFS first reaches it; smaller = higher/earlier.
$low [u]$ is ::: the smallest disc reachable from $u$ 's subtree using tree edges down and at most one back edge up — i.e. the highest city that subtree can escape to.
$min (a, b)$ is ::: the smaller of the two, used to keep the best (highest) escape.