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

3.5.9 · Coding › Graphs

HUM KYA compute kar rahe hain?

Do key numbers

Formula Low-link recurrence ko scratch se derive karna

KYA $u$ wapas upar chadh ke reach kar sakta hai? Teen sources:

Khud apne aap: $u$ hamesha apna discovery time "reach" kar sakta hai → $low [u] = disc [u]$ se shuru karo.
Kisi tree child $v$ ke zariye: jo bhi child ki subtree reach kar sakti hai woh $u$ se bhi reachable hai → $min (low [u], low [v])$ lo.
Kisi back edge $u \to w$ ke zariye (jahan $w$ ek ancestor hai, already visited, parent nahi) → $min (low [u], disc [w])$ lo.

Sab milaakar: $low [u] = min (disc [u], min_{v tree child} low [v], min_{w back edge} disc [w])$

Back edges ke liye disc[w] kyun aur low[w] kyun nahi? Ek back edge ek tree edge nahi hai — hum ise sirf record karne ke liye use karte hain ki hum kitna upar jump kiye, jo exactly $disc [w]$ hai. $low [w]$ use karna paths ko double-count karega aur galat results dega.

Bridge aur articulation conditions

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

Reference implementation

def tarjan(n, adj):
    disc = [-1]*n
    low  = [0]*n
    timer = [0]
    bridges, aps = [], set()
 
    def dfs(u, parent):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        children = 0
        for v in adj[u]:
            if v == parent:
                continue                 # skip the edge we came down on
            if disc[v] == -1:            # tree edge
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((u, v))     # bridge:  strict >
                if parent != -1 and low[v] >= disc[u]:
                    aps.add(u)                 # AP non-root: >=
            else:                        # back edge
                low[u] = min(low[u], disc[v])
        if parent == -1 and children > 1:
            aps.add(u)                   # AP root: 2+ children
    for s in range(n):
        if disc[s] == -1:
            dfs(s, -1)
    return bridges, aps

Worked example 1 — ek simple bridge

Graph: 0 - 1 - 2 aur 2 - 3 - 2? Chalte hain edges $0 - 1, 1 - 2, 2 - 3, 3 - 1$ use karte hain.

step	action	disc/low
visit 0	root	disc0=0, low0=0
→1 tree	child of 0	disc1=1, low1=1
→2 tree	child of 1	disc2=2, low2=2
→3 tree	child of 2	disc3=3, low3=3
3→1 back	back edge to 1	low3 = min(3, disc1=1) = 1
back to 2	low2 = min(2, low3=1) = 1
edge (2,3)?	low3=1 ≤ disc2=2 → not bridge
back to 1	low1 = min(1, low2=1) = 1
edge (1,2)?	low2=1 ≤ disc1=1 → not bridge
back to 0	low0 = min(0, low1=1) = 0
edge (0,1)?	low1=1 > disc0=0 → BRIDGE

Ye step kyun? Vertex 1 ke neeche subtree (cycle 1-2-3) sirf disc=1 tak wapas chadh sakti hai, kabhi 0 tak nahi. Toh $(0, 1)$ akela link hai → bridge. Saath hi vertex 1 (non-root) ka child 2 hai jiske liye $low [2] = 1 \geq disc [1] = 1$ ⇒ 1 ek articulation point hai.

Worked example 2 — root rule

Graph: star 1-0, 2-0, 3-0 (0 beech mein). DFS from 0.

0 root hai, children 1, 2, 3 ko teen alag tree children ki tarah discover karta hai (unke beech koi edges nahi).
children count = 3 > 1 ⇒ 0 ek articulation point hai.

Ye step kyun? 0 hatao toh 1, 2, 3 poori tarah isolated ho jaate hain — unke beech ke saare paths 0 se guzarte the. Root rule (≥2 children) exactly yahi capture karta hai.

Active recall

Recall Peekne se pehle predict karo (Forecast-then-Verify)

Ek simple cycle $0 - 1 - 2 - 3 - 0$ ke liye: kitne bridges hain? Kitne articulation points hain?

Answer: Dono mein se ek bhi nahi. Har edge cycle mein hai, isliye har node ka ek alternate route hai — koi bhi akeli failure use disconnect nahi kar sakti. (Check karo: har $low [v] \leq disc [parent]$ back edge ke zariye jo cycle band karti hai.)

Recall Feynman: 12-saal ke bachche ko explain karo

Socho ek treehouse fort hai jo rope bridges se connected hai. Tum ropes se neeche utarte hue naye platforms explore karte ho. $disc$ woh order hai jisme tumne har platform reach kiya. $low$ woh sabse upar wala platform hai jis par tum ek secret shortcut rope use karke swing back kar sakte ho. Agar fort ka ek poora section sirf khud tak hi swing back kar sake aur kabhi upar nahi, toh usse pakdne wali akeli rope special hai — use kaat do aur woh section ud jaayega (ek bridge). Aur woh platform jisse hoke sabko kahin bhi jaana padta hai woh ek must-not-break support hai (ek articulation point).

Graph mein bridge kya hota hai?

Ek aisi edge jiske hatane se connected components ki sankhya badh jaati hai.

Articulation point kya hota hai?

Ek aisa vertex jiske hatane se (uski edges ke saath) connected components ki sankhya badh jaati hai.

disc[u] ki definition?

DFS discovery timestamp — woh order jisme u ko pehli baar visit kiya jaata hai.

low[u] ki definition?

Sabse choti discovery time jo u ki subtree se reachable hai, tree edges neeche aur zyada se zyada ek back edge use karke.

Low-link recurrence?

low[u] = min(disc[u], min low[v] tree children par, min disc[w] back edges par).

Back edge ke liye disc[w] kyun use karte hain (low[w] nahi)?

Back edge sirf record karti hai ki hum kitna upar jump kiye; low[w] use karne se over-count hoga aur galat values aayenge.

Tree edge (u,v) ke liye bridge condition?

low[v] > disc[u] (strict).

Non-root u ke liye articulation condition child v ke saath?

low[v] >= disc[u].

DFS root ke liye articulation condition?

Uske 2 ya zyada DFS-tree children hain.

Bridge strict (>) kyun hai lekin AP (>=) kyun?

Bridge ek edge delete karta hai; u tak hi jaane wali back edge use bachaa leti hai. AP vertex u ko delete karta hai; u tak jaane wali back edge bhi useless hai jab u chala jaaye.

Tarjan's algorithm ki time complexity?

O(V + E), ek single DFS pass.

Undirected DFS mein kaun se edge types aate hain?

Sirf tree edges aur back edges (koi forward/cross edges nahi).

Parallel edges ke saath kya pitfall hai?

v==parent skip karna ek doosri parallel edge ko ignore karta hai; edge id track karo aur parent edge ko sirf ek baar skip karo.

Connections

Depth-First Search — backbone traversal jo DFS tree produce karta hai.
Strongly Connected Components - Tarjan — directed graphs par same low-link idea.
Biconnected Components — articulation points graph ko inme partition karte hain.
Bridge Trees / 2-edge-connected components — non-bridge edges ko contract karo.
Connected Components — jo cheez bridges/cut vertices todti hain.
Big-O Notation — $O (V + E)$ kyun matter karta hai.