16 - Puntos de articulación (Articulation Points)

Un punto de articulación es un vértice que, al eliminarlo junto con sus aristas incidentes, incrementa la cantidad de componentes conexas del grafo no dirigido. Detectarlos revela nodos críticos de conectividad.

16.1 Definición

• En un árbol, todos los nodos internos son puntos de articulación; las hojas no.
• En un ciclo simple, ningún nodo es punto de articulación.
• Solo consideramos grafos no dirigidos; en digrafos se requieren otras variantes.

16.2 Tarjan paso a paso

El algoritmo de Tarjan para puntos de articulación reutiliza tin[] y low[] con DFS:

• Asignamos tin[u] = low[u] = timer++ al descubrir u.
• Para cada vecino v: si es el padre, se ignora; si no está visitado, se desciende y luego low[u] = min(low[u], low[v]).
• Condición de articulación: si low[v] >= tin[u], el nodo u separa el subárbol de v del resto.
• La raíz del DFS es punto de articulación solo si tiene 2 o más hijos en el árbol DFS.

Simulador de puntos de articulación

16.3 Interpretación de resultados

• Un punto de articulación indica un nodo sin redundancia: su falla fragmenta la red.
• Al remover todos los puntos de articulación se obtiene un conjunto de componentes biconexas (bloques 2-conexos).
• Si no hay puntos de articulación, el grafo es 2-conexo respecto de vértices (no se separa al quitar un solo nodo).

16.4 Casos clave de conectividad

1. Nodos críticos de conectividad
   • Cada uno representa un punto central cuya eliminación separa el grafo en más componentes.
   • En una red de computadoras: routers centrales, switches clave, nodos que si fallan cortan la red.
2. Análisis de vulnerabilidad
   • En infraestructuras (red eléctrica, transporte): señalan dónde conviene redundar recursos.
   • Ejemplos: estaciones centrales, cruces críticos de rutas, subestaciones clave.
3. Detección de hubs en grafos sociales
   • Un nodo articulación puede ser la persona o entidad que conecta grupos distintos.
   • Si se retira, la red se fragmenta en comunidades separadas.

16.5 Aplicación completa para probar en CLion

Implementación con listas de adyacencia que imprime todos los puntos de articulación encontrados.

#include <stdio.h>
#include <stdlib.h>

typedef struct Arista {
  int destino;
  struct Arista *sig;
} Arista;

typedef struct {
  int n;
  Arista **listas;
} Grafo;

Grafo crearGrafo(int n) {
  Grafo g;
  g.n = n;
  g.listas = calloc(n, sizeof(Arista *));
  return g;
}

void agregarAristaNoDirigida(Grafo *g, int u, int v) {
  Arista *a = malloc(sizeof(Arista));
  a->destino = v;
  a->sig = g->listas[u];
  g->listas[u] = a;

  Arista *b = malloc(sizeof(Arista));
  b->destino = u;
  b->sig = g->listas[v];
  g->listas[v] = b;
}

void dfsArticulacion(const Grafo *g, int u, int padre, int *visitado, int *tin, int *low, int *timer, int *hijoRaiz, int *esArticulacion) {
  visitado[u] = 1;
  tin[u] = low[u] = (*timer)++;

  for (Arista *it = g->listas[u]; it; it = it->sig) {
    int v = it->destino;
    if (v == padre) continue;
    if (!visitado[v]) {
      if (padre == -1) (*hijoRaiz)++; /* contar hijos de la raiz */
      dfsArticulacion(g, v, u, visitado, tin, low, timer, hijoRaiz, esArticulacion);
      if (low[v] >= tin[u]) esArticulacion[u] = 1;
      if (low[v] < low[u]) low[u] = low[v];
    } else {
      if (tin[v] < low[u]) low[u] = tin[v];
    }
  }
}

void encontrarPuntosArticulacion(const Grafo *g) {
  int *visitado = calloc(g->n, sizeof(int));
  int *tin = malloc(g->n * sizeof(int));
  int *low = malloc(g->n * sizeof(int));
  int *esArticulacion = calloc(g->n, sizeof(int));
  int timer = 0;

  for (int u = 0; u < g->n; u++) {
    if (!visitado[u]) {
      int hijoRaiz = 0;
      dfsArticulacion(g, u, -1, visitado, tin, low, &timer, &hijoRaiz, esArticulacion);
      if (hijoRaiz < 2) esArticulacion[u] = 0;
    }
  }

  printf("Puntos de articulacion:\n");
  for (int i = 0; i < g->n; i++) {
    if (esArticulacion[i]) {
      printf(" - %d\n", i);
    }
  }

  free(visitado);
  free(tin);
  free(low);
  free(esArticulacion);
}

int main(void) {
  Grafo g = crearGrafo(7);
  agregarAristaNoDirigida(&g, 0, 1);
  agregarAristaNoDirigida(&g, 1, 2);
  agregarAristaNoDirigida(&g, 2, 0); /* ciclo 0-1-2 */
  agregarAristaNoDirigida(&g, 1, 3); /* 1 es articulacion */
  agregarAristaNoDirigida(&g, 3, 4);
  agregarAristaNoDirigida(&g, 4, 5);
  agregarAristaNoDirigida(&g, 5, 3); /* ciclo 3-4-5 */
  agregarAristaNoDirigida(&g, 4, 6); /* 4 es articulacion */

  encontrarPuntosArticulacion(&g);
  return 0;
}