4.3.5. Puntos de articulación y componentes biconexos en grafos no dirigidos.
Definición: un punto de articulación de un grafo no dirigido G es un nodo v tal que cuando es eliminado de G (junto con las aristas incidentes en él) se divide un componente conexo del grafo original en dos o más componentes conexos.
Ejemplo. Si el grafo representa una red de ordenadores, un punto de articulación será un nodo que si no funciona, hará que otros ordenadores de la red queden incomunicados.
- Definición: un grafo no dirigido se dice que es biconexo si no tiene puntos de articulación.
- Definición: un grafo G tiene conectividad k si la eliminación de k-1 nodos (con sus aristas) no desconecta el grafo.