19. Árboles generadores

19.1 Introducción

Un grafo conectado puede contener múltiples rutas redundantes y numerosos ciclos. Si queremos conservar la comunicación entre todos los vértices utilizando menos conexiones, podemos seleccionar un subconjunto de aristas.

Cuando ese subconjunto conecta todos los nodos y no contiene ciclos, forma un árbol generador, también llamado árbol de expansión.

19.2 Definición

Un árbol generador T de un grafo conectado G es un subgrafo que contiene todos los vértices de G y es un árbol.

No se crean conexiones nuevas: solo se eligen algunas aristas del grafo original.

19.3 Propiedades principales

• Incluye todos los vértices del grafo original.
• Utiliza únicamente aristas que ya existían.
• Conecta cada par de vértices mediante un camino.
• No contiene ciclos.
• Si el grafo tiene n vértices, utiliza n − 1 aristas.
• Eliminar cualquiera de sus aristas lo desconecta.

19.4 Existencia

Todo grafo no dirigido y conectado posee al menos un árbol generador. Si el grafo ya es un árbol, su único árbol generador es el propio grafo.

Un grafo desconectado no puede tener un árbol que incluya todos sus vértices, aunque sí puede tener un bosque generador.

19.5 Simulación interactiva: selecciona un árbol generador

Pulsa cerca de una arista para seleccionarla o descartarla. Debes conectar los siete vértices sin formar ciclos y usando exactamente seis conexiones.

Los dos botones de ejemplo producen árboles distintos sobre los mismos vértices. Esto muestra que un grafo puede tener múltiples árboles generadores.

19.6 Eliminar aristas de ciclos

Una forma de obtener un árbol generador consiste en comenzar con el grafo completo y eliminar una arista de cada ciclo sin desconectarlo.

El proceso termina cuando quedan n − 1 aristas.

19.7 Agregar aristas sin crear ciclos

También podemos comenzar sin aristas y agregarlas una por una, siempre que conecten partes diferentes y no formen ciclos.

Esta idea aparece en el algoritmo de Kruskal.

19.8 Árbol generado por DFS o BFS

Durante DFS o BFS, cada vértice nuevo se descubre mediante una arista. El conjunto de esas aristas de descubrimiento forma un árbol generador.

19.9 Árbol generador y árbol mínimo

Todo árbol de expansión mínima es un árbol generador, pero un árbol generador cualquiera no considera costos.

Los árboles mínimos se estudiarán más adelante mediante los algoritmos de Prim y Kruskal.

19.10 Construir un árbol con DFS

function arbolGeneradorDFS(grafo, origen) {
  const visitados = new Set([origen]);
  const aristasArbol = [];

  function dfs(actual) {
    for (const vecino of grafo[actual]) {
      if (!visitados.has(vecino)) {
        visitados.add(vecino);
        aristasArbol.push([actual, vecino]);
        dfs(vecino);
      }
    }
  }

  dfs(origen);
  return aristasArbol;
}

19.11 Validar un árbol generador

function esArbolGenerador(vertices, aristas, estaConectado, tieneCiclo) {
  return estaConectado &&
         !tieneCiclo &&
         aristas.length === vertices.length - 1;
}

console.log(esArbolGenerador(
  ["A", "B", "C", "D"],
  [["A", "B"], ["B", "C"], ["C", "D"]],
  true,
  false
));

19.12 Errores comunes

• Omitir algún vértice del grafo original.
• Agregar una arista que no existe en el grafo.
• Seleccionar n − 1 aristas sin comprobar conectividad.
• Mantener todos los vértices pero permitir un ciclo.
• Confundir cualquier árbol del dibujo con un árbol generador.
• Suponer que el árbol generador siempre es único.

19.13 Qué debes recordar de este tema

• Un árbol generador contiene todos los vértices del grafo.
• Sus aristas pertenecen al grafo original.
• Debe ser conectado y no contener ciclos.
• Con n vértices utiliza exactamente n − 1 aristas.
• Todo grafo conectado posee al menos un árbol generador.
• DFS y BFS producen árboles generadores mediante aristas de descubrimiento.

19.14 Conclusión

Un árbol generador elimina conexiones redundantes sin perder ningún vértice ni la conectividad. Esta estructura sirve como esqueleto de una red y como base de numerosos algoritmos.

En el próximo tema estudiaremos el recorrido en profundidad, una de las formas fundamentales de explorar grafos y construir árboles generadores.