Motivace: Představme si situaci za války, kdy partyzáni znemožňovali postup vojsk tak, že vyhodili do povětří vhodný most a tím přerušili silniční spojení. Dostaneme graf silniční sítě a ptáme se, jestli v ní existuje vrchol (křižovatka) nebo hrana (most) taková, že se po jejím vyhození graf rozpadne na několik komponent.

Pokud se Vám zdá motivace příliš zastaralá, tak místo partyzánů představte teroristy a místo silniční sítě síť počítačovou.

Definice: Graf je $2$-souvislý, pokud po vyhození libovolného vrcholu zůstane souvislý. Platí věta, že graf je $2$-souvislý právě tehdy, když každé dva vrcholy leží na společné kružnici. $2$-souvislá komponenta je maximální $2$-souvislý podgraf. Artikulace je vrchol, po jehož vyhození se graf rozpadne na komponenty souvislosti. Podobně most je hrana, po jejímž vyhození se graf rozpadne. Most je také $2$-souvislá komponenta.

Na následujícím obrázku jsou $2$-souvislé komponenty znázorněny šedými obláčky. Jedna artikulace může patřit do několika $2$-souvislých komponent.

Úkol: Dostaneme graf a chtěli bychom najít všechny jeho artikulace, případně vypsat $2$-souvislé komponenty.

Triviálním řešením je postupně zkusit vyhodit každý vrchol a testovat souvislost výsledného grafu. To by nám ale zabralo čas $\OO(n(n+m))$. Podívejme se na lepší řešení pomocí DFS:

Pozorování: $v$ je artikulace $\Longleftrightarrow$ $v$ je kořen DFS stromu a má alespoň dva potomky nebo není kořen a má syna $w$ takového, že z žádného jeho potomka (včetně $w$) nevede zpětná hrana do předchůdce $v$.

$\def\LOW{{\tt LOW}}$
Přípustná cesta je cesta vedoucí po stromových hranách směrem od kořene, která může končit jedním skokem zpět po zpětné hraně. Pro každý vrchol grafu spočítáme funkci $\LOW(v)=\min \{ {\tt in}[w] \,|\,\mbox{z $v$ do $w$ vede přípustná cesta} \}$. Funkci $\LOW(v)$ můžeme počítat už při průchodu do hloubky, protože při opuštění vrcholu $v$ známe všechny potřebné hodnoty ${\tt in}[w]$. Funkci spočítáme jako $\LOW(v)=\min\{x, y, z\}$, kde $x= {\tt in}[v]$, $y=\min\{ {\tt in}[w] \,|\, vw\mbox{ je zpětná hrana}\}$ a $z=\min\{ \mbox{$\LOW$}[w]\,|\, vw\mbox{ je stromová hrana}\}$.

Předchozí pozorování můžeme přeformulovat pomocí funkce $\LOW$.

Pozorování: $v$ je artikulace $\Longleftrightarrow$ $v$ je kořen DFS stromu a má alespoň dva potomky nebo není kořen a má syna $w$ s $\mbox{$\LOW$($w$)}\ge {\tt in[v]}$

Na základě pozorování poznáme už při průchodu grafu do hloubky, které vrcholy jsou artikulace. Dodejme, že artikulace nemůžeme vypisovat rovnou, protože bychom mohli některé vypsat dvakrát. Musíme si u každého vrcholu pamatovat, jestli je artikulace, a výsledek vypsat až nakonec. Pokud bychom chtěli vypsat i hrany každé $2$-souvislé komponenty, tak stačí během DFS ukládat procházené hrany na druhý zásobník. Při návratu do artikulace vypíšeme všechny hrany, které přibyly na zásobníku od posledního opuštění artikulace (stačí vhodně uříznout vršek zásobníku).