4.3.5. Puntos de articulación y componentes biconexos en grafos no dirigidos.
Un grafo es biconexo si y sólo si tiene conectividad 2 o más.
El cálculo de los puntos de articulación se basa en un recorrido en profundidad.
Algoritmo para localizar los puntos de articulación de un grafo.
1. Realizar una búsqueda primero en profundidad, numerando los nodos en el orden en que son recorridos. En el array numero_bpp[1..N] guardamos el orden de cada nodo.
2. En los puntos de terminación de las llamadas recursivas de bpp (orden posterior) calcular los valores bajo[v] para cada nodo, según la fórmula:
bajo[v] = mínimo (numero_bpp[v],
numero_bpp[z] | tal que exista un arco de retroceso (z, v),
bajo [y] | para todo y hijo de v en el árbol generado)
3. La raíz es un punto de articulación si y sólo si tiene dos o más hijos en el árbol abarcador en profundidad.
4. Un nodo v, distinto de la raíz, es un punto de articulación si y sólo si tiene algún hijo w en el árbol tal que bajo[w] ? numero_bpp[v].