← Volver a los ejercicios

low, puntos de articulación y puentes

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.

1. El grafo con la profundidad hecha

Grafo:

━ arista del árbol ┅ arista de retroceso el número gris sobre cada arista es su identificador

La profundidad arranca en el 0 y recorre los vecinos de menor a mayor. Aristas:

2. Escoja el low de cada vértice

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.

3. Marque los puntos de articulación y los puentes

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.

Vértices que son punto de articulación:
Aristas que son puente:

4. Para llevarse

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.