4.3.5. Puntos de articulación y componentes biconexos en grafos no dirigidos.

• Ejemplo.

a

c

b

e

d

g

f

n_bpp[a] = 1

bajo[a] = 1

n_bpp[d] = 3

bajo[d] = 1

n_bpp[b] = 2

bajo[b] = 1

n_bpp[g] = 7

bajo[g] = 5

n_bpp[e] = 4

bajo[e] = 1

n_bpp[c] = 5

bajo[c] = 5

n_bpp[f] = 6

bajo[f] = 5

a es la raíz y tiene dos hijos ? a es un punto de articulación

c tiene un hijo f tal que bajo[f]=5 ? n_bpp[c]=5 ? c es un punto de articulación

• bajo[v] indica el menor valor de bpp alcanzable desde v hasta algún descendiente y luego a través de un arco de retroceso.

• Si se cumple la condición del punto 4 (bajo[w] ? numero_bpp[v], para algún hijo w de v), si eliminamos v entonces w y sus descendientes no pueden alcanzar los nodos antecesores de v.

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica