Zweifach zusammenhängende Komponenten (II)

Bestimmung der Artikulationspunkte durch Tiefensuche.

Sei (V, B) ein DFS-Baum für G = (V, E) und t : V$\to$$\mathbb {N}$ die dazu gehörende Knotenreihenfolge.

Def: L(v) : = min{t(u) | v$\to_{B}^{*}$w$\to_{E \setminus B}^{0,1}$u}

Satz: u ist Artikulationspunkt $\iff$

• u ist Wurzel von B und outdeg_B(u) > 1
• oder u ist nicht Wurzel von B und $\exists$uv $\in$ E : L(v)$\ge$t(u).

Aufgabe: ist hier L(v) > t(u) möglich?