Una sola profundidad deja dos números por vértice: d,
el momento en que se descubre, y low, el d más bajo
al que llega su subárbol con un salto de retroceso. Con esos dos números salen
los puntos de articulación y los puentes. La profundidad ya corrió: el árbol
está dibujado y cada vértice trae su d. Falta escoger los
low y después marcar las piezas de corte.
La profundidad arranca en el 0 y recorre los vecinos de menor a mayor. Aristas:
Conviene empezar por las hojas del árbol
y subir: el low de un vértice necesita el de sus hijos. Cada
hijo aporta su low, cada retroceso aporta el d del
otro extremo, y la arista por la que se llegó no aporta nada.
La raíz es punto de articulación cuando tiene dos
hijos o más en el árbol; cualquier otro vértice, cuando algún hijo
w cumple low[w] ≥ d[u]. Una arista de árbol es
puente cuando low[w] > d[v], con desigualdad estricta.
Sin solución aquí. En el segundo grafo hay dos
puntos de articulación y ningún puente: diga, para cada uno, cuál es el
hijo que lo marca y por qué la arista hacia ese hijo no es puente. En el
tercer grafo, agregue la arista 4–5 y vuelva a trazar a mano: ¿qué puentes
sobreviven y qué puntos de articulación se pierden? Y en el primero, corra
la profundidad desde el 4 en lugar del 0: los d y los
low cambian, el puente no.